Parsing/RPN calculator algorithm: Difference between revisions
< Parsing
Content added Content deleted
(Add ref.) |
(add Ruby) |
||
Line 95: | Line 95: | ||
The final output value is: '3.0001220703125'</pre> |
The final output value is: '3.0001220703125'</pre> |
||
=={{header|Ruby}}== |
|||
<lang ruby>def evaluate_rpn(expression) |
|||
words = { "+" => "ADD", "-" => "SUB", "*" => "MUL", "/" => "DIV", "^" => "EXP" } |
|||
puts "for RPN expression: #{expression}\nTerm\tAction\tStack" |
|||
stack = [] |
|||
expression.split.each do |term| |
|||
case term |
|||
when "+", "-", "*", "/", "^" |
|||
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#{words[term]}\t#{stack}" |
|||
else |
|||
begin |
|||
number = Integer(term) |
|||
rescue ArgumentError |
|||
number = Float(term) rescue raise(ArgumentError, "not a number: #{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 |
|||
<pre>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</pre> |
Revision as of 17:50, 3 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).
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)
words = { "+" => "ADD", "-" => "SUB", "*" => "MUL", "/" => "DIV", "^" => "EXP" } puts "for RPN expression: #{expression}\nTerm\tAction\tStack" stack = [] expression.split.each do |term| case term when "+", "-", "*", "/", "^" 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#{words[term]}\t#{stack}"
else begin number = Integer(term) rescue ArgumentError number = Float(term) rescue raise(ArgumentError, "not a number: #{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