Parsing/Shunting-yard algorithm
< Parsing
Parsing/Shunting-yard algorithm 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.
Given the operator characteristics and input from the Shunting-yard algorithm page and tables Use the algorithm to show the changes in the operator stack and RPN output as each individual token is processed.
- Assume an input of a correct, space separated, string of tokens
- Generate a space separated output string representing the RPN
- Test with the input 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
- Extra credit
- Add extra text explaining the actions and an optional comment for the action on receipt of each token.
- Note
- the handling of functions and arguments is not required.
Python
Parenthesis are added to the operator table then special-cased in the code. This solution includes the extra credit. <lang python>from collections import namedtuple from pprint import pprint as pp
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),
')': OpInfo(prec=0, assoc=L),
}
NUM, LPAREN, RPAREN = 'NUMBER ( )'.split()
def get_input(inp = None):
'Inputs an expression and returns list of (TOKENTYPE, tokenvalue)'
if inp is None:
inp = input('expression: ')
tokens = inp.strip().split()
tokenvals = []
for token in tokens:
if token in ops:
tokenvals.append((token, ops[token]))
#elif token in (LPAREN, RPAREN):
# tokenvals.append((token, token))
else:
tokenvals.append((NUM, token))
return tokenvals
def shunting(tokenvals):
outq, stack = [], []
table = ['TOKEN,ACTION,RPN OUTPUT,OP STACK,NOTES'.split(',')]
for token, val in tokenvals:
note = action =
if token is NUM:
action = 'Add number to output'
outq.append(val)
table.append( (val, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) )
elif token in ops:
t1, (p1, a1) = token, val
v = t1
note = 'Pop ops from stack to output'
while stack:
t2, (p2, a2) = stack[-1]
if (a1 == L and p1 <= p2) or (a1 == R and p1 < p2):
if t1 != RPAREN:
if t2 != LPAREN:
stack.pop(-1)
action = '(Pop op)'
outq.append(t2)
else:
break
else:
if t2 != LPAREN:
stack.pop(-1)
action = '(Pop op)'
outq.append(t2)
else:
stack.pop(-1)
action = '(Pop & discard "(")'
table.append( (v, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) )
break
table.append( (v, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) )
v = note =
else:
note =
break
note =
note =
if t1 != RPAREN:
stack.append((token, val))
action = 'Push op token to stack'
else:
action = 'Discard ")"'
table.append( (v, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) )
note = 'Drain stack to output'
while stack:
v =
t2, (p2, a2) = stack[-1]
action = '(Pop op)'
stack.pop(-1)
outq.append(t2)
table.append( (v, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) )
v = note =
return table
if __name__ == '__main__':
infix = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
print( 'For infix expression: %r\n' % infix )
rp = shunting(get_input(infix))
maxcolwidths = [len(max(x, key=lambda y: len(y))) for x in zip(*rp)]
row = rp[0]
print( ' '.join('{cell:^{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))
for row in rp[1:]:
print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))
print('\n The final output RPN is: %r' % rp[-1][2])</lang>
- Sample output
For infix expression: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
TOKEN ACTION RPN OUTPUT OP STACK NOTES
3 Add number to output 3
+ Push op token to stack 3 +
4 Add number to output 3 4 +
* Push op token to stack 3 4 + *
2 Add number to output 3 4 2 + *
/ (Pop op) 3 4 2 * + Pop ops from stack to output
Push op token to stack 3 4 2 * + /
( Push op token to stack 3 4 2 * + / (
1 Add number to output 3 4 2 * 1 + / (
- Push op token to stack 3 4 2 * 1 + / ( -
5 Add number to output 3 4 2 * 1 5 + / ( -
) (Pop op) 3 4 2 * 1 5 - + / ( Pop ops from stack to output
(Pop & discard "(") 3 4 2 * 1 5 - + /
Discard ")" 3 4 2 * 1 5 - + /
^ Push op token to stack 3 4 2 * 1 5 - + / ^
2 Add number to output 3 4 2 * 1 5 - 2 + / ^
^ Push op token to stack 3 4 2 * 1 5 - 2 + / ^ ^
3 Add number to output 3 4 2 * 1 5 - 2 3 + / ^ ^
(Pop op) 3 4 2 * 1 5 - 2 3 ^ + / ^ Drain stack to output
(Pop op) 3 4 2 * 1 5 - 2 3 ^ ^ + /
(Pop op) 3 4 2 * 1 5 - 2 3 ^ ^ / +
(Pop op) 3 4 2 * 1 5 - 2 3 ^ ^ / +
The final output RPN is: '3 4 2 * 1 5 - 2 3 ^ ^ / +'