#!/usr/bin/env python3 ''' Reverse Polish Notation Builder (2023-03-10) Take RPN expressions and convert them into infix expressions. Run this file as a Python script for info. Note: the tokenizer is useful working code in this file! ''' import string, operator # Character types identifier_chars = string.ascii_letters + '_' number_chars = string.digits operator_chars = '+-*/%^`:.~' reverse_operator_chars = '()' # How much each operator or type shrinks or grows the stack by # (Positive is growing, negative is shrinking, zero is no change) stack_effects = { 'name': 1, 'number': 1, '+': -1, # add '-': -1, # subtract '*': -1, # multiply '/': -1, # divide '%': -1, # modulo '^': -1, # exponentiate '`': 0, # negate ':': 1, # duplicate '.': -1, # drop '~': 0 # swap } # The higher the number, the higher the precedence operator_precedence = { 'name': 4, 'number': 4, '+': 0, '-': 0, '*': 1, '/': 1, '%': 1, '^': 2, '`': 3, ':': 3, '.': 3, '~': 3 } binary_operator_funcs = { '+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.floordiv, '%': operator.mod, '^': operator.pow, } class Token: def __init__ (self, kind, string, index): self.kind = kind self.string = str(string) self.index = index def require_stack(stack, n, token): L = len(stack) if L < n: raise ValueError("stack requires %s items for the operation '%s' but only has %s" %(n, token.string, L)) def operate (stack, token, simplify_constants=False): if 'name' == token.kind: stack.append(token.string) elif 'number' == token.kind: stack.append(int(token.string)) elif 'operator' == token.kind: if token.string in '+-*/%^': require_stack(stack, 2, token) y, x = stack.pop(), stack.pop() if simplify_constants and (type(x) == type(y) == int): # With actual numbers, the operation is performed func = binary_operator_funcs[token.string] stack.append(func(x, y)) else: # Otherwise, write out what needs to be calculated stack.append((token.string, (x, y))) elif '`' == token.string: # negate (unary operator) require_stack(stack, 1, token) x = stack[-1] if simplify_constants and type(x) == int: stack[-1] = -x else: stack[-1] = ('-', (0, x)) elif ':' == token.string: # duplicate require_stack(stack, 1, token) stack.append(stack[-1]) elif '.' == token.string: # drop require_stack(stack, 1, token) stack.pop() elif '~' == token.string: # swap require_stack(stack, 2, token) x = stack[-1] y = stack[-2] stack[-2] = x stack[-1] = y else: raise ValueError('invalid operator') else: raise ValueError('invalid token kind') def expr_precedence (expression): if type(expression) == int: op = 'number' elif type(expression) == str: op = 'name' elif type(expression) == tuple: op = expression[0] else: raise TypeError('invalid type: %s' % type(expression)) return operator_precedence[op] def infix (expression, add_space=True): # Convert a binary operator expression to infix notation # base case: literal number or variable if isinstance(expression, (int, str)): return str(expression) op = expression[0] level = operator_precedence[op] arg1, arg2 = expression[1] level1 = expr_precedence(arg1) level2 = expr_precedence(arg2) infix1 = infix(arg1, add_space) # recursive call if level1 < level: # 1st arg needs parens infix1 = '(' + infix1 + ')' infix2 = infix(arg2, add_space) # recursive call if level2 < level or (op == '-' and not isinstance(arg2, (int, str))): # 2nd arg needs parens infix2 = '(' + infix2 + ')' joiner = ' ' if add_space else '' return joiner.join((infix1, op, infix2)) def next_char (): global look, it, index try: look = next(it) index += 1 except StopIteration: look = None return look def skip_whitespace (): while look and look in string.whitespace: next_char() def next_token (): global token if look in number_chars: # Numbers kind = 'number' string = '' while look and look in number_chars: string += look next_char() elif look in identifier_chars: # Names kind = 'name' string = '' while look and look in identifier_chars: string += look next_char() elif look in operator_chars: # Operator characters kind = 'operator' string = look next_char() else: raise SyntaxError('unknown symbol: "%s"' % look) token = Token(kind, string, index) return token def main(): global look, it, index, token, tokens simplify_constants = True add_space = False debug = False print('Reverse Polish Notation Builder (2023-03-10)') print('Type "help" for more information') while True: try: source = input('>>> ').strip() except EOFError: break except KeyboardInterrupt: print() continue quit_words = ('exit', 'bye', 'quit') # "quit" --> quit if source.lower().strip() in quit_words: break # Blank input --> ignore if not source: continue # Toggle the add space option if source.lower().strip() == 'space': add_space = not add_space print('* add space:', add_space) continue # Toggle the simplify constants option if source.lower().strip() == 'const': simplify_constants = not simplify_constants print('* simplify constants:', simplify_constants) continue # Secret debug option if source.lower().strip() == 'debug': debug = not debug print('* debug:', debug) continue # "help" --> show help if source.lower().strip() == 'help': print() print('Welcome to RPN Builder\'s help!') print() print('RPN builder will take math expressions written in Reverse Polish Notation and try to convert them into "normal" infix notation.') print() print('These are some options you can change:') print('* add extra spaces (currently %s), toggle by typing "space"' % add_space) print('* simplify constants (currently %s), toggle by typing "const"' % simplify_constants) print() print('You can exit by typing %s or by pressing Ctrl-Z and then enter' %(' or '.join(['"%s"'%w for w in quit_words]))) print() continue try: # Tokenize the input # (global variables) it = iter(source) index = 0 look = None token = None tokens = [] next_char() # prime the first character from the stream while look is not None: skip_whitespace() next_token() tokens.append(token) free_names = set(t.string for t in tokens if t.kind == 'name') if debug: print('free variables:', ', '.join(free_names)) # Do the first step of translation to infix notation, which is switching to S-Expressions stack = [] for t in tokens: operate(stack, t, simplify_constants) if debug: print('stack:', stack) # Now make everything inside-out by removing parentheses and applying the precedence rules in_stack = [] for item in stack: in_stack.append(infix(item, add_space)) if debug: print('infix stack:', in_stack) # Print the final result print(in_stack[0]) except Exception as e: print('error:', ';'.join(str(x) for x in e.args)) continue if __name__ == '__main__': main()