recursive descendent parsing. LL(1). removing left recursion.

calc4.java

package llcalc;

import java.util.StringTokenizer;

class Expr {
    Term term;
    Expr2 expr2;
    Expr(Term term, Expr2 expr2) {
        this.term = term;
        this.expr2 = expr2;
    }
    double eval() {
        if (expr2 == null) {
            return term.eval();
        }
        return expr2.eval(term.eval());
    }
}
class Expr2 {
    String op;
    Term term;
    Expr2 expr2;
    Expr2(String op, Term term, Expr2 expr2) {
        this.op = op;
        this.term = term;
        this.expr2 = expr2;
    }
    double eval(double left) {
        double val;
        if ("+".equals(op)) {
            val = left + term.eval();
        } else {
            val = left - term.eval();
        }
        if (expr2 == null) {
            return val;
        }
        return expr2.eval(val);
    }
}
class Term {
    Factor factor;
    Term2 term2;
    Term(Factor factor, Term2 term2) {
        this.factor = factor;
        this.term2 = term2;
    }
    double eval() {
        if (term2 == null) {
            return factor.eval();
        }
        return term2.eval(factor.eval());
    }
}
class Term2 {
    String op;
    Factor factor;
    Term2 term2;
    Term2(String op, Factor factor, Term2 term2) {
        this.op = op;
        this.factor = factor;
        this.term2 = term2;
    }
    double eval(double left) {
        double val;
        if ("*".equals(op)) {
            val = left * factor.eval();
        } else {
            val = left / factor.eval();
        }
        if (term2 == null) {
            return val;
        }
        return term2.eval(val);
    }
}
class Factor {
    double number;
    Expr expr;
    Factor(double number) {
        this.number = number;
    }
    Factor(Expr expr) {
        this.expr = expr;
    }
    double eval() {
        if (expr == null) {
            return number;
        }
        return expr.eval();
    }
}
class Tokens {
    String buffer;
    StringTokenizer tokens;
    Tokens(String str) {
        tokens = new StringTokenizer(str);
    }
    String nextToken() {
        if (buffer != null) {
            try {
                return buffer;
            } finally {
                buffer = null;
            }
        }
        if (!tokens.hasMoreTokens()) {
            return null;
        }
        return tokens.nextToken();
    }
    boolean hasMoreTokens() {
        if (buffer != null) {
            return true;
        }
        return tokens.hasMoreTokens();
    }
    void putBack(String token) {
        buffer = token;
    }
}
public class LLCalc {
    Tokens tokens;
    Expr parse(String str) {
        tokens = new Tokens(str);
        Expr expr = parseExpr();
        if (tokens.hasMoreTokens()) {
            throw new RuntimeException("invalid expr");
        }
        return expr;
    }
    Expr parseExpr() {
        Term term = parseTerm();
        Expr2 expr = parseExpr2();
        return new Expr(term, expr);
    }
    Expr2 parseExpr2() {
        String op = tokens.nextToken();
        if (op == null) {
            return null;
        }
        if (!"+".equals(op) && !"-".equals(op)) {
            tokens.putBack(op);
            return null;
        }
        Term term = parseTerm();
        if (term == null) {
            throw new RuntimeException("term expected");
        }
        Expr2 expr2 = parseExpr2();
        return new Expr2(op, term, expr2);
    }
    Term parseTerm() {
        Factor factor = parseFactor();
        Term2 term2 = parseTerm2();
        return new Term(factor, term2);
    }
    Term2 parseTerm2() {
        String op = tokens.nextToken();
        if (op == null) {
            return null;
        }
        if (!"*".equals(op) && !"/".equals(op)) {
            tokens.putBack(op);
            return null;
        }
        Factor factor = parseFactor();
        if (factor == null) {
            throw new RuntimeException("factor expected");
        }
        Term2 term2 = parseTerm2();
        return new Term2(op, factor, term2);
    }
    Factor parseFactor() {
        if (!tokens.hasMoreTokens()) {
            return null;
        }
        String token = tokens.nextToken();
        if ("(".equals(token)) {
            Expr expr = parseExpr();
            String rparen = tokens.nextToken();
            if (rparen == null || !")".equals(rparen)) {
                throw new RuntimeException("unclosed paren");
            }
            return new Factor(expr);
        }
        try {
            Double d = Double.parseDouble(token);
            return new Factor(d);
        } catch (NumberFormatException e) {
            throw new RuntimeException("invalid number");
        }
    }
    public static void main(String[] args) {
        LLCalc calc = new LLCalc();
        Expr expr;
        double ret;

        expr = calc.parse("1");
        ret = expr.eval();

        expr = calc.parse("2 * 3");
        ret = expr.eval();

        expr = calc.parse("4 + 5");
        ret = expr.eval();

        expr = calc.parse("1 + 2 * 3");
        ret = expr.eval();

        expr = calc.parse("( 1 + 2 ) * 3");
        ret = expr.eval();

        expr = calc.parse("2 * ( 3 + 4 )");
        ret = expr.eval();
    }
}