import java.util.*;

enum Operator {
    ADD("+", 1), SUBTRACT("-", 1),
    MULTIPLY("*", 2), DIVIDE("/", 2),
    LEFT_BRACKET("(", 3), RIGHT_BRACKET(")", 3);
    String value;
    int priority;

    Operator(String value, int priority) {
        this.value = value;
        this.priority = priority;
    }

    /**
     * 比较两个符号的优先级
     *
     * @return c1的优先级是否比c2的高，高则返回正数，等于返回0，小于返回负数
     */
    public static int cmp(String c1, String c2) {
        int p1 = 0;
        int p2 = 0;
        for (Operator o : Operator.values()) {
            if (Objects.equals(o.value, c1)) {
                p1 = o.priority;
            }
            if (Objects.equals(o.value, c2)) {
                p2 = o.priority;
            }
        }

        return p1 - p2;
    }

    /**
     * 枚举出来的才视为运算符，用于扩展
     *
     * @return true 表示非运算符， false 表示是运算符，符号在枚举类型中
     */
    public static boolean isNotOperate(String c) {
        for (Operator o : Operator.values()) {
            if (Objects.equals(o.value, c)) {
                return false;
            }
        }
        return true;
    }

}

public class Test {
    public static void main(String[] args) {
        String exp = "6*(x+(2+3)*y+3)";
        SuffixExpression se = compile(exp);
        Map<String, Integer> env = Map.of("x", 3, "y", 4);
        int result = se.execute(env);
        System.out.println(exp + " = " + result + " " + (result == 6 * (3 + (2 + 3) * 4 + 3) ? "✓" : "✗"));
    }

    static SuffixExpression compile(String exp) {
        // --- 实例 1个列表 和 1个堆栈 用来存储运算符和输出结果
        List<String> arrStrOpt = new ArrayList<>();
        Deque<String> stackOperate = new LinkedList<>();

        // 记录当前的非操作符字符 用于后续拼接成完整的数值
        // 适用于多位的数值，例如：123
        StringBuilder strValue = new StringBuilder();

        // --- 遍历传入的表达式
        for (int i = 0; i < exp.length(); i++) {
            String strTempChar = String.valueOf(exp.charAt(i));
            // 为空跳过
            if (strTempChar.equals(" "))
                continue;

            // --- 数值的判断
            // 非操作符 记录当前字符
            if (Operator.isNotOperate(strTempChar)) {
                strValue.append(strTempChar);
                continue;
            }
            // 到操作符了 说明前面的数值类字符已经遍历完了
            // 拼接为一个完整数值 并添加到输出结果
            if (strValue.length() > 0) {
                arrStrOpt.add(strValue.toString());
                strValue.delete(0, strValue.length());
            }

            // --- 操作符的判断
            // 规则1：右括号 ")" 用于强制在遇到右括号时将栈中的操作符弹出，直到遇到相应的左括号为止。
            if (strTempChar.equals(Operator.RIGHT_BRACKET.value)) {
                while (!(stackOperate.isEmpty() || stackOperate.peek().equals(Operator.LEFT_BRACKET.value))) {
                    arrStrOpt.add(stackOperate.pop());
                }
                // 输入无误的情况下 肯定会在"("的时候停下 所以这边直接把"("弹掉就好了
                stackOperate.pop();
            }
            // 规则2：如果栈为空，或者栈顶为左括号"("，那么遇到的操作符直接入栈。
            // 规则3：如果遇到的操作符优先级大于栈顶操作符的优先级，那么遇到的操作符入栈。
            else if (stackOperate.isEmpty() || stackOperate.peek().equals(Operator.LEFT_BRACKET.value)
                    || Operator.cmp(strTempChar, stackOperate.peek()) > 0
            ) {
                stackOperate.push(strTempChar);
            }
            // 规则4：如果遇到的操作符优先级小于等于栈顶操作符的优先级，那么将栈顶的操作符弹出并添加到逆波兰表达式中
            // 然后继续比较新的栈顶操作符，直到满足上述条件后再将遇到的操作符入栈。
            else if (Operator.cmp(strTempChar, stackOperate.peek()) <= 0) {
                while (!(stackOperate.isEmpty() || stackOperate.peek().equals(Operator.LEFT_BRACKET.value)
                        || Operator.cmp(strTempChar, stackOperate.peek()) > 0)
                ) {
                    arrStrOpt.add(stackOperate.pop());
                }
                stackOperate.push(strTempChar);
            }

            //System.out.println(stackOperate);
        }

        // --- 遍历完毕
        // 1. 拼接最后的数值
        // 2. 出栈剩余的所有操作符
        if (strValue.length() > 0) {
            arrStrOpt.add(strValue.toString());
            strValue.delete(0, strValue.length());
        }
        while (!stackOperate.isEmpty()) {
            arrStrOpt.add(stackOperate.pop());
        }

        // System.out.println(arrStrOpt);
        return new SuffixExpression(arrStrOpt);
    }
}

class SuffixExpression {
    // final 只是引用不可变 所以设置为这个没有关系
    // 因为数组类是可以直接修改内部的
    private final List<String> m_arrOpt;
    private final Deque<Integer> m_stack = new LinkedList<>();

    SuffixExpression(List<String> arrOpt) {
        this.m_arrOpt = arrOpt;
    }

    int execute(Map<String, Integer> env) {
        for (String strChar : m_arrOpt) {
            if (Operator.isNotOperate(strChar)) {
                switch (strChar) {
                    case "x" -> m_stack.push(env.get("x"));
                    case "y" -> m_stack.push(env.get("y"));
                    default -> m_stack.push(Integer.parseInt(strChar));
                }
            } else {
                int iValue2 = m_stack.pop(); // 堆栈是先进后出 所以这边iValue2要在前面
                int iValue = m_stack.pop();
                int res = switch (strChar) {
                    case "+" -> (iValue + iValue2);
                    case "-" -> (iValue - iValue2);
                    case "*" -> (iValue * iValue2);
                    case "/" -> (iValue / iValue2);
                    default -> 0;
                };
                m_stack.push(res);
            }
        }

        return m_stack.pop();
    }
}