Algorithm to evaluate a postfix expression

A postfix expression is a mathematical expression in which the operator comes after the operands. For example, 2 3 + means 2 + 3. Unlike normal expressions, postfix does not need parentheses to define the order of operations.

To evaluate a postfix expression, we use a stack. We read the expression from left to right, push numbers (operands) onto the stack, and when we encounter an operator like +, -, *, or /, we pop the required numbers from the stack, perform the operation, and push the result back. At the end, the stack contains the final answer.

What is Postfix expression ?

A postfix expression is a way of writing mathematical expressions where the operator comes after the operands. For example, instead of writing A + B (infix form), we write it as A B + in postfix form.

Postfix expressions are easy for computers to understand and evaluate because they don’t need brackets or operator precedence rules. The order of operations is clear just by the position of the operator. For example, the infix expression A + B * C becomes A B C * + in postfix form, which means multiply B and C first, then add A to the result.

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

Prefix and Postfix expressions can be evaluated faster in comparison to an infix expression because we don’t need to process any brackets or follow the operator precedence rule. In postfix and prefix expressions whichever operator comes before will be evaluated first, irrespective of its priority. Also, there are no brackets in these expressions. As long as we can guarantee that a valid prefix or postfix expression is used, it can be evaluated with correctness.

Algorithm to evaluate postfix expression

Step 1: If the character is an operand, push it onto the stack.

Step 2: If the character is an operator, pop two elements from the stack. Perform the operation on these two elements based on the operator, and then push the result back onto the stack.

Step 3: Repeat Steps 1 and 2 for each character until the end of the expression is reached.

Step 4: After processing the entire expression, the final result will be stored at the top of the stack. Return this value as the output.

Step 5: End.

Example for postfix expression

Expression: 2 3 + 4 * 5 –

We will evaluate it using a stack.

Step 1: Understand the Expression

• Postfix means operator comes after operands.
• The expression in infix form is:

((2 + 3) * 4) - 5

Step 2: Evaluate Using a Stack (Left to Right)

We read the expression from left to right: 2, 3, +, 4, *, 5, -.

1. Push operands onto the stack:
   • Push 2 → Stack: [2]
   • Push 3 → Stack: [2, 3]
2. Encounter operator +:
   • Pop two operands: 2 and 3
   • Add: 2 + 3 = 5
   • Push result → Stack: [5]
3. Next operand 4:
   • Push 4 → Stack: [5, 4]
4. Next operator *:
   • Pop two operands: 5 and 4
   • Multiply: 5 * 4 = 20
   • Push result → Stack: [20]
5. Next operand 5:
   • Push 5 → Stack: [20, 5]
6. Next operator -:
   • Pop two operands: 20 and 5
   • Subtract: 20 - 5 = 15
   • Push result → Stack: [15]

Step 3: Final Result

• Only one value remains in the stack: 15
• So, the result of 2 3 + 4 * 5 – is 15

Complexity of Postfix evaluation

The Postfix evaluation algorithm has linear complexity O(N). Since we scan the expression once and perform push and pop operations which take constant time.