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.

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)
}