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



    static SuffixExpression compile(String exp) {



        // 1. 将exp分割为操作数和运算符数组
        String[] expArray = exp.replaceAll("\\(", "\\( ")
                .replaceAll("\\)", "\\ )")
                .split("\\s+");  // 中缀表达式



        // 2. 扫描expArray



        List<String> postExp = new ArrayList<>();  // 后缀表达式
        Deque<String> opTr = new LinkedList<>(); // 操作运算符的栈
        Pattern p = Pattern.compile("[0-9]+");  // 数字正则表达式



        for (String str : expArray) {
            // (1) 如果str是数字, 放到postExp
            if (p.matcher(str).matches()) {
                postExp.add(str);
            // (2) 如果str是(, 进栈到opTr
            } else if ("(".equals(str)) {
                opTr.push(str);
            // (3) 如果str是), 将opTr中出栈时遇到的第一个左括号之前的运算符出栈并放到postExp中，然后将左括号出栈
            } else if (")".equals(str)) {
                while (!"(".equals(opTr.peek())) {
                    String pop = opTr.pop();
                    postExp.add(pop);
                }
                opTr.pop();
            // (4) 如果str为其他运算符
            } else {
                // 如果栈空或者栈顶元素为(, 直接将str进栈
                if (opTr.peek() == null || "(".equals(opTr.peek())) {
                    opTr.push(str);
                // 如果str的优先级高于栈顶元素的优先级，将str进栈
                } else if (getPriority(str) - getPriority(opTr.peek()) > 0) {
                    opTr.push(str);
                // 依次出栈并存入到postExp中，直到栈顶运算符优先级小于str优先级
                } else {
                    while (opTr.peek() != null && getPriority(opTr.peek()) - getPriority(str) >= 0) {
                        String pop = opTr.pop();
                        postExp.add(pop);
                    }
                    opTr.push(str);
                }
            }
        }



        // 3.expArray扫描完毕，将opTr中所有运算符依次出栈并存放到postExp中
        while (opTr.peek() != null) {
            postExp.add(opTr.pop());
        }



        return new SuffixExpression(postExp.toArray(String[]::new));
    }



    // 优先级越高，数值越大
    static int getPriority(String op) {
        int priority;
        switch (op) {
            case "+":
            case "-":
                priority = 1;
                break;
            case "*":
            case "/":
                priority = 2;
                break;
            default:
                throw new IllegalArgumentException("op = " + op);
        }
        return priority;
    }
}



class SuffixExpression {



    String[] postExp;



    public SuffixExpression(String[] postExp) {
        this.postExp = postExp;
    }



    int execute() {
        Deque<Integer> stack = new LinkedList<>();  // 栈
        Pattern p = Pattern.compile("[0-9]+");  // 数字正则表达式



        for (String str : postExp) {
            if (p.matcher(str).matches()) {
                stack.push(Integer.parseInt(str));
            } else {
                Integer i1 = stack.pop();
                Integer i2 = stack.pop();
                Integer result = getResult(i2, i1, str);
                stack.push(result);
            }
        }
        return stack.pop();
    }



    private Integer getResult(Integer i1, Integer i2, String operator) {
        Integer result;
        switch (operator) {
            case "+":
                result = i1 + i2;
                break;
            case "-":
                result = i1 - i2;
                break;
            case "*":
                result = i1 * i2;
                break;
            case "/":
                result = i1 / i2;
                break;
            default:
                throw new IllegalArgumentException("operator = " + operator);
        }
        return result;
    }
}