Practice › Stack & Queue
Evaluate Postfix Expression
Medium · Stack & Queue · Asked at Amazon, Microsoft, LinkedIn, TCS, Infosys
Evaluate an expression in postfix (Reverse Polish) notation. Tokens are integers and + - * /. Division truncates toward zero.
Input
One line of space-separated tokens.
Output
The value of the expression.
Constraints
- 1 ≤ tokens ≤ 10^4
- Every intermediate value fits in a 32-bit integer
- No division by zero
Push numbers on a stack; for an operator pop b, then a, and push a op b.
Example 1
Input
2 1 + 3 *
Output
9
Example 2
Input
4 13 5 / +
Output
6
Hints
- Numbers wait on a stack until an operator needs them.
- For an operator, pop b first and then a (order matters for − and /), and push a op b. Watch out: "-3" is a number, not an operator.
Approach
Read tokens one by one. A token is an operator only if it is exactly one of + - * /. Anything else, such as "-3", is a number and gets pushed. For an operator, pop the right operand b, then the left operand a, and push the result. Division must truncate toward zero: C++/Java / already does, but Python's // floors, so the Python version divides the absolute values and fixes the sign. The single value left at the end is the answer.
Complexity: O(tokens) time · O(tokens) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<long long> st;
string tok;
while (cin >> tok) {
if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
long long b = st.back(); st.pop_back();
long long a = st.back(); st.pop_back();
if (tok == "+") st.push_back(a + b);
else if (tok == "-") st.push_back(a - b);
else if (tok == "*") st.push_back(a * b);
else st.push_back(a / b); // C++ division truncates toward zero
} else {
st.push_back(stoll(tok));
}
}
cout << st.back() << "\n";
return 0;
}Python solution
stack = []
for tok in input().split():
if tok in ("+", "-", "*", "/"):
b = stack.pop()
a = stack.pop()
if tok == "+":
stack.append(a + b)
elif tok == "-":
stack.append(a - b)
elif tok == "*":
stack.append(a * b)
else:
q = abs(a) // abs(b) # truncate toward zero, like C++/Java
stack.append(q if (a < 0) == (b < 0) else -q)
else:
stack.append(int(tok))
print(stack[-1])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayDeque<Long> st = new ArrayDeque<>();
while (sc.hasNext()) {
String tok = sc.next();
if (tok.equals("+") || tok.equals("-") || tok.equals("*") || tok.equals("/")) {
long b = st.pop(), a = st.pop();
switch (tok) {
case "+": st.push(a + b); break;
case "-": st.push(a - b); break;
case "*": st.push(a * b); break;
default: st.push(a / b); // Java division truncates toward zero
}
} else {
st.push(Long.parseLong(tok));
}
}
System.out.println(st.peek());
}
}Solve Evaluate Postfix Expression online · All practice problems