public class Code02 {
    public static void main(String[] args) {
        String exp = "1 + 2 * (9 - 5)";
        SuffixExpression se = compile(exp);
        int result = se.execute();
        System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
    }

    static SuffixExpression compile(String  exp) {
        /**
         * 将前缀表达式转化为后置表达式，方便计算机计算，这个算法是前人已经给我们准备好了的
         * 可以直接拿来用, 可以直接自己进行百度
         * 大概的点有下面几点
         * 1. 准备两个容器 s1（存储运算符和括号是一个中间容器） s2（储存表达式）
         * 2. 如果遇到数字毫不犹豫的存入s2
         * 3. 如果遇到运算符
         * (1). s1栈顶为空则直接将其压入s1
         * (2). s1栈顶的优先级小那么就将其压入s1 如果栈顶优先级更大就将其推出放入s2 并且拿着现在的运算符继续循环下去
         * 4. 如果遇到 ( 请毫不犹豫的压入 s1
         * 5. 如果遇到 ) 将运算符从s1推出至s2,直至遇到 ( 停止并且将 ( 从 s1删除
         * 6. 当所有的运算符括号数字跑完后就将剩余的运算符从 s1 压入 s2
         * 1 + 2 * (9 - 5) => 1 2 9 5 - * +
         *  转换完成后计算就简单了
         *  其中 num num op 为一个基本表达式,当表达式计算完成后并还剩一个num时则为计算完毕
         *  1 2 9 5 - * + =>
         *  1 2 4 * + =>
         *  1 8 + =>
         *  9 =>
         */
        ArrayList<String> suffixExpression = new ArrayList<>(); //存储后缀表达式
        Stack<String> stack = new Stack<>();  //存储运算符
        HashMap<String, Integer> cMap = new HashMap<>();
        cMap.put(null, 0);
        cMap.put("+", 1);
        cMap.put("-", 1);
        cMap.put("*", 2);
        cMap.put("/", 2);
        cMap.put("(", -1);
        cMap.put(")", -1);
        exp = exp.replace("(", " ( ").replace(")", " ) ");
        String[] split = exp.split("\\s+");
        for (String c : split) {
            switch (c){
                case "+":
                case "-":
                case "*":
                case "/":
                    while (true){
                        String peek = stack.isEmpty() ? null : stack.peek();
                        if (cMap.get(c) <= cMap.get(peek)) {
                            suffixExpression.add(stack.pop());
                        }
                        else {
                            stack.push(c);
                            break;
                        }
                    }
                    break;
                case "(":
                    stack.push(c);
                    break;
                case ")":
                    while (!"(".equals(stack.peek())){
                        suffixExpression.add(stack.pop());
                    }
                    stack.pop();
                    break;
                default:
                    suffixExpression.add(c);
            }
        }
        while (!stack.isEmpty()){
            suffixExpression.add(stack.pop());
        }
        return new SuffixExpression(suffixExpression);
    }
}

class SuffixExpression {
    ArrayList<String> exp = null;
    public SuffixExpression(ArrayList<String> exp){
        this.exp = exp;
    }
    int execute() {
        // TODO:
        // n1 n2 op 为底层
        while (exp.size() > 1)
        {
            List<Integer> opIndex = Arrays.asList(exp.indexOf("+"),
                                                exp.indexOf("-"),
                                                exp.indexOf("*"),
                                                exp.indexOf("/"));
            Optional<Integer> min = opIndex.stream().min(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    if (o1 < 0)
                        return Integer.MAX_VALUE;
                    if (o2 < 0)
                        return Integer.MIN_VALUE;
                    return o1 - o2;
                }
            });
            Integer integer = min.get();
            exp(exp, integer);
        }
        return Integer.parseInt(exp.get(0));
    }
    private void exp(ArrayList<String> exp, Integer opIndex){
        int n1 = Integer.parseInt(exp.get(opIndex - 2));
        int n2 = Integer.parseInt(exp.get(opIndex - 1));
        int ret = 0;
        switch (exp.get(opIndex)){
            case "*":
                ret = n1 * n2;
                break;
            case "+":
                ret = n1 + n2;
                break;
            case "-":
                ret = n1 - n2;
                break;
            case "/":
                ret = n1 / n2;
                break;
        }
        for (int i = 0; i < 3; i++)
            exp.remove(opIndex - 2);
        exp.add(opIndex - 2, String.valueOf(ret));
    }
    int execute(Map<String, Integer> env) {
        // TODO:
        exp.replaceAll(new UnaryOperator<String>(){
            @Override
            public String apply(String s) {
                Integer integer = env.get(s);
                if (integer != null)
                    s = String.valueOf(integer);
                return s;
            }
        });
        System.out.println(exp);
        return execute();
    }
}