描述

150. 逆波兰表达式求值 - 力扣（Leetcode）

分析

很简单，一句话。

遇到数字就怼进去。

遇到运算符就把栈最上面两个做运算然后结果入栈。

如此往复。

实现

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
import java.util.Deque;
import java.util.LinkedList;

//150. 逆波兰表达式求值
public class EvaluateReversePolishNotation150 {
	public static void main(String[] args){
		String[] stringArry = {"2","1","+","3","*"};
		System.out.println("res = " + new Solution().evalRPN(stringArry));
	}
}

class Solution {
    public int evalRPN(String[] tokens) {
    	Deque<Integer> stack = new LinkedList<>();
    	for (String item: tokens) {
    		if (item.equals("+")) {
    			stack.push(stack.pop() + stack.pop());
    		}else if (item.equals("-")) {
    			stack.push(-stack.pop() + stack.pop());
    		}else if (item.equals("*")) {
    			stack.push(stack.pop() * stack.pop());
    		}else if (item.equals("/")) {
    			Integer temp1 = stack.pop();
    			Integer temp2 = stack.pop();
    			stack.push(temp2 / temp1);
    		}else {
    			stack.push(Integer.valueOf(item));
    		}
    	}
    	return stack.pop();
    }
}

总结

其实中缀表达式是给人看的，计算机更加喜欢后缀表达式。