/* 中缀表达式转成后缀表达式 "12+((22+31)*4)-5" ==> 12 22 31 + 4 * + 5 - 第一步，将中缀表达式转成中缀字符串list,方便遍历 [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5] 第二步，将中缀字符串list转成后缀表达式对应的list [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5] -> [12, 22, 31, +, 4, *, +, 5, -] 具体步骤： 初始化两个栈，s1运算符栈，s2存储中间结果的栈 遍历中缀表达式字符串list 若是数字，直接入栈s2; 若是"(",直接入栈s1; 若是")",依次弹出符号栈s1的栈顶运算符，并入栈s2，直到遇到左括号，将左括号再出栈，把一对括号消除掉; 若是操作符(加减乘除),比较它和s1栈顶操作符的优先级大小: a.若s1为空，或者栈顶运算符为"(",则直接将此运算符入栈； b.否则，若其优先级比栈顶运算符的优先级高，也将此运算符入栈; c.否则，将s1栈顶的运算符弹出，并入栈到s2中，继续从a循环。 遍历结束后，把s1中剩余的运算符依次弹出，并加入s2。 依次弹出s2中的元素，结果的逆序即为中缀表达式对应的后缀表达式。 */public class InfixToPostfixDemo { // 第1步. 将中缀表达式转成中缀字符串列表，方便遍历。 // "12+((22+31)*4)-5" ==> [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5] public List<String> toInfixList(String exp) { List<String> res = new ArrayList<>(); int i = 0; // 保存遍历过程中产生的数字，连续的数字字符拼接成一个数 StringBuilder sb = new StringBuilder(); while (i < exp.length()) { if (!Character.isDigit(exp.charAt(i))) { res.add(exp.charAt(i) + ""); // 如果当前字符不是数字，直接加入结果 i++; } else { sb.delete(0, sb.length());// 先清除 while (i < exp.length() && Character.isDigit(exp.charAt(i))) { sb.append(exp.charAt(i)); i++; } res.add(sb.toString()); } } return res; } // 第2步 将中缀表达式字符串列表，转成后缀表达式字符串列表. // [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5] -> [12, 22, 31, +, 4, *, +, 5, -] public List<String> toPostList(List<String> list) { Stack<String> s1 = new Stack<>(); // 符号栈 // 存储中间结果 List<String> s2 = new ArrayList<>(); // 在整个转换过程中，没有pop操作，在后面还要逆序输出，所以用list代替栈 for (String item : list) { if (item.matches("\\d+")) s2.add(item); // 如果是数字，加入s2 else if (item.equals("(")) s1.push(item); // 如果是左括号，入栈s1 else if (item.equals(")")) { // 如果是右括号，则依次弹出符号栈s1栈顶的运算符，并压入s2，直到遇到左括号位置，将这一对括号消除掉 while (!s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop(); // 丢弃左括号，继续循环，也就消除了一对括号 } else { // 此时，遇到的是加减乘除运算符 // 当前操作符优先级<=s1的栈顶运算符的优先级，则将s1的运算符弹出，并加入到s2中 while (!s1.empty() && priority(s1.peek()) >= priority(item)) s2.add(s1.pop()); s1.push(item); } } // 将s1中剩余的运算符依次弹出，并加入s2 while (!s1.empty()) { s2.add(s1.pop()); } return s2; } private int priority(String op) { if ("+".equals(op) || "-".equals(op)) return 1; if ("*".equals(op) || "/".equals(op)) return 2; return 0; // 如果是左括号返回0 } // 对后缀表达式字符串列表进行计算 public double calculatePoland(List<String> list) { Stack<Double> stack = new Stack<>(); for (String s : list) { double n1, n2; switch (s) { case "*": n1 = stack.pop(); n2 = stack.pop(); stack.push(n1 * n2); break; case "/": n1 = stack.pop(); n2 = stack.pop(); stack.push(n2 / n1); break; case "+": n1 = stack.pop(); n2 = stack.pop(); stack.push(n1 + n2); break; case "-": n1 = stack.pop(); n2 = stack.pop(); stack.push(n2 - n1); break; default: stack.push(Double.parseDouble(s)); break; } } return stack.pop(); } public static void main(String[] args) { String exp = "12+((22+31)*4)-5"; InfixToPostfixDemo app = new InfixToPostfixDemo(); List<String> infixList = app.toInfixList(exp); // 第1步 List<String> postList = app.toPostList(infixList); // 第2步 double res = app.calculatePoland(postList); //第3步 System.out.println(infixList); System.out.println(postList); System.out.println(res); }}