03-Evaluate-Reverse-Polish-Notation.md

Evaluate Reverse Polish Notation

Problem Link

https://leetcode.com/problems/evaluate-reverse-polish-notation/

---

Pattern

• Stack
• Array

---

Approach

Push operands on a stack and apply operators when they appear.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            switch (token) {
                case "+": stack.push(stack.pop() + stack.pop()); break;
                case "-": {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a - b);
                    break;
                }
                case "*": stack.push(stack.pop() * stack.pop()); break;
                case "/": {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a / b);
                    break;
                }
                default: stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}