Generate boolean truth table

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.