Algorithm to evaluate an infix expression

by

Generally arithmetic expressions are written in infix expression where the operator is written between the operands.

Point to consider

  1. Permitted operands: A, B, C, D means any real number is permitted.
  2. Permitted operators: +,-, *, /, ^(exponentiation)
  3. Blanks are permitted in the expression
  4. Parenthesis are permitted

Suppose given infix expression is

A+B*C-D

where A,B,C,D are operands and +,*,- are operators.

To solve the above infix expression we will use two stack

Operand Stack : This stack will hold operands.

Operator Stack : This stack will hold operators.

Algorithm to evaluate infix expression

Until the end of the expression is reached, get one character and perform only one of the steps (1) through (5):

  1. If the character is an operand, push it onto the operand stack.
  2. If the character is “(“, then push it onto the operator stack.
  3. If the character is “)”, then “process” as explained above until the corresponding “(” is encountered in the operator stack. At this stage POP the operator stack and ignore “(.”
  4. If we encounter an operator
    • If the operator stack is empty then push the operator onto the operator stack.
    • If the operator stack is not empty and the operator’s precedence is greater than the precedence of the stack top of the operator stack, then push the character onto the operator stack.
    • If the operator stack is not empty and the character’s precedence is lower than the precedence of the stack top of operator stack then we pop the operator with high precedence, and two values from the value stack, apply the operator to the values and store the result in the value stack. And, push the current iterated operator in the operator stack.
  5. Once we have iterated the entire expression, we pop one operator from the operator stack and two values from the value operator and apply the operator to the values, store the result in the value stack, and keep on repeating this, until we have just a single value left in the value stack.
  6. The last value in the value stack will be the result.

[wpusb]