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.