Recursive function to solve prefix binary expressions

I'm trying to write a recursive program in SMLNJ that will accept short binary expressions in string form (such as "+*1100"), evaluate the correct solution, then return it.

I currently have two functions:

 fun preEval [x] = [x]
  | preEval [] = []
  | preEval (opt::opr1::opr2::xs) =
 if (opr1 = #"1" orelse opr1 = #"0") andalso (opr2 = #"1" orelse opr2 = #"0") 
 then pcEval(opt,opr1,opr2)::xs else preEval(opt::preEval(opr1::opr2::xs));

and I have a helper function that solves an individual expression within a larger expression (like "*11" in "+*0011"):

fun pcEval(x,y,z) = x
 | pcEval("+","0","0") = 0
 | pcEval("+","0","1") = 1
 | pcEval("+","1","0") = 1
 | pcEval("+","1","1") = 1
 | pcEval("*","0","0") = 0
 | pcEval("*","1","0") = 0
 | pcEval("*","0","1") = 0
 | pcEval("*","1","1") = 1;

The idea is that you would pass in the string to preEval using the String.explode function like this: preEval(explode("*+1011"), which would explode the string into a list which can be used to evaluate.

The problem I have is with my pcEval function as I'm not sure how to evaluate and handle the smaller binary expressions within a larger expression.

Is there any way I can evaluate the smaller binary expressions first or is their a better method for doing this entire program in general?

1 answer

  • answered 2019-03-14 10:52 Simon Shine

    As molbdnilo says, you don't really say how one should interpret the expression "+*1100".

    Is there any way I can evaluate the smaller binary expressions first or is their a better method for doing this entire program in general?

    There are many ways to evaluate expressions depending on the complexity of the expression language. For example, for an RPN calculator (e.g. "2 20 + 3 *" means "(2 + 20) * 3"), you might process a stream of characters and push each number to a stack and evaluate each operator by popping the right number of elements off the stack (a recursive-descent parser):

    fun parse_and_eval ([], NONE, stack) = stack
      | parse_and_eval ([], SOME n, stack) = n::stack
      | parse_and_eval (c::cs, NONE, stack) =
        if Char.isDigit c
        then parse_and_eval (cs, SOME (ord c - ord #"0"), stack)
        else if c = #"+"
             then case stack of
                       (x::y::rest) => parse_and_eval (cs, NONE, x + y :: rest)
                     | rest => raise Fail "Too few elements to pop from stack!"
             else if c = #" "
                  then parse_and_eval (cs, NONE, stack)
                  else raise Fail ("Unknown symbol " ^ str c)
    
      | parse_and_eval (c::cs, SOME n, stack) =
        if Char.isDigit c
        then parse_and_eval (cs, SOME (n * 10 + ord c - ord #"0"), stack)
        else if c = #"+"
             then case stack of
                       (y::rest) => parse_and_eval (cs, NONE, n + y :: rest)
                     | [] => raise Fail "Too few elements to pop from stack!"
             else if c = #" "
                  then parse_and_eval (cs, NONE, n::stack)
                  else raise Fail ("Unknown symbol " ^ str c)
    

    An example of using this:

    - parse_and_eval (explode "123", NONE, []);
    > val it = [123] : int list
    - parse_and_eval (explode "123 456", NONE, []);
    > val it = [456, 123] : int list
    - parse_and_eval (explode "123 456 +", NONE, []);
    > val it = [579] : int list
    - parse_and_eval (explode "123 456 + 87", NONE, []);
    > val it = [87, 579] : int list
    - parse_and_eval (explode "123 456 + 87 +", NONE, []);
    > val it = [666] : int list
    - parse_and_eval (explode "123 456 87 + +", NONE, []);
    > val it = [666] : int list
    - parse_and_eval (explode "123 456 87 + + +", NONE, []);
    ! Uncaught exception:
    ! Fail  "Too few elements to pop from stack!"
    

    This piece of code is, however, bad software. It is one function that tries to do a lot of things at once, which makes it very hard to decipher the individual parts, and even harder to extend: For example, if you wanted to support other operators, you'd need to add them in two places.

    But the general mechanism is OK: You scan one digit ahead and build tokens, which are either integers made from multiple digit characters or an operator made from a single character.

    You may find it enjoyable to try and extend this, or you may like to try and separate the concerns of the function. For example, it is possible to split parsing and evaluation in two:

    datatype token = Int of int | Op of int * int -> int
    type stack = int list
    
    val parse : char list -> token list
    val eval : token list -> stack
    

    You may like to use helper functions that accumulate intermediate results:

    val parse_helper : char list -> int option -> token list
    val eval_helper : token list -> stack -> stack
    

    You may also want to look into parser combinators for SML: