Practice: Terminal and Non-Terminal in a Boolean Language

true, false, and, or and not; sort the classes, then evaluate one sentence.

A language of true, false, and, or and not is small enough to build with the Interpreter pattern in five classes, and this exercise asks you to sort them and evaluate a sentence. Answer before opening the solution.

The classes are TrueLiteral, FalseLiteral, And, Or and Not. Each has an interpret method that returns a boolean, and And and Or hold two parts, Not one.

Which classes are terminal expressions, and which are non-terminal?
Draw the tree for not (true and false) or false, where not applies before or.
What does the sentence evaluate to?

Show a solution

Each class and its kind
Class	Kind	Holds
`TrueLiteral`	Terminal	Nothing
`FalseLiteral`	Terminal	Nothing
`And`	Non-terminal	Two parts
`Or`	Non-terminal	Two parts
`Not`	Non-terminal	One part

The tree for not (true and false) or false

from abc import ABC, abstractmethod


class BooleanExpression(ABC):
    @abstractmethod
    def interpret(self) -> bool: ...


class TrueLiteral(BooleanExpression):
    def interpret(self) -> bool:
        return True


class FalseLiteral(BooleanExpression):
    def interpret(self) -> bool:
        return False


class And(BooleanExpression):
    def __init__(self, left: BooleanExpression, right: BooleanExpression) -> None:
        self.left = left
        self.right = right

    def interpret(self) -> bool:
        return self.left.interpret() and self.right.interpret()


class Or(BooleanExpression):
    def __init__(self, left: BooleanExpression, right: BooleanExpression) -> None:
        self.left = left
        self.right = right

    def interpret(self) -> bool:
        return self.left.interpret() or self.right.interpret()


class Not(BooleanExpression):
    def __init__(self, operand: BooleanExpression) -> None:
        self.operand = operand

    def interpret(self) -> bool:
        return not self.operand.interpret()


sentence = Or(Not(And(TrueLiteral(), FalseLiteral())), FalseLiteral())
print("not (true and false) or false =", sentence.interpret())

OutputRan with python:3.12-slim (Python 3.12.13)

not (true and false) or false = True

`Not` is non-terminal with a single part.

true and false is false, not makes it true, and true or false is true. Not is the one people most often call terminal, because it holds a single part; what makes an expression non-terminal is holding any expression at all, not holding two.

← → move through sections and cards