// 第 7 周 – 用栈计算后缀（逆波兰）表达式
// 运行：java Postfix.java
import java.util.ArrayDeque;

public class Postfix {

    // 各个记号用空格分隔："3 4 + 2 *"
    //   伪代码：
    //     For every token t
    //       If t is a number then Push(t)
    //       else b ← Pop ; a ← Pop ; Push(a t b)
    //     End for
    //     Return Pop
    static double evaluate(String expr, boolean trace) {
        ArrayDeque<Double> stack = new ArrayDeque<>();
        for (String t : expr.trim().split("\\s+")) {
            if (isOperator(t)) {
                double b = stack.pop(); // 注意：右操作数先出栈！
                double a = stack.pop();
                stack.push(apply(a, b, t));
            } else {
                stack.push(Double.parseDouble(t));
            }
            if (trace) System.out.printf("  %-4s stack: %s%n", t, stack);
        }
        if (stack.size() != 1) throw new IllegalArgumentException("invalid expression");
        return stack.pop();
    }

    static boolean isOperator(String t) {
        return t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/");
    }

    static double apply(double a, double b, String op) {
        return switch (op) {
            case "+" -> a + b;
            case "-" -> a - b;
            case "*" -> a * b;
            default -> a / b;
        };
    }

    public static void main(String[] args) {
        System.out.println("3 4 + 2 *  (= (3 + 4) * 2)");
        System.out.println("result: " + evaluate("3 4 + 2 *", true));

        System.out.println("\n1 2 + 3 4 * - 9 /  (= ((1 + 2) - 3 * 4) / 9)");
        System.out.println("result: " + evaluate("1 2 + 3 4 * - 9 /", true));

        System.out.println("\n5 1 2 + 4 * + 3 -  (= 5 + (1 + 2) * 4 - 3)");
        System.out.println("result: " + evaluate("5 1 2 + 4 * + 3 -", false));
    }
}