cswork / libraryOpen practice workspace

Coding questions · Kickoff

Generate boolean truth table

This question evaluates understanding of parsing, boolean expression semantics, and algorithmic enumeration, including tokenization, operator precedence, exhaustive evaluation over variable assignments, and handling of invalid inputs.

Implement a function that, given a string boolean expression, outputs a complete truth table. The expression syntax is: variables are single uppercase letters A–Z; operators are '!' (unary NOT), adjacency (implicit AND), and '+' (binary OR); parentheses '()' are allowed; spaces are ignored. Use precedence: '!' > AND > '+', with left-associative AND and OR. Requirements: (1) Parse the expression (handle implicit AND) and validate tokens; (2) Extract all distinct variables, sort them alphabetically; (3) Enumerate all 2^n assignments and evaluate the expression for each; (4) Print rows as variable values followed by the expression’s result. Example: input "!AB + B!D + !(CD)" should produce a table over A,B,C,D with all 16 combinations. Describe your parsing approach (e.g., shunting-yard or recursive descent), data structures used, and analyze time/space complexity. Discuss edge cases such as unmatched parentheses, unknown symbols, or empty input.

Boolean Truth Table Generator

Examples

Example 1

Input: ('A+B',)
Output: {'variables': ['A', 'B'], 'rows': [[False, False, False], [False, True, True], [True, False, True], [True, True, True]]}

Explanation: Simple OR.

Example 2

Input: ('!A',)
Output: {'variables': ['A'], 'rows': [[False, True], [True, False]]}

Explanation: Unary NOT.

Hints

  1. Choose a representation that makes the core operation simple.
  2. Handle empty and boundary inputs before the main algorithm.