Q:

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 -

0

Postfix Expression Evaluation

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

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
Find the largest rectangular area possible in a gi... >>
<< Given a string of balanced expression, find if it ...