Q:

# 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)