Parsing/RPN calculator algorithm: Difference between revisions
< Parsing
Content added Content deleted
m (→{{header|Ruby}}: tweaks) |
(Add link.) |
||
Line 14: | Line 14: | ||
* Several solutions to [[24 game/Solve]] make use of RPN evaluators (although tracing how they work is not a part of that task). |
* Several solutions to [[24 game/Solve]] make use of RPN evaluators (although tracing how they work is not a part of that task). |
||
* [[Parsing/RPN to infix conversion]]. |
* [[Parsing/RPN to infix conversion]]. |
||
* [[Arithmetic evaluation]]. |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 05:00, 6 December 2011
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.
- Several solutions to 24 game/Solve make use of RPN evaluators (although tracing how they work is not a part of that task).
- Parsing/RPN to infix conversion.
- Arithmetic evaluation.
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'
Ruby
<lang ruby>def evaluate_rpn(expression)
operations = { "+" => "ADD", "-" => "SUB", "*" => "MUL", "/" => "DIV", "^" => "EXP" } puts "for RPN expression: #{expression}\nTerm\tAction\tStack" stack = [] expression.split.each do |term| if operations.has_key?(term) a, b = stack.pop(2) raise ArgumentError, "not enough operands on the stack" if b.nil? a = a.to_f if term == "/" op = (term == "^" ? "**" : term) stack.push(a.method(op).call(b)) puts "#{term}\t#{operations[term]}\t#{stack}" else begin number = Integer(term) rescue Float(term) rescue ArgumentError raise ArgumentError, "cannot handle term: #{term}" end stack.push(number) puts "#{number}\tPUSH\t#{stack}" end end
result = stack.pop puts "Final result = #{result}" result
end
evaluate_rpn "3 4 2 * 1 5 - 2 3 ^ ^ / +"</lang>
output
for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / + Term Action Stack 3 PUSH [3] 4 PUSH [3, 4] 2 PUSH [3, 4, 2] * MUL [3, 8] 1 PUSH [3, 8, 1] 5 PUSH [3, 8, 1, 5] - SUB [3, 8, -4] 2 PUSH [3, 8, -4, 2] 3 PUSH [3, 8, -4, 2, 3] ^ EXP [3, 8, -4, 8] ^ EXP [3, 8, 65536] / DIV [3, 0.0001220703125] + ADD [3.0001220703125] Final result = 3.0001220703125