re
run
.
me

Evaluating Infix Expression With Parentheses in Groovy - Multiple Digits

When I wrote this write-up on evaluating an infix expression having multiple digits, I was lazy to do it for expressions with parentheses. So, here it comes.

As usual, here is the javascript version.

Just like the non-paranthesized version, this algorithm is just the two stack algorithm modified to accommodate parentheses and multiple digits. Floating points aren’t supported intentionally nor is tested. However, I don’t see any reason why it should not work (provided you change the variable types to accommodate a floating point number).

The algorithm goes like this :

1. Initialize two stacks - one for holding values and one for holding operators
2. Read the input expression from left to right - one character at a time. 
3. If the character is a space, ignore
4. If the character is a number, then append it to an accumulating variable 
   (don't push it to the stack yet)
5. If the character is an operator or a right parenthesis, push the accumulated number 
   to the value stack and reinitialize the accumulator.

    5a. If the current operator is a left parenthesis, push it to the expression stack 
        and continue to the next character in the expression. 

    5b. If the current operator is a right parenthesis, then evaluate the stacks 
        until the first left parenthesis is reached. Push the result back to the value stack 

    5b. If the current operator is of higher precedence than the first item in the operator stack,
        then safely ignore and read further. 

    5c. If the current operator is of lower precedence than the first item in the operator 
        stack (peek view), then evaluate the previous set (two from value stack and one 
        from operator stack) and insert the result into the value stack

    5d. Finally, insert the current operator to the operator stack

Note : the operator level for right parenthesis is kept at ‘0’ to retain operator precedence while the operator level of left paranthesis is kept at ‘3’ (or anything higher than all the operators) to be the least in the precedence. The only purpose of storing the left brackets in the expression stack is for identifying the beginning of the paranthesized sub-expression.

Operator Levels
1
public static final Map OPERATOR_LEVELS= [")":0, "*":1, "/":1, "+":2,"-":2, "(":3]

A Groovy implementation is here :

Comments