Interview 150
Evaluate Reverse Polish Notation
- Problem
- LC 150
- File
- interview150_LC150EvaluateReversePolishNotation.java
- Path
- pkg5leetcode/interview150/interview150_LC150EvaluateReversePolishNotation.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC150EvaluateReversePolishNotation.java
- Approach
- Stack push numbers; pop and apply operators.
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Evaluate Reverse Polish Notation | LC 1505 * APPROACH: Stack push numbers; pop and apply operators.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class interview150_LC150EvaluateReversePolishNotation {11 static int evalRPN(String[] tokens) {12 Deque<Integer> st = new ArrayDeque<>();13 for (String t : tokens) {14 if (t.length() == 1 && "+-*/".contains(t)) {15 int b = st.pop(), a = st.pop();16 switch (t) {17 case "+": st.push(a + b); break;18 case "-": st.push(a - b); break;19 case "*": st.push(a * b); break;20 default: st.push(a / b);21 }22 } else st.push(Integer.parseInt(t));23 }24 return st.pop();25 }26 27 public static void main(String[] args) {28 check(evalRPN(new String[]{"2", "1", "+", "3", "*"}) == 9, "case1");29 check(evalRPN(new String[]{"4", "13", "5", "/", "+"}) == 6, "case2");30 System.out.println("all tests passed");31 }32 33 static void check(boolean cond, String name) {34 if (!cond) throw new AssertionError("FAILED: " + name);35 System.out.println(" PASS " + name);36 }37}