How to Evaluate Postfix and Prefix Expressions written by Nischal Lal Shrestha.
Image of Nischal who is author of the post.

By Nischal Lal Shrestha

On Thu 10 May 2018

How to Evaluate Postfix and Prefix Expressions

How to Evaluate Postfix Expressions

As discussed earlier Computers Prefer Postfix Expressions over Infix Expressions. That is why given an algebraic expression written in infix, the computer first converts the expression into equivalent postfix expression.

Evaluating Postfix Expression make extensive use of stacks as a primary tool. Using stacks, any postfix expression can be evaluated very easily. Every character of the postfix expression is scanned from left to right. If the character encountered is an operand, it is pushed on to the stack. However, if an operator is encountered, then the top two values are popped from the stack and the operator is applied to these values. The result is then pushed on to the stack.

Consider the postfix expression 345x +. As you scan the expression from left to right, you first encounter the operands 3 and 4. Both of them are Operand, So no any operation is possible, so push them in stack until any operator is encountered. The next character 5 is also operator so check for next character Now we see an operator, x. This means that the two most recent operands need to be used in a multiplication operation. By popping the stack twice, we can get the proper operands and then perform the multiplication (in this case getting the result 20). We can now handle this result by placing it back on the stack so that it can be used as an operand for the later operators in the expression. When the final operator is processed(20+3=23), there will be only one value left on the stack. Pop and return it as the result of the expression.

The Algorithm to Evaluate Postfix Expression

  • Add a ")" at the end of the expression.

  • Create an Empty Stack called Operand_Stack.

  • Scanned the character from left to right, call the character Scanned_Character.

  • If the Scanned_Character is

    • Operand, Push it into Operand_Stack.
    • Operator, pop Operand_Stack twice, first pop be A and second pop be B and perform B operator A. Push the result into Operand_Stack.
  • When the Scanned_Character is Null, Display the final answer.

How to EValuate Prefix Expressions

The only difference between postfix and prefix is the position of operator. In prefix expression the operator preceeds the two operands or we can say operator is placed before the operands.

The Algorithm to Evaluate Prefix Expression

  • Create an Empty Stack called Operand Stack.

  • Scanned the character from Right,

  • If the Scanned_Character is

    • Operand, push it on the Operand_Stack
    • Operator, Pop Operand_Stack twice, Apply the operator on the popped operands, push the result into Operand_Stack.
  • When the Scanned_Character is Null, Display the final value of Stack.

Comments