Generate boolean truth table
Problem Description
Implement a function that, given a string boolean expression, outputs a complete truth table.
Expression Syntax
- Variables: Single uppercase letters A–Z.
- Operators:
!(unary NOT)- Adjacency (implicit AND)
+(binary OR)
- Parentheses:
()are allowed. - Spaces: Ignored.
Operator Precedence
! > AND > + (NOT has highest precedence, then AND, then OR).
AND and OR operators are left-associative.
Requirements
- Parsing and Validation: Parse the expression, handling implicit AND. Validate all tokens.
- Variable Extraction: Extract all distinct variables and sort them alphabetically.
- Truth Assignment Enumeration: Enumerate all
2^npossible assignments forndistinct variables. - Evaluation: Evaluate the expression for each assignment.
- Output: Print rows as variable values followed by the expression’s result.
Example
Input: !AB + B!D + !(CD)
Output: A truth table over variables A, B, C, D with all 16 combinations, showing the result of the expression for each.
Discussion Points
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.
AI interview prep
Core dilemma
Accurately parsing a boolean expression with implicit operators and complex precedence rules, then efficiently evaluating it across all possible variable assignments.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Generate boolean truth table
Problem Description
Implement a function that, given a string boolean expression, outputs a complete truth table.
Expression Syntax
- Variables: Single uppercase letters A–Z.
- Operators:
!(unary NOT)- Adjacency (implicit AND)
+(binary OR)
- Parentheses:
()are allowed. - Spaces: Ignored.
Operator Precedence
! > AND > + (NOT has highest precedence, then AND, then OR).
AND and OR operators are left-associative.
Requirements
- Parsing and Validation: Parse the expression, handling implicit AND. Validate all tokens.
- Variable Extraction: Extract all distinct variables and sort them alphabetically.
- Truth Assignment Enumeration: Enumerate all
2^npossible assignments forndistinct variables. - Evaluation: Evaluate the expression for each assignment.
- Output: Print rows as variable values followed by the expression’s result.
Example
Input: !AB + B!D + !(CD)
Output: A truth table over variables A, B, C, D with all 16 combinations, showing the result of the expression for each.
Discussion Points
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.