Postfix Evaluation

Postfix notation (also known as Reverse Polish Notation) is a way to represent an expression, where operators follow their corresponding operands. Evaluating an expression represented as postfix notation can easily be done using the stack data structure.

Scope

• In this article, the concept of the Polish postfix notation (or simply postfix notation) has been discussed briefly along with some examples.
• An algorithm that mainly uses the stack data structure has been shown to evaluate postfix expression.

Takeaways

• Stack data structure is used to efficiently evaluate Postfix Expression.
• Time and Space complexity for evaluating postfix expression using stack are
  • Time complexity – $O(N)$
  • Space complexity – $O(N)$

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

import java.util.*;
public class Main{

    // Function to evaluate the postfix expression
    static int evaluatePostfixExpression(char[] expression) {
        // Defining an stack of integer type.
        Stack<Integer> st=new Stack<>();

        // Traversing in the expression from left 
        // to right. 
        for (int i = 0; i < expression.length; i++){
            char c = expression[i];

            // If 'c' is a digit (operand)
            if (c >= '0' && c <= '9'){
                // Convert 'c' in integer and
                // push it into the stack.
                int temp = (int)(c - '0');
                st.push(temp);
            }
            // Otherwise it is an operator.
            else{
                // Pop element from the stack.
                int op1 = st.pop();
                // Pop another element from the stack. 
                int op2 = st.pop();

                // Use the switch case to deal with
                // the operand accordingly.
                switch(c){
                    case '+':
                        st.push(op2 + op1);
                        break;
                    case '-':
                        st.push(op2 - op1);
                        break;
                    case '*':
                        st.push(op2 * op1);
                        break;    
                    case '/':
                        st.push(op2 / op1);
                        break;
                }
            }
        }

        // Return the element at the top 
        // of the stack.
        return st.peek();
    }

    // Main function
    public static void main(String[] args) {

        // Postfix expression.
        String expression = "23*45+*";

        // Calling function to find the result
        // of the postfix expression.
        System.out.println(
            evaluatePostfixExpression(expression.toCharArray()));
    }

}

Output –

54

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Function to evaluate the postfix expression
int evaluatePostfixExpression(string expression) {
    // Defining an stack of integer type.
    stack<int> st;

    // Traversing in the expression from left 
    // to right. 
    for (int i = 0; i < expression.length(); i++){
        char c = expression[i];

        // If 'c' is a digit (operand)
        if (c >= '0' && c <= '9'){
            // Convert 'c' in integer and
            // push it into the stack.
            int temp = (int)(c - '0');
            st.push(temp);
        }
        // Otherwise it is an operator.
        else{
            // Pop element from the stack.
            int op1 = st.top();
            st.pop();
            // Pop another element from the stack. 
            int op2 = st.top();
            st.pop();

            // Use the switch case to deal with
            // the operand accordingly.
            switch(c){
                case '+':
                    st.push(op2 + op1);
                    break;
                case '-':
                    st.push(op2 - op1);
                    break;
                case '*':
                    st.push(op2 * op1);
                    break;    
                case '/':
                    st.push(op2 / op1);
                    break;
            }
        }
    }

    // Return the element at the top 
    // of the stack.
    return st.top();
}

// Main function
int main() {

    // Postfix expression.
    string expression = "23*45+*";

    // Calling function to find the result
    // of the postfix expression.
    cout <<
        evaluatePostfixExpression(expression) << endl;
}

Output –

54

Python Implementation

# Function to evaluate the postfix expression
def evaluatePostfixExpression(expression):
    # Defining an stack of integer type.
    st = []

    # Traversing in the expression from left 
    # to right. 
    for i in range(len(expression)):
        c = expression[i]

        # If 'c' is a digit (operand)
        if (c >= '0' and c <= '9'):
            # Convert 'c' in integer and
            # push it into the stack.
            temp = int(c)
            st.append(temp)

        # Otherwise it is an operator.
        else:
            # Pop element from the stack.
            op1 = st.pop()
            # Pop another element from the stack. 
            op2 = st.pop()

            # Use the if else ladder to deal with
            # the operand accordingly.
            if (c == '+'):
                st.append(op2 + op1)
            elif (c == '-'):
                st.append(op2 - op1)
            elif (c == '*'):
                st.append(op2 * op1)
            elif (c == '/'):
                st.append(op2 / op1)


    # Return the element at the top 
    # of the stack.
    return st.pop()

# Driver code

# Postfix expression.
expression = "23*45+*"

# Calling function to find the result
# of the postfix expression.
print(evaluatePostfixExpression(expression))

Output –

54

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)$.

A Limitation of the Previous Approach

While implementing the previous approach, we are not taking care of the following two cases –

1. If the given postfix expression itself is invalid.
2. If the operands in expression are of two or more digits.

To handle these cases, we need to make some minor changes in the code which are as follows –

1. If while popping out any element we found that the stack is already empty. It indicates that the given postfix expression is invalid.
2. If the expression contains operands with two or more digits, all of them must be separated by blank space. Therefore, for each element, we need to calculate its value.

Java Implementation

import java.util.*;
public class Main{

    // Function to evaluate the postfix expression
    static int evaluatePostfixExpression(char[] expression) {
        // Defining an stack of integer type.
        Stack<Integer> st=new Stack<>();

        // Traversing in the expression from left 
        // to right. 
        int i = 0;
        while (i < expression.length){
            char c = expression[i];

            // If the current character is space
            // increase the index and continue.
            if (c == ' '){
                i++;
                continue;
            }
            // Else if 'c' is a digit (operand)
            else if (c >= '0' && c <= '9'){
                // Find the value of current operand.
                int val = 0;
                while (expression[i]!=' '){
                    // Obtain the value of current character
                    int temp = (int)(expression[i] - '0');
                    // Increase the val
                    val = 10 * val + temp;

                    // Increase the index;
                    i++;
                }

                // Push val into the stack.
                st.push(val);
            }
            // Otherwise it is an operator.
            else{
                // Checking if the stack contain less than 
                // two elements, which means the expression 
                // is invalid.
                if (st.size() < 2){
                    System.out.println("Given expression is invalid");
                    return Integer.MIN_VALUE;
                }
                // Pop element from the stack.
                int op1 = st.pop();
                // Pop another element from the stack. 
                int op2 = st.pop();

                // Use the switch case to deal with
                // the operand accordingly.
                switch(c){
                    case '+':
                        st.push(op2 + op1);
                        break;
                    case '-':
                        st.push(op2 - op1);
                        break;
                    case '*':
                        st.push(op2 * op1);
                        break;    
                    case '/':
                        st.push(op2 / op1);
                        break;
                }
            }

            // Incrasing the index
            i++;
        }

        // Return the element at the top 
        // of the stack.
        return st.peek();
    }

    // Main function
    public static void main(String[] args) {

        // Postfix expression.
        String expression = "10 22 + 8 / 6 * 5 +";

        // Calling function to find the result
        // of the postfix expression.
        System.out.println(
            evaluatePostfixExpression(expression.toCharArray()));
    }


}

Output –

29

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Function to evaluate the postfix expression
int evaluatePostfixExpression(string expression) {
    // Defining an stack of integer type.
    stack<int> st;

    // Traversing in the expression from left 
    // to right. 
     int i = 0;
    while (i < expression.length()){
        char c = expression[i];
        // If the current character is space
        // increase the index and continue.
        if (c == ' '){
            i++;
            continue;
        }
        // If 'c' is a digit (operand)
        else if (c >= '0' && c <= '9'){
             // Find the value of current operand.
            int val = 0;
            while (expression[i]!=' '){
                // Obtain the value of current character
                int temp = (int)(expression[i] - '0');
                // Increase the val
                val = 10 * val + temp;

                // Increase the index;
                i++;
            }

            // Push val into the stack.
            st.push(val);
        }
        // Otherwise it is an operator.
        else{
             // Checking if the stack contain less than 
            // two elements, which means the expression 
            // is invalid.
            if (st.size() < 2){
                cout << "Given expression is invalid" << endl;
                return INT_MIN;
            }
            // Pop element from the stack.
            int op1 = st.top();
            st.pop();
            // Pop another element from the stack. 
            int op2 = st.top();
            st.pop();

            // Use the switch case to deal with
            // the operand accordingly.
            switch(c){
                case '+':
                    st.push(op2 + op1);
                    break;
                case '-':
                    st.push(op2 - op1);
                    break;
                case '*':
                    st.push(op2 * op1);
                    break;    
                case '/':
                    st.push(op2 / op1);
                    break;
            }

            // Increasing the index
            i++;
        }
    }

    // Return the element at the top 
    // of the stack.
    return st.top();
}

// Main function
int main() {

    // Postfix expression.
    string expression = "10 22 + 8 / 6 * 5 +";

    // Calling function to find the result
    // of the postfix expression.
    cout <<
        evaluatePostfixExpression(expression) << endl;
}

Output –

29

Python Implementation

# Function to evaluate the postfix expression
def evaluatePostfixExpression(expression):
    # Defining an stack of integer type.
    st = []

    # Traversing in the expression from left 
    # to right. 
    i = 0
    while (i < len(expression)):
        c = expression[i]

       # If the current character is space
        # increase the index and continue.
        if (c == ' '):
            i+=1
            continue

        # If 'c' is a digit (operand)
        elif (c >= '0' and c <= '9'):
             # Find the value of current operand.
            val = 0
            while (expression[i]!=' '):
                # Obtain the value of current character
                temp = int(expression[i])
                # Increase the val
                val = 10 * val + temp

                # Increase the index
                i+=1

            # Push val into the stack.
            st.append(val)

        # Otherwise it is an operator.
        else:
            # Checking if the stack contains less than 
            # two elements, which means the expression 
            # is invalid.
            if (len(st) < 2):
                print("Given expression is invalid")
                return -9999999

            # Pop element from the stack.
            op1 = st.pop()
            # Pop another element from the stack. 
            op2 = st.pop()

            # Use the if else ladder to deal with
            # the operand accordingly.
            if (c == '+'):
                st.append(op2 + op1)
            elif (c == '-'):
                st.append(op2 - op1)
            elif (c == '*'):
                st.append(op2 * op1)
            elif (c == '/'):
                st.append(op2 / op1)

            # Increasing the index
            i+=1
    # Return the element at the top 
    # of the stack.
    return st.pop()

# Driver code

# Postfix expression.
expression = "10 22 + 8 / 6 * 5 +"

# Calling function to find the result
# of the postfix expression.
print(evaluatePostfixExpression(expression))

Output –

29

Conclusion

• In postfix notation, the operator appears after the operands.
• It does not require the use of parentheses and therefore it is faster when compared to other notations.
• Stack data structure is used for evaluation of postfix expression efficiently.