栈的最后表演：逆波兰表达式求值

前言

今天刷题遇到了逆波兰表达式，死亡的记忆突然开始攻击我，好嘛，既然根基不牢，那么就一次性给他搞明白了！

一、算术表达式求值

算术表达式又叫中缀表达式，如果直接给出一个中缀表达式让我们求值，当然并不是不可以，只不过说会比较麻烦。就拿四则运算来说我们既要考虑“括号”又要考虑运算符的“优先级”。当然对于括号问题和优先级问题我们借助递归和栈都能够解决：

public int solve (String s) {// write code heres = s.trim();Deque<Integer> stack = new ArrayDeque<>();// 初始化字符、符号int number = 0;char sign = '+';char[] charArray = s.toCharArray();for (int i = 0; i < charArray.length; i ++) {// 获取当前字符char c = s.charAt(i);if (c == ' ') {// 空字符是无效字符直接跳过continue;}if (Character.isDigit(c)) {// 遇到数字时继续遍历求这个完整的数字的值，保存到 number 中(如“10”)number = number * 10 + c - '0';}if (c == '(') {// 遇到左括号时递归求这个括号里面的表达式的值// 先遍历找到对应的右括号，因为可能里面还嵌有多对括号，// 使用一个变量 counterPartition 统计括号对数直到变量为 0int j = i + 1;int counterPartition = 1;while (counterPartition > 0) {if (charArray[j] == '(') {counterPartition++;}if (charArray[j] == ')') {counterPartition--;}j++;}number = solve(s.substring(i + 1, j - 1));i = j - 1;}if (!Character.isDigit(c) || i == charArray.length) {// 遇到符号字符时，包括遍历到末尾时都需要：// 1.根据上一个运算符并把计算结果 push 进栈// 2.然后保存新的运算符到 signif (sign == '+') {stack.push(number);} else if (sign == '-') {stack.push(-1 * number);} else if (sign == '*') {stack.push(stack.pop() * number);} else if (sign == '/') {stack.push(stack.pop() / number);}number = 0;sign = c;}}// 用栈保存各部分计算的和，最后把栈中的结果求和即可int ans = 0;while (!stack.isEmpty()) {ans += stack.pop();}return ans;
}

虽然我们上面使用栈也可以解决算术(中缀)表达式求值的问题，但是整个过程肉眼可见的麻烦，那么能不能更简单有效的处理表达式求值呢？逆波兰表达式应运而生。

二、中缀表达式转逆波兰表达式

逆波兰表达式是一种不需要括号的后缀表达法，它的特点就是所有的符号都是在要运算数的后面出现。比如："9+(3-1)*3+10/2" 转换成逆波兰表达式就成了：“9 3 1- 3*+ 10 2 /+”。显然，这里没有括号，对于习惯了算术(中缀)表达式的我们来说，这样的表述是很难受的。不过我们不喜欢，有机器喜欢，比如我们聪明的计算机。

在具体介绍如何使用逆波兰表达式求值之前，你肯定跟我一样好奇：算术表达式和逆波兰表达式之间是如何转换的？下面我们就来进行解密。

1、转换规则

从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

2、代码实现：

    // 中缀表达式转逆波兰表达式// 定义运算符优先级private static final Map<Character, Integer> precedence = new HashMap<>();static {precedence.put('+', 1);precedence.put('-', 1);precedence.put('*', 2);precedence.put('/', 2);precedence.put('^', 3);}public static String infixToRPN(String infix) {StringBuilder output = new StringBuilder(); // 存放输出结果Stack<Character> stack = new Stack<>(); // 运算符栈for (char c : infix.toCharArray()) {if (Character.isDigit(c)) { // 如果是数字，直接输出output.append(c);} else if (c == '(') { // 如果是左括号，入栈stack.push(c);} else if (c == ')') { // 如果是右括号，将左括号之前的运算符全部输出while (!stack.isEmpty() && stack.peek() != '(') {output.append(stack.pop());}if (!stack.isEmpty()) {stack.pop(); // 弹出左括号}} else { // 如果是运算符while (!stack.isEmpty() && stack.peek() != '(' && precedence.get(c) <= precedence.get(stack.peek())) {output.append(stack.pop()); // 将优先级高于等于当前运算符的运算符全部输出}stack.push(c);}}while (!stack.isEmpty()) { // 将剩余的运算符全部输出output.append(stack.pop());}return output.toString();}

三、逆波兰表达式求值

1、求值规则

规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，直到最终获得结果。

2、代码实现

public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String x:tokens) {if (!x.equals("+") && !x.equals("-") && !x.equals("*") && !x.equals("/")) {stack.push(Integer.parseInt(x));} else {int num1 = stack.pop();int num2 = stack.pop();switch (x) {case "+":stack.push(num2+num1);break;case "-":stack.push(num2-num1);break;case "*":stack.push(num2*num1);break;case "/":stack.push(num2/num1);break;}}}return stack.pop();}