Early exit boolean expression parser in Python

2017-07-18 (Tuesday) | 600 words (~3 minutes reading)

I wanted to have a go at rush-implementing a boolean expression parser with early exit, i.e. that it will not bother evaluating the right hand side of an expression like 0&(1|0) and just return false once it sees 0&.

Here’s an attempt in Python. It deals with nested expressions by recursion and “collapsing” the evaluation into a 0 or 1 token to continue evaluating from there. It uses a similar approach to handle !.

from typing import List, Union

VALID_TOKENS = ["0", "1", "|", "&", "^", "!", "(", ")"]

def eval_bool_expr(expr: Union[List[str], str]) -> bool:
    expr = [t.strip() for t in expr if t.strip() in VALID_TOKENS]
    if expr == ["1"]:
        return True
    elif expr == ["0"]:
        return False
    elif expr[0] == "!":
        if expr[1] == "(":
            nest = 1
            sub = []
            for i, t in enumerate(expr[2:]):
                if t == "(":
                    nest += 1
                if t == ")":
                    nest -= 1

                if nest > 0:
                    sub.append(t)
                else:
                    sub_eval = ["1"] if eval_bool_expr(sub) else ["0"]
                    expr = ["!"] + sub_eval + expr[3+i:]
                    break

        if expr[1] == "0":
            expr[1] = "1"
        elif expr[1] == "1":
            expr[1] = "0"
        else:
            raise ValueError("Invalid boolean expression", expr)

        return eval_bool_expr(expr[1:])
    elif expr[0] == "(":
        nest = 1
        sub = []
        for i, t in enumerate(expr[1:]):
            if t == "(":
                nest += 1
            if t == ")":
                nest -= 1

            if nest > 0:
                sub.append(t)
            else:
                sub_eval = ["1"] if eval_bool_expr(sub) else ["0"]
                return eval_bool_expr(sub_eval + expr[2 + i:])
    elif len(expr) > 2:
        if expr[0] == "0":
            if expr[1] == "&":
                return False
            elif expr[1] == "|":
                return eval_bool_expr(expr[2:])
            elif expr[1] == "^":
                return eval_bool_expr(expr[2:])
        elif expr[0] == "1":
            if expr[1] == "&":
                return eval_bool_expr(expr[2:])
            elif expr[1] == "|":
                return True
            elif expr[1] == "^":
                return not eval_bool_expr(expr[2:])
    else:
        raise ValueError("Invalid boolean expression", expr)


if __name__ == "__main__":
    assert eval_bool_expr("1") is True
    assert eval_bool_expr("0") is False

    assert eval_bool_expr("!1") is False
    assert eval_bool_expr("!0") is True

    assert eval_bool_expr("1&1") is True
    assert eval_bool_expr("1&0") is False
    assert eval_bool_expr("0&0") is False
    assert eval_bool_expr("1|1") is True
    assert eval_bool_expr("1|0") is True
    assert eval_bool_expr("0|0") is False

    assert eval_bool_expr("1^0") is True
    assert eval_bool_expr("0^1") is True
    assert eval_bool_expr("0^0") is False
    assert eval_bool_expr("1^1") is False

    assert eval_bool_expr("!1&1") is False
    assert eval_bool_expr("1&!0") is True
    assert eval_bool_expr("!0&!0") is True
    assert eval_bool_expr("!1|1") is True
    assert eval_bool_expr("!1|0") is False
    assert eval_bool_expr("0|!0") is True

    assert eval_bool_expr("(1)") is True
    assert eval_bool_expr("(0)") is False

    assert eval_bool_expr("(!1)") is False
    assert eval_bool_expr("(!0)") is True

    assert eval_bool_expr("(1&1)") is True
    assert eval_bool_expr("(1&0)") is False
    assert eval_bool_expr("(0&0)") is False
    assert eval_bool_expr("(1|1)") is True
    assert eval_bool_expr("(1|0)") is True
    assert eval_bool_expr("(0|0)") is False

    assert eval_bool_expr("(1^0)") is True
    assert eval_bool_expr("(0^1)") is True
    assert eval_bool_expr("(0^0)") is False
    assert eval_bool_expr("(1^1)") is False

    assert eval_bool_expr("(!1&1)") is False
    assert eval_bool_expr("(1&!0)") is True
    assert eval_bool_expr("(!0&!0)") is True
    assert eval_bool_expr("(!1|1)") is True
    assert eval_bool_expr("(!1|0)") is False
    assert eval_bool_expr("(0|!0)") is True

    assert eval_bool_expr("(0|1)&1") is True
    assert eval_bool_expr("(0|1)&(1&1)") is True
    assert eval_bool_expr("(0|1)&(1|1)") is True
    assert eval_bool_expr("(0|1)&(1|0)") is True
    assert eval_bool_expr("(0|1)&(0|0)") is False
    assert eval_bool_expr("(0|1)|(0|0)") is True
    assert eval_bool_expr("(0&1)&(1|1)") is False

    assert eval_bool_expr("(1)|0") is True
    assert eval_bool_expr("!(1)|0") is False
    assert eval_bool_expr("!(1|0)&0") is False
    assert eval_bool_expr("!(1|0)&!0") is False
    assert eval_bool_expr("!(0&(1^1))&!0") is True

    assert eval_bool_expr("(1|1&(0|1))&1") is True
    assert eval_bool_expr("(((((1&1)&1)&1)&1)&1)") is True
    assert eval_bool_expr("(((((1|0)|1)|0)|1)|0)") is True
    assert eval_bool_expr("(((((1|0)|1)&0)|1)|0)") is True
    assert eval_bool_expr("(((((1|0)|1)&0)|1)&0)") is False

Tech mentioned