> [!META]- Inline Metadata
> [tags:: #career #leetcode/stacks #concepts/programming/stacks]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/evaluate-reverse-polish-notation/]
> [up:: [[Leetcode MOC]]]
> [!NOTE]
> Received this (and failed) when interviewing for ICON.
## Problem
You are given an array of strings `tokens` that represents an arithmetic expression in a [Reverse Polish Notation](http://en.wikipedia.org/wiki/Reverse_Polish_notation).
Evaluate the expression. Return _an integer that represents the value of the expression_.
**Note** that:
- The valid operators are `'+'`, `'-'`, `'*'`, and `'/'`.
- Each operand may be an integer or another expression.
- The division between two integers always **truncates toward zero**.
- There will not be any division by zero.
- The input represents a valid arithmetic expression in a reverse polish notation.
- The answer and all the intermediate calculations can be represented in a **32-bit** integer.
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
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
```
Constraints:
1 <= tokens.length <= 10^4
tokens[i] is either an operator: `"+"`, `"-"`, `"*"`, or `"/"`, or an integer in the range [-200, 200].
## Solution
### Mine
#### Python
```python
from decimal import Decimal
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
op = {
"+": lambda x, y: x + y,
"-": lambda x, y: x - y,
"*": lambda x, y: x * y,
"/": lambda x, y: int(Decimal(x) // Decimal(y)), # truncate to 0
}
operand_stack = []
for token in tokens:
try:
operand_stack.append(int(token))
except ValueError:
right = operand_stack.pop()
left = operand_stack.pop()
operand_stack.append(op[token](left, right))
return operand_stack[0]
```
#### Rust
### LC's
## Things I Learned
### Neetcode Video Notes
For RPN, example `2, 1, +, 3, *`. Read left to right, when you hit an operator you apply it to the previous operands.
`2, 1, +, 3, *` -> `3, 3 *` -> `9`
This would've been so much easier if the interviewer just explained RPN correctly.
Didn't watch the rest.
## Scratchpad