Description
You are given an array of strings tokens that represents an arithmetic expression in a 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 <= 104tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | import operator
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
opt = {
"+": operator.add,
"-": operator.sub,
"*": operator.mul,
"/": operator.truediv,
}
s = []
for token in tokens:
if token in opt:
s.append(int(opt[token](s.pop(-2), s.pop(-1))))
else:
s.append(int(token))
return s[0]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stk = new ArrayDeque<>();
for (String t : tokens) {
if (t.length() > 1 || Character.isDigit(t.charAt(0))) {
stk.push(Integer.parseInt(t));
} else {
int y = stk.pop();
int x = stk.pop();
switch (t) {
case "+":
stk.push(x + y);
break;
case "-":
stk.push(x - y);
break;
case "*":
stk.push(x * y);
break;
default:
stk.push(x / y);
break;
}
}
}
return stk.pop();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for (auto& t : tokens) {
if (t.size() > 1 || isdigit(t[0])) {
stk.push(stoi(t));
} else {
int y = stk.top();
stk.pop();
int x = stk.top();
stk.pop();
if (t[0] == '+')
stk.push(x + y);
else if (t[0] == '-')
stk.push(x - y);
else if (t[0] == '*')
stk.push(x * y);
else
stk.push(x / y);
}
}
return stk.top();
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | func evalRPN(tokens []string) int {
// https://github.com/emirpasic/gods#arraystack
stk := arraystack.New()
for _, token := range tokens {
if len(token) > 1 || token[0] >= '0' && token[0] <= '9' {
num, _ := strconv.Atoi(token)
stk.Push(num)
} else {
y := popInt(stk)
x := popInt(stk)
switch token {
case "+":
stk.Push(x + y)
case "-":
stk.Push(x - y)
case "*":
stk.Push(x * y)
default:
stk.Push(x / y)
}
}
}
return popInt(stk)
}
func popInt(stack *arraystack.Stack) int {
v, _ := stack.Pop()
return v.(int)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | function evalRPN(tokens: string[]): number {
const stack = [];
for (const token of tokens) {
if (/\d/.test(token)) {
stack.push(Number(token));
} else {
const a = stack.pop();
const b = stack.pop();
switch (token) {
case '+':
stack.push(b + a);
break;
case '-':
stack.push(b - a);
break;
case '*':
stack.push(b * a);
break;
case '/':
stack.push(~~(b / a));
break;
}
}
}
return stack[0];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | impl Solution {
pub fn eval_rpn(tokens: Vec<String>) -> i32 {
let mut stack = vec![];
for token in tokens {
match token.parse() {
Ok(num) => stack.push(num),
Err(_) => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(match token.as_str() {
"+" => b + a,
"-" => b - a,
"*" => b * a,
"/" => b / a,
_ => 0,
});
}
}
}
stack[0]
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | using System.Collections.Generic;
public class Solution {
public int EvalRPN(string[] tokens) {
var stack = new Stack<int>();
foreach (var token in tokens)
{
switch (token)
{
case "+":
stack.Push(stack.Pop() + stack.Pop());
break;
case "-":
stack.Push(-stack.Pop() + stack.Pop());
break;
case "*":
stack.Push(stack.Pop() * stack.Pop());
break;
case "/":
var right = stack.Pop();
stack.Push(stack.Pop() / right);
break;
default:
stack.Push(int.Parse(token));
break;
}
}
return stack.Pop();
}
}
|
Solution 2