Expression compiler

I recently had the need to evaluate expressions. The expression is represented as a string and can contain variable names, integers, string constants, and any operations on them.

Example:
expression: "x + 10 == 5 * y / (1 + z * 2)";
you must be able to evaluate this expression for any x, y, and z values.

And of course, the priorities of the operators must be taken into account.
')
For the solution, you need to make a compiler, which builds an “Computable Expression” object on the line. This object will have a “calculate for these variable values” method.

Solution in Java, but can be easily translated into other languages.



First about what we get at the output after compiling the string. This is an Expression object (expression) with the execute method (Map vars). The object is a tree, in nodes the operators on the leaves are variables or constants. By example, I think everything is clear:

"X + 1 <y / (1 + 2)" =>

[ "<" ]
[ "+" ]
[ x ]
[ 1 ]
[ "/" ]
[ y ]
[ "+" ]
[ 1 ]
[ 2 ]


The nodes of this tree are:

• Binary - operator and two operands (+, -, ==, etc.)
• Unary - operator and one operand (negation and unary minus)
• Variable - leaf node with variable name
• Line
• Number

To calculate you need to recursively bypass the tree by calculating the values ​​in the nodes. For a variable, the string and the number of calculations are trivial, for the binary and unary nodes, you must first calculate the values ​​of the operands and simply apply the operator to them.

Now the most interesting is compilation.
I will try to tell it is clear for habra people unfamiliar with finite automata and grammars.
For clarity, let us examine the simplest expressions, which can contain only numbers, “+”, “-” signs and brackets. For example, 10 - (3 + 2 - (10 - 5)).

We write formally:

: [+ / - ] *
: | ()


Pronounced like this:
The expression is a term, plus or minus term (this “plus or minus term” can be repeated from zero to any number of times).
The term is a number or expression in brackets.

The processing algorithm looking at the formal record is as follows:

:
X1 = ()

«+» «-»
X2 = ();
X1 = ( «+» «-», X1, X2)

X1


:
'('
X = ()
X






The following compiler uses a more complex grammar:

S0 : S1 [ || S1] *
S1: S2 [ && S2] *
S2: S3 | ! S3
S3: S4 | S4 == S4 | S4 != S4 | S4 <= S4 | S4 < S4 | S4 >= S4 | S4 > S4
S4: S5 [«+» «-» S5] *
S5: S6 [«*» «.» S6] *
S6: 'string' | var | number | null | (S0) | - var | - number | - (S0)


And the actual code:

import java.util.Map;

/**
*
*/
public abstract class Expression {

/** */
public abstract Object execute(Map< String , Object> values) throws Exception;


/** — «» */
static class Num extends Expression {
private final long value ;

public Num( long x) {
value = x;
}

@Override
public Object execute(Map< String , Object> values) {
return value ;
}
}

/** — «» */
static class Str extends Expression {
private final String value ;

public Str( String x) {
value = x;
}

@Override
public Object execute(Map< String , Object> values) {
return value ;
}
}

/** — «» */
static class Var extends Expression {
private final String name;

public Var( String name) {
this .name = name;
}

@Override
public Object execute(Map< String , Object> values) {
return values. get (name);
}
}


/** — « » */
static class Unary extends Expression {
private final Expression expr;
private final boolean not;

public Unary(Expression e, String oper) {
expr = e;
not = "!" .equals(oper);
}

@Override
public Object execute(Map< String , Object> values) throws Exception {
Object o = expr.execute(values);
if (not)
return !(Boolean)o;
else
return -(Long)o;
}
}



/** — « » */
static class Binary extends Expression {
private final Expression x1;
private final Expression x2;
private final String op;

public Binary(Expression x1, Expression x2, String op) {
this .x1 = x1;
this .x2 = x2;
this .op = op;
}

@Override
public Object execute(Map< String , Object> values) throws Exception {
Object o1 = x1.execute(values);
Object o2 = x2.execute(values);

Class type = commonType(o1, o2);

if (type == String . class )
return execStr(o1 != null ? o1.toString() : null , o2 != null ? o2.toString() : null );
else if (type == Long. class )
return execNum((Long)o1, (Long)o2);
else
return execBool((Boolean)o1, (Boolean)o2);
}

private Class commonType(Object o1, Object o2) {
if (o1 == null || o2 == null || o1 instanceof String || o2 instanceof String )
return String . class ;
if (o1 instanceof Long && o2 instanceof Long)
return Long. class ;
return Boolean. class ;
}

private Object execStr( String s1, String s2) throws Exception {
if ( "==" .equals(op))
return (Boolean)(s1 == null ? s2 == null : s1.equals(s2));
if ( "!=" .equals(op))
return (Boolean)(s1 == null ? s2 != null : !s1.equals(s2));
if ( "+" .equals(op))
return ( String )(s1 == null ? s2 : s1 + (s2 == null ? "" : s2));
throw new Exception( "Illegal String operator: " + op);
}

private Object execBool(boolean q1, boolean q2) throws Exception {
if ( "&&" .equals(op))
return q1 && q2;
if ( "||" .equals(op))
return q1 || q2;
if ( "==" .equals(op))
return q1 == q2;
if ( "!=" .equals(op))
return q1 != q2;
throw new Exception( "Illegal Boolean operator: " + op);
}

private Object execNum( long n1, long n2) throws Exception {
if ( "==" .equals(op))
return (Boolean)(n1 == n2);
if ( "!=" .equals(op))
return (Boolean)(n1 != n2);
if ( "<" .equals(op))
return (Boolean)(n1 < n2);
if ( "<=" .equals(op))
return (Boolean)(n1 <= n2);
if ( ">" .equals(op))
return (Boolean)(n1 > n2);
if ( ">=" .equals(op))
return (Boolean)(n1 >= n2);
if ( "+" .equals(op))
return (Long)(n1 + n2);
if ( "-" .equals(op))
return (Long)(n1 - n2);
if ( "*" .equals(op))
return (Long)(n1 * n2);
if ( "/" .equals(op))
return (Long)(n1 / n2);

throw new Exception( "Illegal Long operator: " + op);
}
}
}

* This source code was highlighted with Source Code Highlighter .

And the compiler itself:

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;
import static org.junit.Assert.assertTrue;

/** */
public class ExpressionBuilder {

private String expression; //
private int p = 0; //

public static Expression build( String expression) {
ExpressionBuilder builder = new ExpressionBuilder(expression);
builder.skip( " " );
Expression expr = builder.build(0);
return expr;
}

private ExpressionBuilder( String expression) {
this .expression = expression;
}


/** */
Expression build( int state) {
if (lastState(state)) {
Expression ex = null ;
boolean isMinus = startWith( "-" );
if (isMinus)
skip( "-" );

if (startWith( "(" )) {
skip( "(" );
ex = build(0);
skip( ")" );
}
else
ex = readSingle();
if (isMinus)
ex = new Expression.Unary(ex, "-" );
return ex;
}

boolean unarNot = state == 2 && startWith( "!" );
if (unarNot)
skip( "!" );

/* */
Expression a1 = build(state+1);
if (unarNot)
a1 = new Expression.Unary(a1, "!" );

//
String op = null ;
while ((op = readStateOperator(state)) != null ) {
Expression a2 = build(state + 1);
a1 = new Expression.Binary(a1, a2, op);

}
return a1;
}

private static String [][] states = new String [][] {
{ "||" },
{ "&&" },
{ "!" },
{ "<=" , ">=" , "==" , "!=" , "<" , ">" },
{ "+" , "-" },
{ "*" , "/" },
null
};

private boolean lastState( int s) {
return s+1 >= states.length;
}

private boolean startWith( String s) {
return expression.startsWith(s, p);
}

private void skip( String s) {
if (startWith(s))
p+= s.length();
while (p < expression.length() && expression.charAt(p) == ' ' )
p++;
}


private String readStateOperator( int state) {
String [] ops = states[state];
for ( String s : ops) {
if (startWith(s)) {
skip(s);
return s;
}
}
return null ;
}

/**
* "" ( , )
* @return
*/
private Expression readSingle() {
int p0 = p;
//
if (startWith( "'" ) || startWith( "\"" )) {
boolean q2 = startWith( "\"" );
p = expression.indexOf(q2 ? '"' : '\'' , p+1);
Expression ex = new Expression.Str(expression.substring(p0+1, p));
skip(q2 ? "\"" : "'" );
return ex;
}

// =>
while (p < expression.length()) {
if (!(Character.isLetterOrDigit(expression.charAt(p))))
break ;
p++;
}

Expression ex = null ;
if (p > p0) {
String s = expression.substring(p0, p);
skip( " " );
try {
//
long x = Long.parseLong(s);
return new Expression.Num(x);
}
catch (Exception e){}

if ( "null" .equals(s))
return new Expression.Str( null );

// , null —
return new Expression.Var(s);

}
return null ;
}





// -
public ExpressionBuilder(){}

@Test
public void testBuilder() throws Exception {
String str = "qwerty" ;
long n1 = 10;
long n2 = 5;

Map< String , Object> map = new HashMap< String , Object>();
map.put( "str" , "str" );
map.put( "n1" , n1);
map.put( "n2" , n2);

Expression e = ExpressionBuilder.build( "str != 'qwerty' && n1 / n2 >= 3 * (n2 + 10 / n1 * (2+3))" );
Boolean a = (Boolean) e.execute(map);
Boolean b = ! "qwerty" .equals(str) && n1 / n2 >= 3 * (n2 + 10 / n1 * (2+3));
assertTrue(a == b);
}
}


* This source code was highlighted with Source Code Highlighter .

Thanks for attention!