Parsing/RPN calculator algorithm
< Parsing
Parsing/RPN calculator 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.
Create a stack-based evaluator for an expression in reverse Polish notation that also shows the changes in the stack as each individual token is processed as a table.
- Assume an input of a correct, space separated, string of tokens of an RPN expression
- Test with the RPN expression generated from the Parsing/Shunting-yard algorithm task
'3 4 2 * 1 5 - 2 3 ^ ^ / +'
then print and display the output here.
- Note
- '^' means exponentiation in the expression above.
- See also
- Parsing/Shunting-yard algorithm for a method of generating an RPN from an infix expression.
Python
<lang python>def op_pow(stack):
b = stack.pop(-1); a = stack.pop(-1) stack.append( a ** b )
def op_mul(stack):
b = stack.pop(-1); a = stack.pop(-1) stack.append( a * b )
def op_div(stack):
b = stack.pop(-1); a = stack.pop(-1) stack.append( a / b )
def op_add(stack):
b = stack.pop(-1); a = stack.pop(-1) stack.append( a + b )
def op_sub(stack):
b = stack.pop(-1); a = stack.pop(-1) stack.append( a - b )
def op_num(stack, num):
stack.append( num )
ops = {
'^': op_pow, '*': op_mul, '/': op_div, '+': op_add, '-': op_sub, }
def get_input(inp = None):
'Inputs an expression and returns list of tokens' if inp is None: inp = input('expression: ') tokens = inp.strip().split() return tokens
def rpn_calc(tokens):
stack = [] table = ['TOKEN,ACTION,STACK'.split(',')] for token in tokens: if token in ops: action = 'Apply op to top of stack' ops[token](stack) table.append( (token, action, ' '.join(str(s) for s in stack)) ) else: action = 'Push num onto top of stack' op_num(stack, eval(token)) table.append( (token, action, ' '.join(str(s) for s in stack)) ) return table
if __name__ == '__main__':
rpn = '3 4 2 * 1 5 - 2 3 ^ ^ / +' print( 'For RPN expression: %r\n' % rpn ) rp = rpn_calc(get_input(rpn)) 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 value is: %r' % rp[-1][2])</lang>
- Output
For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +' TOKEN ACTION STACK 3 Push num onto top of stack 3 4 Push num onto top of stack 3 4 2 Push num onto top of stack 3 4 2 * Apply op to top of stack 3 8 1 Push num onto top of stack 3 8 1 5 Push num onto top of stack 3 8 1 5 - Apply op to top of stack 3 8 -4 2 Push num onto top of stack 3 8 -4 2 3 Push num onto top of stack 3 8 -4 2 3 ^ Apply op to top of stack 3 8 -4 8 ^ Apply op to top of stack 3 8 65536 / Apply op to top of stack 3 0.0001220703125 + Apply op to top of stack 3.0001220703125 The final output value is: '3.0001220703125'