题目要求
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
计算后缀表达式。我们一般看到的数学表达式就是中缀表达式，也就是将符号放在两个数字之间。后缀表达式也就是将运算符放在相应数字的后面。后缀表达式相当于树中的后序遍历。
思路一：栈
当我们遇到数字时就将数字压入栈中，如果遇到操作符就将栈顶的两个数字弹出，并将其根据操作符计算结构并重新压入栈中。栈中剩下的最后的值就是我们的结果。
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
| public int (String[] tokens) {
LinkedList<Integer> stack = new LinkedList<Integer>();
for(String token : tokens){
if(token.equals("+")){
int operand1 = stack.pop();
int operand2 = stack.pop();
stack.push(operand2 + operand1);
}else if(token.equals("-")){
int operand1 = stack.pop();
int operand2 = stack.pop();
stack.push(operand2 - operand1);
}else if(token.equals("*")){
int operand1 = stack.pop();
int operand2 = stack.pop();
stack.push(operand2 * operand1);
}else if(token.equals("/")){
int operand1 = stack.pop();
int operand2 = stack.pop();
stack.push(operand2 / operand1);
}else{
stack.push(Integer.valueOf(token));
}
}
return stack.pop();
}
|
思路二：递归
从后缀表达式的末尾开始递归获取操作符对应的两个操作符。通过index获得对应位置的操作符。如果对应的还是操作符，则继续递归往前计算。
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
| int index;
public int evalRPN2(String[] tokens){
index = tokens.length-1;
return recursive(tokens);
}
public int recursive(String[] tokens){
String current = tokens[index--];
int operand1, operand2;
switch(current){
case "+" :
operand1 = recursive(tokens);
operand2 = recursive(tokens);
return operand1 + operand2;
case "-" :
operand1 = recursive(tokens);
operand2 = recursive(tokens);
return operand2 - operand1;
case "*" :
operand1 = recursive(tokens);
operand2 = recursive(tokens);
return operand2 * operand1;
case "/" :
operand1 = recursive(tokens);
operand2 = recursive(tokens);
return operand2 / operand1;
default:
return Integer.valueOf(current);
}
}
|
