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