逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）
定义一个表达式E的后缀形式可以如下定义：
（1）如果E是一个变量或常量，则E的后缀式是E本身。
（2）如果E是E1 op E2形式的表达式，这里op是如何二元操作符，则E的后缀式为E1’E2’ op，这里E1’和E2’分别为E1和E2的后缀式。
（3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
(a+b)*c-(a+b)/e的后缀表达式为：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
为什么要转换成后缀表达式 实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。
算法实现 判断是否为数字 static boolean isOperator(char expression) { return expression < 48 || expression > 57; } 判断运算符优先级 static int getPeriod(int character) { if (character == '*' || character == '/') { return 1; } if (character == '+' || character == '-') { return 0; } return 0; } 表达式转成List static List<String> strToInfixExpression(String expression) { String num; char cur = ' '; List<String> list = new ArrayList<>(); for (int i = 0; i < expression.length(); i++) { cur = expression.charAt(i); if (isOperator(cur)) { list.add("" + cur); continue; } num = "" + cur; if (i + 1 < expression.length() && isOperator(expression.charAt(i + 1))) { list.add("" + cur); continue; } while (i + 1 < expression.length() && !isOperator(expression.charAt(i + 1))) { num += "" + expression.charAt(i + 1); i++; } list.add(num); } return list; } 转换为逆波兰式的集合 static List<String> change2ReversePolish(String str) { if (str == null || str.length() == 0) { return null; } Stack<String> stack1 = new Stack<>(); List<String> reversePokish = new ArrayList<>(); //拆分原有字符 List<String> characters = strToInfixExpression(str); for (String character : characters) { //匹配数字 if (character.matches("\d+")) { reversePokish.add(character); continue; } //为"("直接入栈 if (character.equals("(")) { stack1.push(character); continue; } //为")"，直接把符号栈的从栈顶到第一个"（"的操作符放到结果集合 if (character.equals(")")) { while (!"(".equals(stack1.peek())) { reversePokish.add(stack1.pop()); } stack1.pop(); continue; } //如果当前字符小于符号占中的优先级，符号栈出栈当前到结果直到栈顶的优先级不大于当前 while (!stack1.isEmpty() && getPeriod(stack1.peek().charAt(0)) > getPeriod(character.charAt(0))) { reversePokish.add(stack1.pop()); } //当前字符入栈 stack1.push(character); } while (!stack1.isEmpty()) { reversePokish.add(stack1.pop()); } return reversePokish; }