// 14. hét – Kifejezésfa: felépítés postfix alakból VEREMMEL, kiértékelés rekurzióval
// Futtatás: java ExpressionTree.java
import java.util.ArrayDeque;

public class ExpressionTree {

    static class Node {
        String token;
        Node left, right;
        Node(String t, Node l, Node r) { token = t; left = l; right = r; }
    }

    static boolean isOp(String t) { return t.length() == 1 && "+-*/".contains(t); }

    // Postfix -> fa: számnál új levél a verembe; operátornál két részfa ki, új csomópont be
    static Node fromPostfix(String expr) {
        ArrayDeque<Node> st = new ArrayDeque<>();
        for (String t : expr.split(" ")) {
            if (isOp(t)) {
                Node r = st.pop(), l = st.pop();
                st.push(new Node(t, l, r));
            } else {
                st.push(new Node(t, null, null));
            }
        }
        return st.pop();
    }

    // Kiértékelés: postorder jellegű – előbb a két részfa értéke, aztán a művelet
    static double eval(Node p) {
        if (!isOp(p.token)) return Double.parseDouble(p.token);
        double a = eval(p.left), b = eval(p.right);
        return switch (p.token) {
            case "+" -> a + b;
            case "-" -> a - b;
            case "*" -> a * b;
            default -> a / b;
        };
    }

    static String infix(Node p) {     // inorder zárójelekkel
        if (!isOp(p.token)) return p.token;
        return "(" + infix(p.left) + " " + p.token + " " + infix(p.right) + ")";
    }

    static String prefix(Node p) {    // preorder
        if (!isOp(p.token)) return p.token;
        return p.token + " " + prefix(p.left) + " " + prefix(p.right);
    }

    static String postfix(Node p) {   // postorder
        if (!isOp(p.token)) return p.token;
        return postfix(p.left) + " " + postfix(p.right) + " " + p.token;
    }

    public static void main(String[] args) {
        Node t = fromPostfix("3 4 + 5 2 - *");
        System.out.println("infix:   " + infix(t));
        System.out.println("prefix:  " + prefix(t));
        System.out.println("postfix: " + postfix(t));
        System.out.println("érték:   " + eval(t));

        Node u = fromPostfix("1 2 + 3 4 * - 9 /");
        System.out.println("\n" + infix(u) + " = " + eval(u));
    }
}