Parsing/RPN to infix conversion
< Parsing
Parsing/RPN to infix conversion is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Create a program that takes an RPN representation of an expression formatted as a space separated sequence of tokens and generates the same expression in infix notation.
- Assume an input of a correct, space separated, string of tokens
- Generate a space separated output string representing the same expression in infix notation
- Show how the major datastructure of your algorithm changes with each new token parsed.
- Test with the input RPN string
'3 4 2 * 1 5 - 2 3 ^ ^ / +'then print and display the output here. - Operator precedence is given in this table:
operator precedence associativity ^ 4 Right * 3 Left / 3 Left + 2 Left - 2 Left
- Note
- '^' means exponentiation.
- See also
- Parsing/Shunting-yard algorithm for a method of generating an RPN from an infix expression.
- Parsing/RPN calculator algorithm for a method of calculating a final value from this output RPN expression.
- Postfix to infix from the RubyQuiz site.
Python
<lang python>from collections import namedtuple
OpInfo = namedtuple('OpInfo', 'prec assoc') L, R = 'Left Right'.split()
ops = {
'^': OpInfo(prec=4, assoc=R), '*': OpInfo(prec=3, assoc=L), '/': OpInfo(prec=3, assoc=L), '+': OpInfo(prec=2, assoc=L), '-': OpInfo(prec=2, assoc=L), ')': OpInfo(prec=9, assoc=L), #NUM: OpInfo(prec=0, assoc=L) }
numinfo = OpInfo(prec=9, assoc=L)
NUM, LPAREN, RPAREN = 'NUMBER ( )'.split()
def get_input(inp = None):
'Inputs a space separated expression and returns list of tokens'
if inp is None:
inp = input('expression: ')
return inp.strip().split()
def rpn2infix(tokens):
stack = [] # [ (partial_expr, (prec, assoc)), ... ]
table = ['TOKEN,ACTION,STACK (comma separated)'.split(',')]
for token in tokens:
if token in ops:
action = 'Push partial expression'
opinfo = ops[token]
b = stack.pop(); a = stack.pop()
if b[1].prec < opinfo.prec: b = '( %s )' % b[0], ops[')']
if a[1].prec < opinfo.prec: a = '( %s )' % a[0], ops[')']
stack.append( ('%s %s %s' % (a[0], token, b[0]), opinfo) )
else:
action = 'Push num'
stack.append((token, numinfo))
row = (token, action, ', '.join(str(s[0]) for s in stack))
#pp(row, width=120)
table.append( row )
return table
if __name__ == '__main__':
rpn = '3 4 2 * 1 5 - 2 3 ^ ^ / +'
print( 'For RPN expression: %r\n' % rpn )
infix = rpn2infix(get_input(rpn))
maxcolwidths = [len(max(x, key=lambda y: len(y))) for x in zip(*infix)]
row = infix[0]
print( ' '.join('{cell:^{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))
for row in infix[1:]:
print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))
print('\n The final output infix expression is: %r' % infix[-1][2])</lang>
- Sample output
For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +' TOKEN ACTION STACK (comma separated) 3 Push num 3 4 Push num 3, 4 2 Push num 3, 4, 2 * Push partial expression 3, 4 * 2 1 Push num 3, 4 * 2, 1 5 Push num 3, 4 * 2, 1, 5 - Push partial expression 3, 4 * 2, 1 - 5 2 Push num 3, 4 * 2, 1 - 5, 2 3 Push num 3, 4 * 2, 1 - 5, 2, 3 ^ Push partial expression 3, 4 * 2, 1 - 5, 2 ^ 3 ^ Push partial expression 3, 4 * 2, ( 1 - 5 ) ^ 2 ^ 3 / Push partial expression 3, 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 + Push partial expression 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 The final output infix expression is: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'