import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class Calc {

    // ---- Tokens ----
    sealed interface Token permits Num, Name, Sym {}
    record Num(double value) implements Token {}
    record Name(String text) implements Token {}
    record Sym(char c) implements Token {}

    static List<Token> tokenize(String src) {
        List<Token> out = new ArrayList<>();
        int i = 0;
        while (i < src.length()) {
            char c = src.charAt(i);
            if (Character.isWhitespace(c)) {
                i++;
            } else if (Character.isDigit(c) || c == '.') {
                int start = i;
                while (i < src.length() && (Character.isDigit(src.charAt(i)) || src.charAt(i) == '.')) i++;
                out.add(new Num(Double.parseDouble(src.substring(start, i))));
            } else if (Character.isLetter(c)) {
                int start = i;
                while (i < src.length() && Character.isLetterOrDigit(src.charAt(i))) i++;
                out.add(new Name(src.substring(start, i)));
            } else if ("+-*/^(),".indexOf(c) >= 0) {
                out.add(new Sym(c));
                i++;
            } else {
                throw new IllegalArgumentException("Unexpected character '" + c + "' at " + i);
            }
        }
        return out;
    }

    // ---- Syntax tree ----
    sealed interface Expr permits Number, Var, Unary, Binary, Call {}
    record Number(double value) implements Expr {}
    record Var(String name) implements Expr {}
    record Unary(char op, Expr operand) implements Expr {}
    record Binary(char op, Expr left, Expr right) implements Expr {}
    record Call(String function, List<Expr> args) implements Expr {}

    // ---- Parser ----
    //   expression -> term (('+' | '-') term)*
    //   term       -> unary (('*' | '/') unary)*
    //   unary      -> '-' unary | power
    //   power      -> primary ('^' unary)?
    //   primary    -> NUMBER | NAME | NAME '(' args ')' | '(' expression ')'
    static final class Parser {
        private final List<Token> tokens;
        private int pos = 0;

        Parser(List<Token> tokens) { this.tokens = tokens; }

        Expr parse() {
            Expr e = expression();
            if (pos != tokens.size()) throw error("unexpected " + tokens.get(pos));
            return e;
        }

        private Expr expression() {
            Expr left = term();
            while (peek('+') || peek('-')) {
                char op = next();
                left = new Binary(op, left, term());
            }
            return left;
        }

        private Expr term() {
            Expr left = unary();
            while (peek('*') || peek('/')) {
                char op = next();
                left = new Binary(op, left, unary());
            }
            return left;
        }

        private Expr unary() {
            if (peek('-')) {
                next();
                return new Unary('-', unary());
            }
            return power();
        }

        private Expr power() {
            Expr base = primary();
            if (peek('^')) {
                next();
                return new Binary('^', base, unary()); // right-associative: 2^3^2 = 2^9
            }
            return base;
        }

        private Expr primary() {
            if (pos >= tokens.size()) throw error("unexpected end of expression");
            Token t = tokens.get(pos++);
            return switch (t) {
                case Num n -> new Number(n.value());
                case Name n when peek('(') -> call(n.text());
                case Name n -> new Var(n.text());
                case Sym s when s.c() == '(' -> {
                    Expr inner = expression();
                    expect(')');
                    yield inner;
                }
                case Sym s -> throw error("unexpected '" + s.c() + "'");
            };
        }

        private Expr call(String function) {
            expect('(');
            List<Expr> args = new ArrayList<>();
            if (!peek(')')) {
                args.add(expression());
                while (peek(',')) {
                    next();
                    args.add(expression());
                }
            }
            expect(')');
            return new Call(function, args);
        }

        private boolean peek(char c) {
            return pos < tokens.size() && tokens.get(pos) instanceof Sym s && s.c() == c;
        }

        private char next() {
            return ((Sym) tokens.get(pos++)).c();
        }

        private void expect(char c) {
            if (!peek(c)) throw error("'" + c + "' expected");
            pos++;
        }

        private IllegalArgumentException error(String message) {
            return new IllegalArgumentException(message + " at token " + pos);
        }
    }

    // ---- Evaluation ----
    static double eval(Expr e, Map<String, Double> vars) {
        return switch (e) {
            case Number n -> n.value();
            case Var v -> {
                Double value = vars.get(v.name());
                if (value == null) throw new IllegalArgumentException("unknown variable " + v.name());
                yield value;
            }
            case Unary u -> -eval(u.operand(), vars);
            case Binary b -> {
                double l = eval(b.left(), vars), r = eval(b.right(), vars);
                yield switch (b.op()) {
                    case '+' -> l + r;
                    case '-' -> l - r;
                    case '*' -> l * r;
                    case '/' -> l / r;
                    case '^' -> Math.pow(l, r);
                    default -> throw new IllegalStateException("operator " + b.op());
                };
            }
            case Call c -> {
                List<Double> a = c.args().stream().map(x -> eval(x, vars)).toList();
                yield switch (c.function()) {
                    case "sqrt" -> Math.sqrt(a.get(0));
                    case "sin" -> Math.sin(a.get(0));
                    case "max" -> a.stream().mapToDouble(Double::doubleValue).max().orElseThrow();
                    default -> throw new IllegalArgumentException("unknown function " + c.function());
                };
            }
        };
    }

    static double calc(String src, Map<String, Double> vars) {
        return eval(new Parser(tokenize(src)).parse(), vars);
    }

    public static void main(String[] args) {
        Map<String, Double> vars = Map.of("x", 3.0, "pi", Math.PI);
        String[][] cases = {
            {"2 + 3 * (4 - 5) + 6 - 7", "-2.0"},
            {"2 + 2 * (3 + 4 * (5 - 6))", "0.0"},
            {"10 - 4 - 3", "3.0"},
            {"-2 ^ 2", "-4.0"},
            {"2 ^ 3 ^ 2", "512.0"},
            {"2 * -x", "-6.0"},
            {"max(1, x * 2, sqrt(16))", "6.0"},
            {"-(1 + 2) * 3", "-9.0"},
        };
        for (String[] c : cases) {
            double r = calc(c[0], vars);
            System.out.printf("%-28s = %-6s %s%n", c[0], r, String.valueOf(r).equals(c[1]) ? "ok" : "EXPECTED " + c[1]);
        }
        for (String bad : new String[] {"2 +", "(1 + 2", "2 3", "1 # 2"}) {
            try {
                calc(bad, vars);
                System.out.println(bad + " -> NO ERROR");
            } catch (IllegalArgumentException ex) {
                System.out.printf("%-28s -> %s%n", bad, ex.getMessage());
            }
        }
        System.out.println(new Parser(tokenize("2 + 3 * x")).parse());
    }
}