Solution: Evaluate Reverse Polish Notation
Tags: algorithms, javascript, java, python
Published: 2021-05-25 09:11:45

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/evaluate-reverse-polish-notation/discuss/1229403).*

---

#### [Leetcode Problem #150 (*Medium*): Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
>
Valid operators are `+`, `-`, `*`, and `/`. Each operand may be an integer or another expression.
>
**Note** that division between two integers should truncate toward zero.
>
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

---

#### ***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 = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output:|22
Explanation:|((10 * (6 / ((9 + 3) * -11))) + 17) + 5<br>= ((10 * (6 / (12 * -11))) + 17) + 5<br>= ((10 * (6 / -132)) + 17) + 5<br>= ((10 * 0) + 17) + 5<br>= (0 + 17) + 5<br>= 17 + 5<br>= 22

---

#### ***Constraints:***
>
 - `1 <= tokens.length <= 10^4`
 - `tokens[i]` is either an operator: `"+"`, `"-"`, `"*"`, or `"/"`, or an integer in the range `[-200, 200]`.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

**Reverse Polish Notation** was designed specifically to make computing easier with the more efficient use of a **stack**. So we can use a **stack** here to store numbers until they're used, and then each operand will use the top two values of the **stack**.

Since the order of the numbers is still important for subtraction and division, we'll have to make sure that the two numbers are processed in their original order, which is the opposite order of the **stack**.

After each successful operation, the result should be pushed back onto the **stack** until it's used. After iteration is complete, the remaining value in the **stack** will be our answer, so we should **return stack[0]**.

 - _**Time Complexity: O(N)** where **N** is the length of **tokens**_
 - _**Space Complexity: O(N)** for the length of the **stack**, up to **N / 2 + 1** values_
     - _or **O(1)** with the use of an **in-place stack**_

---

#### ***Implementation:***

Javascript object values can be functions, so we can store the operations directly in an evaluate object as **lambda** functions.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
let a, b
const evaluate = {"+": ()=>a+b, "-": ()=>a-b, "*": ()=>a*b, "/": ()=>~~(a/b)}

var evalRPN = function(tokens) {
    let stack = []
    for (let t of tokens) {
        if (evaluate[t]) {
            b = stack.pop(), a = stack.pop()
            stack.push(evaluate[t]())
        } else stack.push(~~t)
    }
    return stack[0]
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for t in tokens:
            if t not in {"+", "-", "*", "/"}:
                stack.append(int(t))
            else:
                b, a = stack.pop(), stack.pop()
                if t == "+": stack.append(a + b)
                elif t == "-": stack.append(a - b)
                elif t == "*": stack.append(a * b)
                else: stack.append(trunc(a / b))
        return stack[0]
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    private Set<String> ops = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String t : tokens) {
            if (!ops.contains(t)) stack.push(Integer.parseInt(t));
            else {
                int b = stack.pop(), a = stack.pop();
                if (t.equals("+")) stack.push(a + b);
                else if (t.equals("-")) stack.push(a - b);
                else if (t.equals("*")) stack.push(a * b);
                else stack.push(a / b);
            }
        }
        return stack.pop();
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
static unordered_set<string> ops({"+", "-", "*", "/"});

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stack;
        for (auto t : tokens) {
            if (ops.find(t) == ops.end()) stack.push(stoi(t));
            else {
                int b = stack.top(); stack.pop();
                int a = stack.top(); stack.pop();
                if (t == "+") stack.push(a + b);
                else if (t == "-") stack.push(a - b);
                else if (t == "*") stack.push(a * b);
                else stack.push(a / b);
            }
        }
        return stack.top();
    }
};
```