How can we evaluate a boolean expression represented by a String in Kotlin?

Question

val exp = "( 0 == 1 && 10 > 11 ) || ( 10 < 9 ) && ( 10 == 10)"
val result: Boolean = evaluate(exp) //result = true/false

How can I write a simple program in Android (Kotlin) to evaluate the above string and get a boolean result? I DO NOT want to use a complete evaluator like JEL or JEval, Js Eval or any other library, as they are too large for this specific requirement.

Preconditions :
Operators supported : < > == && || 
Works only on digits

Also don't want to use ScriptEngineManager()

Note: The javax.script package is not available on Android.

Gabey

It will not be very fast, but you can use Kotlin Jsr 223. More examples here – Dyun

if you only need it for arithmetic operations, then search for a calculator library. Otherwise if you only use boolean operations you can parse everything by yourself easily, first convert parantheses to polish form and then parse it. – Hellhole

@Hellhole Do you have a good sample for boolean evaluators in Kotlin? – Gabey

If you're working with Android, I'd suggest Mozilla Rhino – Bung

I do not wan't to use any third party library. Would prefer pure Kotlin – Gabey

What's this for? What platform will it run on, how often, what performance is needed, where the expressions come from, whether any variables or other interpolation is needed, what the result will be used for, &c? – Heroworship

no variables, platform is android, the result is used for a normal if condition. The solution should not be dependent on any library. – Gabey

This is just not a simple problem and will require a lot of complicated code. – Afresh

Answer 1

The following parser is 100% stand-alone and needs no libraries whatsoever. Of course it can be improved in 1000 ways and one, but it shows the principle (and was fun to write).

sealed class Token
data class BooleanComposition(val c: Char) : Token()
data class NumberComparison(val c: Char) : Token()
data class Number(val value: Int) : Token()
object ParenLeft : Token()
object ParenRight : Token()
object EOF : Token()

sealed class Expression
data class BooleanTerm(val numExpr: NumberExpression) : Expression()
data class BooleanExpression(val b1: Expression, val cmp: (Boolean, Boolean) -> Boolean, val b2: Expression) : Expression()
data class NumberExpression(val n1: Int, val cmp: (Int, Int) -> Boolean, val n2: Int) : Expression()

fun and(b1: Boolean, b2: Boolean) = b1 && b2
fun or(b1: Boolean, b2: Boolean) = b1 || b2
fun lessThan(n1: Int, n2: Int): Boolean = n1 < n2
fun greaterThan(n1: Int, n2: Int): Boolean = n1 > n2
fun equal(n1: Int, n2: Int): Boolean = n1 == n2

fun scan(inputString: String): List<Token> = sequence {
    var index = 0
    while (index < inputString.length) {
        val c = inputString[index]
        if (c == '&' || c == '|' || c == '=') {
            check(inputString[++index] == c)
        }
        when (c) {
            in '0'..'9' -> {
                var end = index
                while (end < inputString.length && inputString[end].isDigit()) {
                    end += 1
                }
                val numToken = Number(inputString.substring(index, end).toInt())
                index = end - 1
                yield(numToken)
            }
            '&', '|' -> yield(BooleanComposition(c))
            '=', '<', '>' -> yield(NumberComparison(c))
            '(' -> yield(ParenLeft)
            ')' -> yield(ParenRight)
            else -> check(c.isWhitespace())
        }
        index += 1
    }
    yield(EOF)
}.toList()

fun parse(inputTokens: List<Token>): Expression {
    var index = 0

    fun expression(): Expression {
        val lastExpression = when (val firstToken = inputTokens[index++]) {
            is ParenLeft -> {
                val nestedExpression = expression()
                val closingToken = inputTokens[index++]
                check(closingToken is ParenRight) { "Found $closingToken" }
                nestedExpression
            }
            is Number -> {
                val opToken = inputTokens[index++]
                check(opToken is NumberComparison)
                val op = when (opToken.c) {
                    '<' -> ::lessThan
                    '>' -> ::greaterThan
                    '=' -> ::equal
                    else -> error("Bad op $opToken")
                }
                val secondToken = inputTokens[index++]
                check(secondToken is Number)
                NumberExpression(firstToken.value, op, secondToken.value)
            }
            else -> error("Parse error on $firstToken")
        }

        return when (val lookAhead = inputTokens[index]) {
            is EOF, is ParenRight -> lastExpression // pushback
            is BooleanComposition -> {
                // use lookAhead
                index += 1
                val op = when (lookAhead.c) {
                    '&' -> ::and
                    '|' -> ::or
                    else -> error("Bad op $lookAhead")
                }
                val secondExpression = expression()
                BooleanExpression(lastExpression, op, secondExpression)
            }
            else -> error("Parse error on $lookAhead")
        }
    }

    return expression()
}

fun evaluate(expr: Expression): Boolean = when (expr) {
    is BooleanTerm -> evaluate(expr.numExpr)
    is BooleanExpression -> expr.cmp.invoke(evaluate(expr.b1), evaluate(expr.b2))
    is NumberExpression -> expr.cmp.invoke(expr.n1, expr.n2)
}

fun main() {
    // scan . parse . evaluate ("( 0 == 1 && 10 > 11 ) || ( 10 < 9 ) && ( 10 == 10)")
    val soExample = evaluate(parse(scan("( 0 == 1 && 10 > 11 ) || ( 10 < 9 ) && ( 10 == 10)")))
    println(soExample)
}

Hilten

Great answer, absurd there were only 3 upvotes! – Capful

This looks like it can be rewritten to parse logical string matching expressions like (*dog || *cat) && (food || eat* || nutrition) and solve a dozen questions about regexes on Stackoverflow. – Longshoreman

Answer 2

There's no built-in option for this on Android. You have to either use some 3rd-party interpreter or write your own.

I ended up using JEXL: it's pretty small (~ 400KB jar) and easy to use.

Gradle dependency:

compile 'org.apache.commons:commons-jexl3:3.1'

Usage (the wrapper I created):

class ExpressionEvaluator {
    private val jexlEngine = JexlBuilder().create()
    private val jexlContext = MapContext()

    fun evaluate(expression: String): Any? = try {
        val jexlExpression = jexlEngine.createExpression(expression)
        jexlExpression.evaluate(jexlContext)
    } catch (e: JexlException) {
        Timber.w("Could not evaluate expression '$expression'") //just logs
        null
    }

    fun evaluateAsBoolean(expression: String): Boolean? {
        val boolean = evaluate(expression) as? Boolean
        if (boolean == null) {
            Timber.w("Could not evaluate expression '$expression' as Boolean") //just logs
        }
        return boolean
    }
}

Feet