""" Enter a propositional logic formula to print it's truth table. Operators have several different formats. ., &, &&, /\, and, ∧, return true if both operands are true +, |, ||, \/, or, ∨ return true if any of the operands are true ->, =>, implies, ⇒ return false if first operand is true and second is false else it returns true <->, <=>, iff, ⇔ returns true if both operands are same xor, ^, ⊕ return true if only one of operands are true xnor, ⊙ return not xor nand, ⊼ return not and nor, ⊽ return not or ~, !, ¬ return 1 - operand ⊤ and ⊥ can be entered as T and F Operator precedence from highest to lowest is not nand xnor nor and xor or implies iff Input examples: T or F p xor q and r p && q | (w <=> z) Note: Unicode characters (like ⊽ ⊼) don't work on Sololearn """ from itertools import product import sys import codecs import unittest sys.stdout = codecs.getwriter('utf_16')( sys.stdout.buffer, 'strict' ) EOL = 0 NAME = 1 BOOL = 2 KEYWORD = 3 PAREN = 4 OP = 5 UNEXPECTED_CHAR = -1 NEED_OPERAND = -2 NEED_OPERATOR = -3 NO_OPEN_PARENTHESIS = -4 NO_CLOSE_PARENTHESIS = -5 kwlist = frozenset(('AND', 'OR', 'XOR', 'NAND', 'NOR', 'NOT', 'IMPLIES', 'IFF','XNOR')) OP_TO_KW = { '.': 'AND', '+': 'OR', '&': 'AND', '&&': 'AND', '|': 'OR', '||': 'OR', '~': 'NOT', '\\/': 'OR', '/\\': 'AND', '=>': 'IMPLIES', '->': 'IMPLIES', '<->': 'IFF', '<=>': 'IFF', '!': 'NOT', '^': 'XOR', } KW_TO_OP = { 'AND': '\u2227', 'OR': '\u2228', 'XOR': '\u2295', True: '\u22A4', False: '\u22A5', 'NOT': '\u00AC', 'IFF': '\u21D4', 'IMPLIES': '\u21D2', 'NAND': '\u22BC', 'NOR': '\u22BD', 'XNOR': '\u2299', } OP_TO_KW.update({value: key for key, value in KW_TO_OP.items()}) PREC = { 'NOT': 10, 'NAND': 9, 'XNOR': 8, 'NOR': 7, 'AND': 6, 'XOR': 5, 'OR': 4, 'IMPLIES': 3, 'IFF': 2, } def IMPLIES(p, q): return not p or q def IFF(p, q): return IMPLIES(p, q) and IMPLIES(q, p) def NAND(p, q): return not (p and q) def NOT(p): return not p def AND(p, q): return p and q def OR(p, q): return p or q def NOR(p, q): return not (p or q) def XOR(p, q): return AND(NAND(p, q), OR(p, q)) def XNOR(p, q): return not XOR(p, q) FUNCS = { 'AND': AND, 'OR': OR, 'NOR': NOR, 'XOR': XOR, 'XNOR': XNOR, 'IFF': IFF, 'IMPLIES': IMPLIES, 'NAND': NAND, } def syntaxerror(msg, line, i): print(msg) print(line) s = getattr(i, 'start', i) a = getattr(i, 'stop', s+1) - s print(('^'*a).rjust(a+s, ' ')) def iskeyword(k): return type(k) is str and k.upper() in kwlist def is_potential_id_start(c): return c.isalpha() or c == '_' def is_potential_id_char(c): return c.isalnum() or c == '_' def tokenize(inp): toks = [] i = 0 parens = 0 need_operand = True def readwhile(func): nonlocal i token = '' while i < len(inp) and func(inp[i]): token += inp[i] i += 1 return token while i < len(inp): readwhile(str.isspace) if is_potential_id_start(inp[i]): oldi = i value = inp[i] i += 1 value += readwhile(is_potential_id_char) if not iskeyword(value): if not need_operand: return NEED_OPERATOR, slice(oldi, i) need_operand = False if value == 'T': toks.append((BOOL, True)) elif value == 'F': toks.append((BOOL, False)) elif iskeyword(value): if value.upper() != 'NOT' and need_operand: return NEED_OPERAND, slice(oldi, i) elif value.upper() == 'NOT' and not need_operand: return NEED_OPERATOR, i need_operand = True toks.append((KEYWORD, value.upper())) else: toks.append((NAME, value)) elif inp[i] in '()': if inp[i] == '(' and not need_operand: return NEED_OPERATOR, i elif inp[i] == ')' and need_operand: return NEED_OPERAND, i toks.append((PAREN, inp[i])) parens += 1 if inp[i] == '(' else -1 if parens < 0: return NO_OPEN_PARENTHESIS, i i += 1 else: c1 = inp[i] if i + 1 < len(inp): c2 = inp[i+1] if i + 2 < len(inp): c3 = inp[i+2] three = c1 + c2 + c3 if three in OP_TO_KW: if need_operand: return NEED_OPERAND, slice(i, i+3) toks.append((KEYWORD, OP_TO_KW[three])) need_operand = True i += 3 continue two = c1 + c2 if two in OP_TO_KW: if need_operand: return NEED_OPERAND, slice(i, i+2) toks.append((KEYWORD, OP_TO_KW[two])) need_operand = True i += 2 continue if c1 in OP_TO_KW: tok = OP_TO_KW[c1] if need_operand and tok != 'NOT': return NEED_OPERAND, i elif not need_operand and tok == 'NOT': return NEED_OPERATOR, i toks.append((KEYWORD, tok)) i += 1 need_operand = True else: return UNEXPECTED_CHAR, i if need_operand: return EOL, slice(i - len(toks[-1][1]), i) if parens: return NO_CLOSE_PARENTHESIS, [i for i, j in enumerate(inp) if j == '('][-1] return toks def parse(tokens): out = [] op = [] for token in tokens: typ, value = token if typ in (BOOL, NAME): out.append(token) elif iskeyword(value): while op and op[-1][1] != '(' and op[-1][0] == KEYWORD and PREC[op[-1][1]] > PREC[value]: out.append(op.pop()) op.append(token) elif typ == PAREN: if value == '(': op.append(token) else: while op[-1][1] != '(': out.append(op.pop()) if op[-1][1] == '(': op.pop() else: out.append(token) out.extend(reversed(op)) return out def evaluate(rpn, var_dict): stack = [] def dict_get(key): return var_dict.get(key, key) for typ, value in rpn: if typ == KEYWORD: if value == 'NOT': operand = stack.pop() operand = dict_get(operand) stack.append(NOT(operand)) else: operand2 = stack.pop() operand2 = dict_get(operand2) operand1 = stack.pop() operand1 = dict_get(operand1) stack.append(FUNCS[value](operand1, operand2)) else: stack.append(value) return int(dict_get(stack.pop())) def postfix_to_infix(tokens): s = [] for token in tokens: typ, value = token if typ == BOOL: s.append(KW_TO_OP[value]) elif typ == NAME: s.append(value) else: if value == 'NOT': s.append(f'{KW_TO_OP["NOT"]}{s.pop()}') else: operand2 = s.pop() operand1 = s.pop() s.append(f'({operand1} {KW_TO_OP[value]} {operand2})') return s.pop() def gen_truth_table(expr): out = [] toks = tokenize(expr) if toks[0] == UNEXPECTED_CHAR: return syntaxerror(f'Unexpected character: {expr[toks[1]]!r}', expr, toks[1]) elif toks[0] == NEED_OPERAND: return syntaxerror(f'Expected a variable, constant or an open parenthesis, got {expr[toks[1]]!r}', expr, toks[1]) elif toks[0] == NEED_OPERATOR: return syntaxerror(f'Expected a binary connector or a close parentesis, got {expr[toks[1]]!r}', expr, toks[1]) elif toks[0] == EOL: return syntaxerror(f'Operator {expr[toks[1]]!r} is missing an operand', expr, toks[1]) elif toks[0] == NO_CLOSE_PARENTHESIS: return syntaxerror('No matching close parenthesis', expr, toks[1]) elif toks[0] == NO_OPEN_PARENTHESIS: return syntaxerror('No matching open parenthesis', expr, toks[1]) rpn = parse(toks) infix = postfix_to_infix(rpn) names = [] for typ, value in rpn: if typ == NAME and value not in names: names.append(value) if not names: return (infix,), (evaluate(rpn, {}),) out.append(names + [infix]) for prod in product((True, False), repeat=len(names)): var_dict = dict(zip(names, prod)) out.append([KW_TO_OP[var_dict[n]] for n in names] + [KW_TO_OP[evaluate(rpn, var_dict)]]) return out class Test(unittest.TestCase): def test_tokenize(self): cases = { '(T or F)': [(PAREN, '('), (BOOL, True), (KEYWORD, 'OR'), (BOOL, False), (PAREN, ')')], '_B3 <=> !~F': [(NAME, '_B3'), (KEYWORD, 'IFF'), (KEYWORD, 'NOT'), (KEYWORD, 'NOT'), (BOOL, False)], } k = [tokenize(i) for i in cases] v = list(cases.values()) self.assertSequenceEqual(k, v) def test_tokenize_errors(self): cases = { '(T or F': (NO_CLOSE_PARENTHESIS, 0), 'or b': (NEED_OPERAND, slice(0, 2)), 'a or <->': (NEED_OPERAND, slice(5, 8)), 'a or': (EOL, slice(2, 4)), 'a b or c': (NEED_OPERATOR, slice(2, 3)), 'a (b or c)': (NEED_OPERATOR, 2), 'a - b': (UNEXPECTED_CHAR, 2), 'A And c)': (NO_OPEN_PARENTHESIS, 7), } k = [tokenize(i) for i in cases] v = list(cases.values()) self.assertSequenceEqual(k, v) def test_parse(self): cases= { 'a or b': [(NAME, 'a'), (NAME, 'b'), (KEYWORD, 'OR')], 'a or b and c': [(NAME, 'a'), (NAME, 'b'), (NAME, 'c'), (KEYWORD, 'AND'), (KEYWORD, 'OR')], '(a or b) and c': [(NAME, 'a'), (NAME, 'b'), (KEYWORD, 'OR'), (NAME, 'c'), (KEYWORD, 'AND')], } k = [parse(tokenize(x)) for x in cases] v = list(cases.values()) self.assertSequenceEqual(k, v) def test_evaluate(self): cases = { ('a or b', (('a', 1), ('b', 0))): 1, ('p => F', (('p', 0),)): 1, ('p => F', (('p', 1),)): 0, ('(p <=> !q) => p', (('p', 0), ('q', 1))): 0, } k = [evaluate(parse(tokenize(a)), dict(b)) for a,b in cases] v = list(cases.values()) self.assertSequenceEqual(k, v) def main(): expr = input().strip() if not expr: return unittest.main() truth_table = gen_truth_table(expr) if not truth_table: return pad = [len(i) for i in truth_table[0]] for row in truth_table: print('|' + '|'.join(str(n).center(max(5, pad[i])) for i, n in enumerate(row)) + '|') if __name__ == '__main__': main()

Truth Table Generator