Expression evaluation in Java (3)

In the first part of the series we evaluated expressions to get the result, in the second part we parsed the expression with our own grammar. Today we will expand on the topic, we will introduce more types and more operations. Variables are left for the next installment as this part will be long enough without them anyway.

As always – complete example is available on Github and its structure is pretty much similar to the first simple version of our ANTLR based expression evaluator. And what will we do today?

• We will expand our numbers from integers to floating point (implemented with BigDecimals).
• We will add strings and booleans types too, along with relational operators (comparing).
• Relation operators can be written as >= but also as GE which is extremely handy when expressions are part of XML configuration. In addition to this, keywords will be case insensitive.

We will start introducing the grammar changes from the end of the file to the beginning – you can download our new grammar in its wholeness.

Case-insensitive keywords

It would be cool if there was some easy way how to say to ANTLR that some particular keyword (string literal in the grammar) is case insensitive – as there are many languages that use this way. But there no magical switch, so we have to help ourselves with tiny parts of token rules called fragments. Following part will go to the very end of the grammar file.

fragment DIGIT : [0-9];

fragment A : [aA];
fragment B : [bB];
fragment C : [cC];
fragment D : [dD];
fragment E : [eE];
fragment F : [fF];
fragment G : [gG];
fragment H : [hH];
fragment I : [iI];
fragment J : [jJ];
fragment K : [kK];
fragment L : [lL];
fragment M : [mM];
fragment N : [nN];
fragment O : [oO];
fragment P : [pP];
fragment Q : [qQ];
fragment R : [rR];
fragment S : [sS];
fragment T : [tT];
fragment U : [uU];
fragment V : [vV];
fragment W : [wW];
fragment X : [xX];
fragment Y : [yY];
fragment Z : [zZ];

Now when we want case-insensitive keyword we will write O R instead of ‘or’ like this:

OP_OR: O R | '||';

But we will get to operators later, let’s do the literals and company first.

Literals and whitespaces

We will support boolean literals as a word and a letter (blame my recent experience with R language). Number literals must cover floating point numbers too. And finally there are strings here as well. White spaces are without any change at all:

BOOLEAN_LITERAL: T R U E | T
    | F A L S E | F
    ;

NUMERIC_LITERAL : DIGIT+ ( '.' DIGIT* )? ( E [-+]? DIGIT+ )?
    | '.' DIGIT+ ( E [-+]? DIGIT+ )?
    ;

STRING_LITERAL : '\'' ( ~'\'' | '\'\'' )* '\'';

WS: [ \t\r\n]+ -> skip;

Operators

Nothing special here, we just add more of them.

OP_LT: L T | '<'; OP_GT: G T | '>';
OP_LE: L E | '<='; OP_GE: G E | '>=';
OP_EQ: E Q | '=' '='?;
OP_NE: N E | N E Q | '!=' | '<>';
OP_AND: A N D | '&&';
OP_OR: O R | '||';
OP_NOT: N O T | '!';
OP_ADD: '+';
OP_SUB: '-';
OP_MUL: '*';
OP_DIV: '/';
OP_MOD: '%';

Equality can be written both as in SQL or as in Java, because there is no assignment statement in our grammar. All relational and logical operators have both the symbols and keywords. If you miss XOR you can add it yourself, of course.

And the expression rule…

Finally we got to the expression rule, which got a bit richer:

result: expr;

expr: STRING_LITERAL # stringLiteral
    | BOOLEAN_LITERAL # booleanLiteral
    | NUMERIC_LITERAL # numericLiteral
    | op=('-' | '+') expr # unarySign
    | expr op=(OP_MUL | OP_DIV | OP_MOD) expr # arithmeticOp
    | expr op=(OP_ADD | OP_SUB) expr # arithmeticOp
    | expr op=(OP_LT | OP_GT | OP_EQ | OP_NE | OP_LE | OP_GE) expr # comparisonOp
    | OP_NOT expr # logicNot
    | expr op=(OP_AND | OP_OR) expr # logicOp
    | '(' expr ')' # parens
    ;

You may notice one additional rule – result. We will use this for a single special reason covered later. Now is the time to generate the classes from the grammar and then to reimplement the visitor class.

BTW: Our new version of the calculator visitor will not extend ExprBaseVisitor<Integer> with parameter (Integer) anymore as the result may be of any supported type – String, BigDecimal or Boolean. And we don’t know what will be the result. So we just don’t state the parameterized type at all.

Implementing literals

Before we implement, we should have some expectations – and that means tests. My test class is not perfect one case per test, but it does the job.

    @Test
    public void booleanLiterals() {
        assertEquals(expr("t"), true);
        assertEquals(expr("True"), true);
        assertEquals(expr("f"), false);
        assertEquals(expr("faLSE"), false);
    }

    @Test
    public void stringLiteral() {
        assertEquals(expr("''"), "");
        assertEquals(expr("''''"), "'");
        assertEquals(expr("'something'"), "something");
    }

    @Test
    public void numberLiterals() {
        assertEquals(expr("5"), new BigDecimal("5"));
        assertEquals(expr("10.35"), new BigDecimal("10.35"));
    }

Method expr in test is still implemented like before. Let’s focus on the visitor implementation now. The parts we need for this test to work are here:

    @Override
    public String visitStringLiteral(StringLiteralContext ctx) {
        String text = ctx.STRING_LITERAL().getText();
        text = text.substring(1, text.length() - 1)
            .replaceAll("''", "'");
        return text;
    }

    @Override
    public Boolean visitBooleanLiteral(BooleanLiteralContext ctx) {
        return ctx.BOOLEAN_LITERAL().getText().toLowerCase().charAt(0) == 't';
    }

    @Override
    public BigDecimal visitNumericLiteral(NumericLiteralContext ctx) {
        String text = ctx.NUMERIC_LITERAL().getText();
        return stringToNumber(text);
    }

    private BigDecimal stringToNumber(String text) {
        BigDecimal bigDecimal = new BigDecimal(text);

        return bigDecimal.scale() < 0
            ? bigDecimal.setScale(0, roundingMode)
            : bigDecimal;
    }

Arithmetic operations

Now we will implement arithmetics with BigDecimals, including unary signs and parentheses.

    @Test
    public void arithmeticTest() {
        assertEquals(expr("5+5.1"), new BigDecimal("10.1"));
        assertEquals(expr("5-5.1"), new BigDecimal("-0.1"));
        assertEquals(expr("0.3*0.1"), new BigDecimal("0.03"));
        assertEquals(expr("0.33/0.1"), new BigDecimal("3.3"));
        assertEquals(expr("1/3"), new BigDecimal("0.333333333333333"));
        assertEquals(expr("10%3"), new BigDecimal("1"));
    }

    @Test
    public void unarySignTest() {
        assertEquals(expr("-5"), new BigDecimal("-5"));
        assertEquals(expr("-+-5"), new BigDecimal("5"));
        assertEquals(expr("-(3+5)"), new BigDecimal("-8"));
    }

The implementation in the Visitor respects our defined maximal scale, which is very important for cases like 1/3. Without scale and rounding set this would throw an error.

    public static final int DEFAULT_MAX_SCALE = 15;
    private int maxScale = DEFAULT_MAX_SCALE;
    private int roundingMode = BigDecimal.ROUND_HALF_UP;

    @Override
    public BigDecimal visitArithmeticOp(ExprParser.ArithmeticOpContext ctx) {
        BigDecimal left = (BigDecimal) visit(ctx.expr(0));
        BigDecimal right = (BigDecimal) visit(ctx.expr(1));
        return bigDecimalArithmetic(ctx, left, right);
    }

    private BigDecimal bigDecimalArithmetic(ExprParser.ArithmeticOpContext ctx, BigDecimal left, BigDecimal right) {
        switch (ctx.op.getType()) {
            case OP_ADD:
                return left.add(right);
            case OP_SUB:
                return left.subtract(right);
            case OP_MUL:
                return left.multiply(right);
            case OP_DIV:
                return left.divide(right, maxScale, roundingMode).stripTrailingZeros();
            case OP_MOD:
                return left.remainder(right);
            default:
                throw new IllegalStateException("Unknown operator " + ctx.op);
        }
    }

    @Override
    public BigDecimal visitUnarySign(UnarySignContext ctx) {
        BigDecimal result = (BigDecimal) visit(ctx.expr());
        boolean unaryMinus = ctx.op.getText().equals("-");
        return unaryMinus
            ? result.negate()
            : result;
    }

    @Override
    public Object visitParens(ParensContext ctx) {
        return visit(ctx.expr());
    }

We may appreciate scale 15 for interim results, but maybe we want lower scale for final result. Let’s do that now:

Result rule with different scale

Let’s say we require just scale of 6 for final results. We will implement result rule for that:

    public static final int DEFAULT_MAX_RESULT_SCALE = 6;
    private int maxResultScale = DEFAULT_MAX_RESULT_SCALE;

    /** Maximum BigDecimal scale used during computations. */
    public ExpressionCalculatorVisitor maxScale(int maxScale) {
        this.maxScale = maxScale;
        return this;
    }

    /** Maximum BigDecimal scale for result. */
    public ExpressionCalculatorVisitor maxResultScale(int maxResultScale) {
        this.maxResultScale = maxResultScale;
        return this;
    }

    @Override
    public Object visitResult(ExprParser.ResultContext ctx) {
        Object result = visit(ctx.expr());
        if (result instanceof BigDecimal) {
            BigDecimal bdResult = (BigDecimal) result;
            if (bdResult.scale() > maxResultScale) {
                result = bdResult.setScale(maxResultScale, roundingMode);
            }
        }
        return result;
    }

We also introduced two methods setting the maximal interim and result scale. Both of them return this, so they can be used right after constructor of the ExpressionCalculatorVisitor. One last change is required in ExpressionUtils – instead of calling expr rule on parser we need to use result rule. Otherwise the util class looks exactly like before.

Of course we have to fix the test and for 1/3 expect just 0.333333 instead of 15 digits like before.

Logical operations

After previous problems this is a piece of cake. First the test:

    @Test
    public void logicalOperatorTest() {
        assertEquals(expr("F && F"), false);
        assertEquals(expr("F && T"), false);
        assertEquals(expr("T and F"), false);
        assertEquals(expr("T AND T"), true);
        assertEquals(expr("F || F"), false);
        assertEquals(expr("F || T"), true);
        assertEquals(expr("T or F"), true);
        assertEquals(expr("T OR T"), true);
        assertEquals(expr("!T"), false);
        assertEquals(expr("not T"), false);
        assertEquals(expr("!f"), true);
    }

And the visitor implementation:

    @Override
    public Boolean visitLogicOp(ExprParser.LogicOpContext ctx) {
        boolean left = (boolean) visit(ctx.expr(0));

        switch (ctx.op.getType()) {
            case OP_AND:
                return left && booleanRightSide(ctx);
            case OP_OR:
                return left || booleanRightSide(ctx);
            default:
                throw new IllegalStateException("Unknown operator " + ctx.op);
        }
    }

    private boolean booleanRightSide(ExprParser.LogicOpContext ctx) {
        return (boolean) visit(ctx.expr(1));
    }

    @Override
    public Boolean visitLogicNot(ExprParser.LogicNotContext ctx) {
        return !(Boolean) visit(ctx.expr());
    }

Relational operators

Let’s do some comparisons and (non) equalities. Test first:

    @Test
    public void relationalOperatorTest() {
        assertEquals(expr("1 > 0.5"), true);
        assertEquals(expr("1 > 1"), false);
        assertEquals(expr("1 >= 0.5"), true);
        assertEquals(expr("1 >= 1"), true);
        assertEquals(expr("5 == 5"), true);
        assertEquals(expr("5 != 5"), false);
        assertEquals(expr("'a' > 'b'"), false);
        assertEquals(expr("'a' >= 'b'"), false);
        assertEquals(expr("'a' < 'b'"), true);
        assertEquals(expr("'a' <= 'b'"), true);
        assertEquals(expr("true == true"), true);
        assertEquals(expr("true == f"), false);
        assertEquals(expr("true eq t"), true);
    }

Again, I realize that these should be many separate tests and the coverage of cases is also not that great, but let’s move on to the implementation:

    @Override
    public Boolean visitComparisonOp(ExprParser.ComparisonOpContext ctx) {
        Comparable left = (Comparable) visit(ctx.expr(0));
        Comparable right = (Comparable) visit(ctx.expr(1));
        int operator = ctx.op.getType();
        if (left == null || right == null) {
            return left == null && right == null && operator == OP_EQ
                || (left != null || right != null) && operator == OP_NE;
        }

        //noinspection unchecked
        int comp = left.compareTo(right);
        switch (operator) {
            case OP_EQ:
                return comp == 0;
            case OP_NE:
                return comp != 0;
            case OP_GT:
                return comp > 0;
            case OP_LT:
                return comp < 0; case OP_GE: return comp >= 0;
            case OP_LE:
                return comp <= 0;
            default:
                throw new IllegalStateException("Unknown operator " + ctx.op);
        }
    }

Nothing special here – we utilize the fact that Strings, Booleans and BigDecimals are all comparable.

Conclusion

What did we see and what more can we do? For the sheer scope of the changes we postponed the variables for the next part of the series. Of course, variables (and functions!) are very important for expression evaluation, otherwise we’re talking about constant result for each expression anyway, right?

We have created flexible grammar that is kinda mix between SQL and Java. Of course, you may not like too many options for all the operators, but in our context it doesn’t pose any problem. It might have – in the context of general programming language (e.g. = vs == operators).

Another thing is that numbers are BigDecimals – always. This is kinda Groovy-like, where 3 / 2 is not 1 as Java programmer would expect and this division is also much slower than integer division. We may introduce integers and support smart division based on the context (like Java does after all, except that FP is IEEE 754 and not BigDecimal-based). But not now.

Now you can download the complete example – and if you don’t know how to download part of the repo, you may try this command:

svn export https://github.com/virgo47/litterbin/trunk/demos/antlr-expr/src/main/java/expr2/

Tests are in src/test of course. See you next with variables and maybe even functions.