Evaluate Reverse Polish Notation

stack

math

# Evaluate Reverse Polish Notation

## Difficulty
Medium

## Tags
`stack`, `math`

## Problem Statement
Evaluate the value of an arithmetic expression in Reverse Polish Notation (Postfix notation).

Valid operators are `+`, `-`, `*`, `/`. Each operand may be an integer or another expression.

**Note:**
- Division between two integers truncates toward zero.
- The given expression is always valid.
- No division by zero will occur.

## Constraints
- 1 ≤ tokens.length ≤ 10⁴
- tokens[i] is either an operator or an integer in range [-200, 200]

## Signatures
### Python
```python
def eval_rpn(tokens: List[str]) -> int:
    pass
```

### Java
```java
public class Solution {
    public int eval_rpn(List<String> tokens) {
        return null;
    }
}
```

### Csharp
```csharp
public class Solution {
    public int eval_rpn(IList<string> tokens) {
        throw new NotImplementedException();
    }
}
```

### Cpp
```cpp
class Solution {
public:
    int eval_rpn(vector<string> tokens) {
        
    }
};
```

### C
```c
int eval_rpn(vector<char*> tokens) {
    
}
```

### Ruby
```ruby
def eval_rpn(tokens)
    
end
```

### Perl
```perl
sub eval_rpn {
    my ($self, @args) = @_;
    
}
```

### Scala
```scala
object Solution {
    def eval_rpn(tokens: List[String]): Int = {
        
    }
}
```

### Haskell
```haskell
eval_rpn :: ... -> ...
eval_rpn args = undefined
```

### Clojure
```clojure
(defn eval_rpn [tokens]
  )
```

### Scheme
```scheme
(define (eval_rpn tokens)
  )
```

## 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)) = 4 + 2 = 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
= 22

## Hints
1. Use a stack to store operands.
2. When you encounter a number, push it onto the stack.
3. When you encounter an operator, pop two numbers, apply the operator, push the result.
4. Be careful with order: for subtraction and division, the second popped value is the left operand.
5. For Python, use `int(a / b)` to truncate toward zero (not `//`).

Please log in to view the solution editor and submit code.