Generate boolean truth table

Q: 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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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: (

Parse the expression (handle implicit AND) and validate tokens; (
Extract all distinct variables, sort them alphabetically; (
Enumerate all 2^n assignments and evaluate the expression for each; (
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.

Generate boolean truth table

Overview

Comments (0)