// 7. hét – Infix kifejezés átalakítása postfixre (Dijkstra "tolatópályaudvar" algoritmusa, egyszerűsítve)
// Futtatás: java InfixToPostfix.java
import java.util.ArrayDeque;

public class InfixToPostfix {

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

    // Egyjegyű számokra / változónevekre, + - * / és zárójelek
    //  - operandus: azonnal a kimenetre
    //  - '(': a verembe
    //  - ')': a veremből a kimenetre a '('-ig
    //  - operátor: amíg a verem tetején legalább ilyen erős operátor van, azt kiírjuk; utána betesszük
    //  - a végén a verem maradékát kiírjuk
    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(); // a '(' eldobása
            } 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);
        }
        // Az átalakított kifejezés kiértékelhető (lásd Postfix.java):
        String p = convert("(3 + 4) * 2");
        System.out.println("\n(3 + 4) * 2 = " + evaluatePostfix(p));
    }

    // Postfix kiértékelés (ugyanaz, mint a Postfix.java-ban, egész számokra)
    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();
    }
}