Home » Interview coding problems/challenges

Postfix Expression Evaluation

Postfix Expression Evaluation: Here, we are going to learn to find the solution of Postfix Expression Evaluation – which has been featured in interview rounds of companies such as Flipkart, Amazon etc. Submitted by Divyansh Jaipuriyar, on May 11, 2020

Problem statement

Given a postfix expression, the task is to evaluate the expression and print the final value. Operators will only include the basic arithmetic operators like *, / , +, and -.

Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.

Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.

Input

The first line of input contains an integer T denoting the number of test cases. The next T lines contain a postfix expression. The expression contains all characters and ^, *, /, +, -.

Output

For each test case, in a new line, evaluate the postfix expression and print the value.

Examples

    Input:	
    T = 1

    5641*+8-
    
    Output: 
    2

    Input:
    T = 1

    123+*8+
    
    Output: 
    13

Solution Approach

Stack Based Approach

We will perform the following operation.

Iterate from left to right, if we encounter operand then push it into the stack otherwise if we encounter operator then we will do the following,

• Pop top two elements from the stack, the first element is the second value of the integer (n2) and the second top element is the first value of the integer(n1) as stack follow last in first out manner.
• Then we will perform the operation represented by the operator like +, -, *, / etc.
• Then push the value calculated after performing the operation back into the stack.
• Finally, the stack contains only one value and that is the evaluated expression.

Pseudo Code

int infixvalue(string str):
{
	stack st; //declare stack.

	int n=str.length();  //string length

	//iterate from left to right
	for(int i=0;i<n;i++)
	{
		// if the character is not operator 
		// then push it into stack.
		if(str[i]!='+' and str[i]!='-' and str[i]!='*' and str[i]!='/')
		    st.push(str[i]-'0')
		else
		{
			int n2=st.top()	//get top of stack for second operand
			st.pop() 	//pop it from the stack.

			int n1=st.top()	//get top of stack for first operand
			st.pop()	//pop it from the stack.

			// if operator is encountered then 
			// perform the following operation.
			if(str[i]=='+') 
			    st.push(n1+n2)
			if(str[i]=='-')
			    st.push(n1-n2)
			if(str[i]=='*')
			    st.push(n1*n2)
			if(str[i]=='/')
			    st.push(n1/n2)
		}
	}
	// finally return the final result 
	// stored in the stack top.
	return st.top()
}

• Time Complexity for above approach in worst case is: O(n)
• Space complexity for above approach is: O(n)

C++ Implementation

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

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test Cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter postfix expression: ";
        string str;
        cin >> str;

        stack<ll> st; //declare stack.
        ll n = str.length(); //string length

        //iterate from left to right
        for (ll i = 0; i < n; i++) {
            // if the character is not operator then push it into stack.
            if (str[i] != '+' and str[i] != '-' and str[i] != '*' and str[i] != '/')
                st.push(str[i] - '0');
            else {
                int n2 = st.top(); //get top of stack for second operand
                st.pop(); //pop it from the stack
                int n1 = st.top(); //get top of stack for first operand
                st.pop(); //pop it from the stack.

                //if operator is encountered then perform the following operation.
                if (str[i] == '+')
                    st.push(n1 + n2);
                if (str[i] == '-')
                    st.push(n1 - n2);
                if (str[i] == '*')
                    st.push(n1 * n2);
                if (str[i] == '/')
                    st.push(n1 / n2);
            }
        }
        cout << "Final value: ";
        cout << st.top() << "\n";
    }
    
    return 0;
}

Output

Enter number of test Cases: 3
Enter postfix expression: 5641*+8-
Final value: 2
Enter postfix expression: 123+*8+
Final value: 13
Enter postfix expression: 562*-7+
Final value: 0