Converting Infix expression to Postfix and evaluating it
Let infix be the input expression, postfix the output expression and opstack operator stack.
If infix begins with -, set firstMinus boolean flag to true and set infix scanning index(i) to 1, otherwise set firstMinus to false and ii to 0.
Now start scanning infix from i character by character (c).
- If c is operand, while this is true append it to postfix, and set c to infix at i = i+1.
If firstMinus is true and infix character at 1 is not left bracket append @ (sign for unary minus) to postfix. - If c is operator:
- If opstack is empty, just push c on opstack
- If c is left bracket, push it on opstack
- If c is right bracket, pop every opstack element while opstack top element is not left bracket and append it to postfix, and after pop the left bracket (top opstack element). If firstMinus is true, append @ to postfix.
- If c is minus and character before c was left bracket, append @ to postfix.
- If c is any other operator, while opstack top operator has higher or same priority, append them to postfix and pop from opstack. Now push c on opstack.
- If opstack is not empty, append its elements to postfix and pop them.
Now return postfix.
Let postfix be the input expression, operandStack be the operand Stack.
Start scanning postfix character by character (c).
- If c is operand, push it on opstack.
- If c is operator:
- If c is @(unary minus), pop operandStack top element and push its negative.
- If c is any other operator (+, -, * or /), pop two operands from operandStack, do the operation indicated by c and push the result on operandStack.
Now return operandStack top element (the result).