import java.util.*; // context for expression eval interface Context { boolean getBoolean (String identifier) ; double getNumeric (String identifier) ; } // printable expression abstract class Expression { public abstract boolean evalBoolean (Context context) ; public abstract double evalNumeric (Context context) ; public boolean isBoolean () { return false; } public boolean isNumeric () { return false; } public StringBuffer concat (StringBuffer buffer, int precidence) { return buffer.append(this); } } // boolean expressions abstract class BooleanExpression extends Expression { public double evalNumeric (Context context) { throw new RuntimeException(); } public boolean isBoolean () { return true; } } // numeric expressions abstract class NumericExpression extends Expression { public boolean evalBoolean (Context context) { throw new RuntimeException(); } public boolean isNumeric () { return true; } } // literals class BooleanLiteral extends BooleanExpression { private BooleanLiteral (boolean value) { this.value = value; } private final boolean value; public boolean evalBoolean (Context context) { return value; } static final BooleanLiteral TRUE = new BooleanLiteral(true); static final BooleanLiteral FALSE = new BooleanLiteral(false); public String toString () { return String.valueOf(value); } } class NumericLiteral extends NumericExpression { NumericLiteral (double value) { this.value = value; } private final double value; public double evalNumeric (Context context) { return value; } static final NumericLiteral ZERO = new NumericLiteral(0); static final NumericLiteral ONE = new NumericLiteral(1); public String toString () { return String.valueOf(value); } } // numeric variables class Variable extends Expression { Variable (String identifier) { this.identifier = identifier; } private final String identifier; public double evalNumeric (Context context) { return context.getNumeric(identifier); } public boolean evalBoolean (Context context) { return context.getBoolean(identifier); } public boolean isBoolean () { return true; } public boolean isNumeric () { return true; } public String toString () { return identifier; } } class Operator { Operator (String symbol, int precidence) { this.symbol = symbol; this.precidence = precidence; OPERATORS.put(symbol, this); } final String symbol; final int precidence; int getPrecidence () { return precidence; } public String toString () { return symbol; } Expression buildExpression (Expression left, Expression right) { throw new RuntimeException("Not a binary operator"); } static final Map OPERATORS = new HashMap(); } // binary operators abstract class BinaryNumericOperator extends Operator { BinaryNumericOperator (String symbol, int precidence) { super(symbol, precidence + 500); } abstract double apply (double left, double right) ; Expression buildExpression (Expression left, Expression right) { if (left.isNumeric() && right.isNumeric()) { return new BinaryNumericExpression(left, this, right); } else { throw new RuntimeException(this + " requires numeric operands."); } } static final BinaryNumericOperator PLUS = new BinaryNumericOperator("+", 0) { double apply (double left, double right) { return left + right; } }; static final BinaryNumericOperator MINUS = new BinaryNumericOperator("-", 0) { double apply (double left, double right) { return left - right; } }; static final BinaryNumericOperator TIMES = new BinaryNumericOperator("*", 2) { double apply (double left, double right) { return left * right; } }; static final BinaryNumericOperator DIVIDE = new BinaryNumericOperator("/", 3) { double apply (double left, double right) { return left / right; } }; static void forceLoad () { } } abstract class BinaryBooleanOperator extends Operator { BinaryBooleanOperator (String symbol, int precidence) { super(symbol, precidence); } abstract boolean apply (boolean left, boolean right) ; Expression buildExpression (Expression left, Expression right) { if (left.isBoolean() && right.isBoolean()) { return new BinaryBooleanExpression(left, this, right); } else { throw new RuntimeException(this + " requires boolean operands."); } } static final BinaryBooleanOperator AND = new BinaryBooleanOperator("and", 0) { boolean apply (boolean left, boolean right) { return left & right; } }; static final BinaryBooleanOperator OR = new BinaryBooleanOperator("or", 1) { boolean apply (boolean left, boolean right) { return left | right; } }; static final BinaryBooleanOperator XOR = new BinaryBooleanOperator("xor", 2) { boolean apply (boolean left, boolean right) { return left ^ right; } }; static final BinaryBooleanOperator EQIV = new BinaryBooleanOperator("<=>", 3) { boolean apply (boolean left, boolean right) { return left == right; } }; static void forceLoad () { } } abstract class RelationalOperator extends Operator { RelationalOperator (String symbol, int precidence) { super(symbol, precidence + 100); } abstract boolean apply (double left, double right) ; Expression buildExpression (Expression left, Expression right) { if (left.isNumeric() && right.isNumeric()) { return new BinaryRelationalExpression(left, this, right); } else { throw new RuntimeException(this + " requires numeric operands."); } } static final RelationalOperator EQ = new RelationalOperator("=", 0) { boolean apply (double left, double right) { return left == right; } }; static final RelationalOperator NE = new RelationalOperator("!=", 0) { boolean apply (double left, double right) { return left != right; } }; static final RelationalOperator LT = new RelationalOperator("<", 0) { boolean apply (double left, double right) { return left < right; } }; static final RelationalOperator LE = new RelationalOperator("<=", 0) { boolean apply (double left, double right) { return left <= right; } }; static final RelationalOperator GT = new RelationalOperator(">", 0) { boolean apply (double left, double right) { return left > right; } }; static final RelationalOperator GE = new RelationalOperator(">=", 0) { boolean apply (double left, double right) { return left >= right; } }; static void forceLoad () { } } // binary expressions abstract class BinaryExpression extends Expression { BinaryExpression (Expression left, O operator, Expression right) { this.operator = operator; this.left = left; this.right = right; } final O operator; final Expression left; final Expression right; public StringBuffer concat (StringBuffer buffer, int precidence) { final int p = operator.getPrecidence(); if (precidence > p) { buffer.append('('); } left.concat(buffer, p); buffer.append(operator); right.concat(buffer, p); if (precidence > p) { buffer.append(')'); } return buffer; } public String toString () { return concat(new StringBuffer(), 0).toString(); } } class BinaryNumericExpression extends BinaryExpression { BinaryNumericExpression (Expression left, BinaryNumericOperator operator, Expression right) { super(left, operator, right); } public double evalNumeric (Context context) { return operator.apply(left.evalNumeric(context), right.evalNumeric(context)); } public boolean evalBoolean (Context context) { throw new RuntimeException(); } public boolean isNumeric () { return true; } } class BinaryBooleanExpression extends BinaryExpression { BinaryBooleanExpression (Expression left, BinaryBooleanOperator operator, Expression right) { super(left, operator, right); } public double evalNumeric (Context context) { throw new RuntimeException(); } public boolean evalBoolean (Context context) { return operator.apply(left.evalBoolean(context), right.evalBoolean(context)); } public boolean isBoolean () { return true; } } class BinaryRelationalExpression extends BinaryExpression { BinaryRelationalExpression (Expression left, RelationalOperator operator, Expression right) { super(left, operator, right); } public double evalNumeric (Context context) { throw new RuntimeException(); } public boolean evalBoolean (Context context) { return operator.apply(left.evalNumeric(context), right.evalNumeric(context)); } public boolean isBoolean () { return true; } } // Concrete context class ConcreteContext implements Context { public boolean getBoolean (String identifier) { return false; } public double getNumeric (String identifier) { return values.get(identifier); } void set (String identifier, double value) { values.put(identifier, value); } final Map values = new HashMap(); } // Parser pushes left or right based on precidence public class ExpressionParser { ExpressionParser (String input) { this.input = input; this.index = 0; this.length = input.length(); } private final String input; private final int length; private int index; public static Expression parse (String input) { return new ExpressionParser(input).parseInternal(-1, END_OF_INPUT); } private Expression parseTerm () { switch (nextToken()) { case IDENTIFIER: return new Variable(token); case NUMERIC: return new NumericLiteral(Double.parseDouble(token)); case OPEN_PAREN: { Expression expression = parseInternal(-1, CLOSE_PAREN); int tt = nextToken(); if (tt != CLOSE_PAREN) throw new RuntimeException("unexpected '" + token + "' (" + tt + ") at " + index); return expression; } case LITERAL_TRUE: return BooleanLiteral.TRUE; case LITERAL_FALSE: return BooleanLiteral.FALSE; default: throw new RuntimeException("unexpected '" + token + "' at " + index); } } private Expression parseInternal (int precidence, int end) { Expression left = parseTerm(); for (;;) { int tt = nextToken(); if (tt == end) { rewind = tt; return left; } if (tt != OPERATOR) throw new RuntimeException("unexpected '" + token + "' at " + index); if (operator.getPrecidence() < precidence) { rewind = tt; return left; } Operator op = operator; Expression right = parseInternal(op.getPrecidence(), end); left = op.buildExpression(left, right); } } // lexing int nextToken () { if (rewind != 0) { int tt = rewind; rewind = 0; return tt; } token = null; while ((index < length) && (Character.isWhitespace(input.charAt(index)))) ++index; if (index >= length) return END_OF_INPUT; final int start = index; char ch = input.charAt(start); ++index; if (ch == '(') return OPEN_PAREN; if (ch == ')') return CLOSE_PAREN; if (Character.isJavaIdentifierStart(ch)) { while ((index < length) && (Character.isJavaIdentifierPart(input.charAt(index)))) ++index; token = input.substring(start, index); if ("true".equals(token)) { return LITERAL_TRUE; } if ("false".equals(token)) { return LITERAL_FALSE; } operator = Operator.OPERATORS.get(token); return operator == null ? IDENTIFIER : OPERATOR; } if (Character.isDigit(ch)) { while ((index < length) && (Character.isDigit(ch = input.charAt(index)) || (ch == '.'))) // etc. ++index; token = input.substring(start, index); numeric = Double.parseDouble(token); return NUMERIC; } while ((index < length) && (!Character.isWhitespace(ch = input.charAt(index))) && (!Character.isJavaIdentifierPart(ch)) && (ch != '(') && (ch != ')')) ++index; token = input.substring(start, index); operator = Operator.OPERATORS.get(token); if (operator == null) { throw new RuntimeException("unknown operator '" + token + "'"); } return OPERATOR; } Operator operator; String token; double numeric; int rewind; static final int END_OF_INPUT = 0; static final int IDENTIFIER = 1; static final int NUMERIC = 2; static final int OPERATOR = 3; static final int OPEN_PAREN = 4; static final int CLOSE_PAREN = 5; static final int LITERAL_TRUE = 6; static final int LITERAL_FALSE = 7; public static void main (String...args) { /* // test tokenizer ExpressionParser parser = new ExpressionParser("this + is > ( a and (true xor false) or ( c*d/e < test ))"); eof: for (;;) { switch (parser.nextToken()) { case IDENTIFIER: System.out.println("IDENTIFIER " + parser.token); break; case NUMERIC: System.out.println("NUMERIC " + parser.numeric); break; case OPERATOR: System.out.println("OPERATOR " + parser.operator); break; case OPEN_PAREN: System.out.println("OPEN_PAREN "); break; case CLOSE_PAREN: System.out.println("CLOSE_PAREN"); break; case LITERAL_TRUE: System.out.println("LITERAL_TRUE"); break; case LITERAL_FALSE: System.out.println("LITERAL_FALSE"); break; default: break eof; } } */ // test the whole gubbins ConcreteContext context = new ConcreteContext(); context.set("a", 8); context.set("b", 5); context.set("c", 6); context.set("pi", Math.PI); String[] tests = { "10*2+3*7", "((((((((((pi))))))))))", "(1+(4))", "((1+(2+3)+(4)))", "7>=8", "7>=8-1", "7+1>=8-1", "( (8+1 > 4*5) and ((6 +2) * 6 <= 5) )", "(a+1 > b*5) and ((c +2) * 6 <= 5)", }; for (int i = 0; i < tests.length; ++i) { System.out.println(tests[i]); Expression expression = parse(tests[i]); System.out.println(expression); if (expression.isNumeric()) { System.out.println(expression.evalNumeric(context)); } else { System.out.println(expression.evalBoolean(context)); } System.out.println(); } } static { BinaryBooleanOperator.forceLoad(); BinaryNumericOperator.forceLoad(); RelationalOperator.forceLoad(); } }