前言
今天刷题遇到了逆波兰表达式，死亡的记忆突然开始攻击我，好嘛，既然根基不牢，那么就一次性给他搞明白了！
一、算术表达式求值
算术表达式又叫中缀表达式，如果直接给出一个中缀表达式让我们求值，当然并不是不可以，只不过说会比较麻烦。就拿四则运算来说我们既要考虑“括号”又要考虑运算符的“优先级”。当然对于括号问题和优先级问题我们借助递归和栈都能够解决：
public int solve (String s) { // write code here s = 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 统计括号对数直到变量为 0 int 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.然后保存新的运算符到 sign if (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(); }
四、拓展思考
有前缀表达式吗？当然是有的，前缀表达式就是所谓的波兰表达式，它的转换与求值和后缀表达式不同：后缀表达式的转换和运求值扫描顺序都是从左往右，而前缀表达式的转换和求值是从右向左，其他规则一致。
