Rosetta Code

Parsing/RPN to infix conversion: Difference between revisions

Page Discussion

Parsing/RPN to infix conversion (view source)

Revision as of 11:36, 14 June 2012

557 bytes added ,  11 years ago
→‎{{header|Python}}: Replaced old example with one that properly takes associativity into account.
No edit summary
(→‎{{header|Python}}: Replaced old example with one that properly takes associativity into account.)
Line 757:
 
=={{header|Python}}==
{{incorrect|Python|Doesn't deal with associativity}}
 
<lang python>from collections import namedtuple
"""
>>> # EXAMPLE USAGE
>>> result = rpn_to_infix('3 4 2 * 1 5 - 2 3 ^ ^ / +', VERBOSE=True)
TOKEN STACK
3 ['3']
4 ['3', '4']
2 ['3', '4', '2']
* ['3', Node('4','*','2')]
1 ['3', Node('4','*','2'), '1']
5 ['3', Node('4','*','2'), '1', '5']
- ['3', Node('4','*','2'), Node('1','-','5')]
2 ['3', Node('4','*','2'), Node('1','-','5'), '2']
3 ['3', Node('4','*','2'), Node('1','-','5'), '2', '3']
^ ['3', Node('4','*','2'), Node('1','-','5'), Node('2','^','3')]
^ ['3', Node('4','*','2'), Node(Node('1','-','5'),'^',Node('2','^','3'))]
/ ['3', Node(Node('4','*','2'),'/',Node(Node('1','-','5'),'^',Node('2','^','3')))]
+ [Node('3','+',Node(Node('4','*','2'),'/',Node(Node('1','-','5'),'^',Node('2','^','3'))))]
>>> result
'3 + 4 * 2 / (1 - 5) ^ 2 ^ 3'
"""
 
prec_dict = {'^':4, '*':3, '/':3, '+':2, '-':2}
OpInfo = namedtuple('OpInfo', 'prec assoc')
assoc_dict = {'^':1, '*':0, '/':0, '+':0, '-':0}
L, R = 'Left Right'.split()
 
class Node:
ops = {
def __init__(self,y,op,x):
'^': OpInfo(prec=4, assoc=R),
global prec_dict,assoc_dict
'*': OpInfo(prec=3, assoc=L),
'/': OpInfo(prec=3, assoc=L),
self.precedence = prec_dict[op]
'+': OpInfo(prec=2, assoc=L),
self.assocright = assoc_dict[op]
'-': OpInfo(prec=2, assoc=L),
self.op = op
')': OpInfo(prec=9, assoc=L),
#NUM: OpInfo(prec=0, assoc=L)
if not self.assocright and self >= x and \
}
isinstance(x, Node) and not isinstance(y, Node):
numinfo = OpInfo(prec=9, assoc=L)
self.x = x.x
self.y = Node(y, x.op, x.y)
else:
self.x,self.y = x,y
def __str__(self):
showypar = self.y < self or (self.y == self and self.assocright)
showxpar = self.x < self or (self.x == self and not self.assocright)
str_y = (str(self.y), '(%s)'%str(self.y))[showypar]
str_x = (str(self.x), '(%s)'%str(self.x))[showxpar]
return ' '.join([str_y, self.op, str_x])
 
def __repr__(self):
NUM, LPAREN, RPAREN = 'NUMBER ( )'.split()
"""
>>> repr(Node('3','+','4')) == repr(eval(repr(Node('3','+','4'))))
True
"""
return 'Node(%s,%s,%s)'%(repr(self.y), repr(self.op), repr(self.x))
 
def __cmp__(self, other):
"""
>>> Node('3','+','4') < Node('6','*','7')
True
>>> Node('3','+','4') == Node('6','-','7')
True
>>> Node('3','+','4') == '-'
True
>>> Node('3','^','4') < '1'
True
"""
if isinstance(other, Node):
return cmp(self.precedence, other.precedence)
return cmp(self.precedence, prec_dict.get(other,9))
 
def get_inputrpn_to_infix(inps, VERBOSE= NoneFalse):
"""
'Inputs a space separated expression and returns list of tokens'
>>> rpn_to_infix('5 4 +')
'5 + 4'
>>> rpn_to_infix('5 4 3 2 ^ ^ ^')
'5 ^ 4 ^ 3 ^ 2'
>>> rpn_to_infix('5 6 ^ 7 ^')
'(5 ^ 6) ^ 7'
>>> rpn_to_infix('4 3 2 + +')
'4 + 3 + 2'
>>> rpn_to_infix('5 4 3 2 + + +')
'5 + 4 + 3 + 2'
>>> rpn_to_infix('3 4 5 * -')
'3 - 4 * 5'
>>> rpn_to_infix('3 4 5 - *')
'(3 - 4) * 5'
>>> rpn_to_infix('4 2 * 1 5 - +')
'4 * 2 + (1 - 5)'
>>> rpn_to_infix('4 2 * 1 5 - 2 ^ /')
'4 * 2 / (1 - 5) ^ 2'
>>> rpn_to_infix('3 4 2 * 1 5 - 2 3 ^ ^ / +')
'3 + 4 * 2 / (1 - 5) ^ 2 ^ 3'
>>> rpn_to_infix('1 2 + 3 4 + ^ 5 6 + ^')
'((1 + 2) ^ (3 + 4)) ^ (5 + 6)'
"""
global prec_dict
 
if VERBOSE : print('TOKEN STACK')
if inp is None:stack=[]
for token in s.split():
inp = input('expression: ')
if token in prec_dict:
return inp.strip().split()
x,y=stack.pop(),stack.pop()
 
stack.append(Node(y,token,x))
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)
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>
 
# can't use \t in order to make global docstring pass doctest
;Sample output:
if VERBOSE : print(token+' '*6+repr(stack))
<pre>For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +'
 
return str(stack[0])
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
 
if __name__ == "__main__":
The final output infix expression is: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'</pre>
import doctest
doctest.testmod()
</lang>
 
=={{header|Ruby}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/209402"