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