1. 关于 Reverse Polish Notation
定义见网络。
2. 题目内容
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples:
[“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/“, “+”] -> (4 + (13 / 5)) -> 6
3. 解题思路
对于一个合法的字符数组，依次扫描该字符数组：
- 如果该字符是”+”,”-“,”*”,”/“中的任意一个，则将其放入栈中；
- 如果该字符是操作符，则从栈中取出两个操作数按照顺序进行运算；
- 直到扫描完毕，取出栈中的最后一个数，即为结果。
4. 代码实现
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
31
32
33
34
35
36
| public int evalRPN(String[] tokens) {
List<String> operators = new ArrayList<String>() {{
add("+");
add("-");
add("*");
add("/");
}};
Stack<Integer> tempValue = new Stack<>();
int number1;
int number2;
int result = 0;
for (String token : tokens) {
if (!operators.contains(token)) {
tempValue.push((Integer.valueOf(token)));
} else {
number1 = tempValue.pop();
number2 = tempValue.pop();
switch (token) {
case "+":
result = number2 + number1;
break;
case "-":
result = number2 - number1;
break;
case "*":
result = number2 * number1;
break;
case "/":
result = number2 / number1;
break;
}
tempValue.push(result);
}
}
return tempValue.pop();
}
|