Postfix Evaluation

Introduction

Postfix notation is one of the few ways to represent algebraic expressions. It is used in computers because it is faster than other types of notations (such as infix notation) as parentheses are not required to represent them.

As the name suggests, in the postfix expression operators follow their operands. Therefore, the process of postfix evaluation is quite different than solving the infix notation (normal notation used in daily use).

Input-Output

Input - A string consisting of numeric values along with operator symbols (*, /, +, -, etc) is given as the input. Output - The result obtained by solving the given input is required to be printed.

Examples of Postfix Expression Evaluation

Example 1 -

Input - $2 3 * 4 5 + *$

Output - $54$

Example 2 -

Input - $5 2 3 * *$

Output - $30$

Algorithm of Postfix Expression Evaluation

As we have discussed earlier, the operators follow their operands in the postfix expression. Hence, for the postfix evaluation we will use the Stack data structure.

We know that the stack data structure works on the last in first out (LIFO) principle. Therefore, previously encountered operands can easily be accessed using the stack.

The algorithm for evaluation of postfix expression is as follows -

• Create a stack that holds integer type data to store the operands of the given postfix expression. Let it be st.
• Iterate over the string from left to right and do the following -
  • If the current element is an operand, push it into the stack.
  • Otherwise, if the current element is an operator (say /)do the following -
    • Pop an element from st, let it be op1.
    • Pop another element from st, let it be op2.
    • Computer the result of op2 / op1, and push it into the stack. Note the order $i.e.$ op2 / op1 should not be changed otherwise it will affect the final result in some cases.
• At last, st will consist of a single element $i.e.$ the result after evaluating the postfix expression.

How to Evaluate a Postfix Expression Using Stack?

We have discussed the algorithm that uses the stack for postfix evaluation. Now we dry run the above algorithm to make the concept crystal clear.

Let the the postfix expression be "10 22 + 8 / 6 * 5 +". Now, proceeding as per the algorithm -

1. Create a stack (say st).

2. Now since the first element is an operand, so we will push it in the stack $i.e.$ st.push(10). After which stack looks like -

   st
   10

3. Now we traverse further in the postfix expression and found that the next element is again an operand. So, we will push it into the stack, after which the stack will look like -

   st
   22
   10

4. The next element of the expression is an operator (+ operator) so we will do the following -

   1. Pop an element (say op1) from the stack. Here op1 = 22.
   2. Pop another element (say op2) from the stack. Here op2 = 10.
   3. Now, we will compute op2 + op1 which is 32, and push it into the stack. After this step stack will look like -

   st
   32

5. On traversing further in the expression string, we found next element is an operand. So we will push it into the stack. Upon doing this, the stack will look like -

   st
   8
   32

6. The next element is the / operator, so we will do the following -

   1. Pop an element (say op1) from the stack. Here op1 = 8.
   2. Pop another element (say op2) from the stack. Here op2 = 32.
   3. Now, we will compute op2 / op1 which is 4, and push it into the stack. After this step stack will look like -

   st
   4

7. The next element is an operand, hence pushing it in the stack. After this step stack will look like -

   st
   6
   4

8. The next element is the * operator, hence we need to perform the following steps -

   1. Pop an element (say op1) from the stack. Here op1 = 6.
   2. Pop another element (say op2) from the stack. Here op2 = 4.
   3. Now, we will compute op2 * op1 which is 24, and push it into the stack. After this step stack will look like -

   st
   24

9. The next operator is an operand, hence pushing it into the stack. Upon doing which stack will look like -

   st
   5
   24

10. The last element is the + operator. Hence it is required to do the following steps -

    1. Pop an element (say op1) from the stack. Here op1 = 5.
    2. Pop another element (say op2) from the stack. Here op2 = 24.
    3. Now, we will compute op2 + op1 which is 29, and push it into the stack. After this step stack will look like -

    st
    29

11. Now, we have traversed the given postfix expression, and hence as per the algorithm the only element remaining in the stack i.e. 29 is the result we get on evaluating the postfix expression.

Implementation of the Algorithm

Java Implementation

Output -

C++ Implementation

Output -

Python Implementation

Output -

Complexity Analysis

Time Complexity - Since, we are traversing the expression once, which costs $O(n)$ time. Therefore the overall time complexity of postfix evaluation is $O(n)$.

Space Complexity - The maximum number of elements in our stack can reach up to $O(n)$ in the worst case. The space complexity is $O(n)$. :::