Evaluate Reverse Polish Notation
MediumOperators pop their two operands
Push numbers onto a pile; when you see a +−×÷, take the top two, combine them, and push the result back.
The idea
Scan tokens. Push numbers. On an operator, pop the top two numbers, apply it, and push the result. The final stack value is the answer.
2
1
+
3
*
0
1
2
3
4
stack[]
Step 1 of 7. Scan tokens: push numbers; on an operator pop the top two, apply it, and push the result. Values: 2, 1, +, 3, *. stack [].
1/7
Optimal
timeO(n)spaceO(n)
Fold operators over the stack.
1const st = [];2for (const t of tokens) {3 if (isOp(t)) {4 const b = st.pop(), a = st.pop();5 st.push(apply(t, a, b));6 } else st.push(+t);7}8return st[0];Input
- array
- [2, 1, +, 3, *]
Memory
- i
- —
- stack
- []
Output
- stack
- []
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tokens = ["2","1","+","3","*"]
- Output:
- 9
- Explanation:
- (2+1)*3 = 9.
Example 2
- Input:
- tokens = ["4","13","5","/","+"]
- Output:
- 6
- Explanation:
- 4 + (13/5) = 6.
Example 3
- Input:
- tokens = ["5","1","2","+","4","*","+","3","-"]
- Output:
- 14
- Explanation:
- Works out to 14.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.