2. How it works

1. Tokenisation

• Input is split into tokens. These tokens are internal representations of the input.
• Tokens are either operators, variables, or brackets.
• For example, the input A & ! B would be tokenised into [A, AND, NOT, B].

2. Parsing

• Tokens are parsed into postfix or Reverse Polish notation, using the (slightly modified) Shunting-yard algorithm.
• Postfix notation removes the need for brackets, and makes it easier to evaluate the expression. In this notation, the operator is placed before the operands (rather than in between them).
• Our tokenised list, [A, AND, NOT, B] would be parsed into [A, B, NOT, AND].

3. AST

• The parsed tokens are then converted into an AST (Abstract Syntax Tree). This is so that the expression can be evaluated and easily traversed.
• An AST consists of several nodes, each with children nodes (0, 1, or 2 depending on its type). Each node represents an operator or variable.
• Our parsed list, [A, B, NOT, AND], would be converted into the following AST:

  AND
  ├── A
  └── NOT
      └── B
  

4. Evaluation

• Finally, the AST is evaluated, and a truth table is printed out for the expression.
• Evaluation simply traverses the AST and evaluates each node recursively, using the values of its children.
• Each expression is evaluated using every possible set of inputs which is then collated into a truth table.