中缀表达式转后缀表达式并计算结果Java实现

/*
  中缀表达式转成后缀表达式 "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);
    }
}