// 第 7 周 – 把中缀表达式转换成后缀表达式（Dijkstra 调度场算法的简化版）
// 运行：java InfixToPostfix.java
import java.util.ArrayDeque;

public class InfixToPostfix {

    static int precedence(char op) {
        return (op == '*' || op == '/') ? 2 : (op == '+' || op == '-') ? 1 : 0;
    }

    // 适用于一位数字 / 变量名、+ - * / 和括号
    //  - 操作数：直接输出
    //  - '('：入栈
    //  - ')'：把栈中元素依次输出，直到遇到 '('
    //  - 运算符：只要栈顶是优先级不低于它的运算符，就输出栈顶；然后入栈
    //  - 最后，输出栈中剩余的元素
    static String convert(String infix) {
        StringBuilder out = new StringBuilder();
        ArrayDeque<Character> ops = new ArrayDeque<>();
        for (char c : infix.toCharArray()) {
            if (c == ' ') continue;
            if (Character.isLetterOrDigit(c)) {
                out.append(c).append(' ');
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.peek() != '(') out.append(ops.pop()).append(' ');
                ops.pop(); // 丢弃 '('
            } else {
                while (!ops.isEmpty() && precedence(ops.peek()) >= precedence(c)) out.append(ops.pop()).append(' ');
                ops.push(c);
            }
        }
        while (!ops.isEmpty()) out.append(ops.pop()).append(' ');
        return out.toString().trim();
    }

    public static void main(String[] args) {
        String[] tests = { "3 + 4 * 2", "(3 + 4) * 2", "a + b * c - d", "(a + b) * (c - d)", "1 + 2 - 3 * 4 / 5" };
        for (String t : tests) {
            String p = convert(t);
            System.out.printf("%-20s ->  %s%n", t, p);
        }
        // 转换后的表达式可以求值（见 Postfix.java）：
        String p = convert("(3 + 4) * 2");
        System.out.println("\n(3 + 4) * 2 = " + evaluatePostfix(p));
    }

    // 后缀表达式求值（与 Postfix.java 相同，用于整数）
    static int evaluatePostfix(String expr) {
        ArrayDeque<Integer> st = new ArrayDeque<>();
        for (String t : expr.split(" ")) {
            if (t.length() == 1 && "+-*/".contains(t)) {
                int b = st.pop(), a = st.pop();
                st.push(switch (t.charAt(0)) {
                    case '+' -> a + b;
                    case '-' -> a - b;
                    case '*' -> a * b;
                    default -> a / b;
                });
            } else {
                st.push(Integer.parseInt(t));
            }
        }
        return st.pop();
    }
}