Parsing/RPN calculator algorithm: Difference between revisions
(→Tcl: Added implementation) |
m (→{{header|Ruby}}: move code to Parsing/RPN/Ruby) |
||
Line 99: | Line 99: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
See [[Parsing/RPN/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 |
|||
Relevant output from test suite is |
|||
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 ^ ^ / + |
<pre>for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / + |
||
Term Action Stack |
Term Action Stack |
||
Line 145: | Line 117: | ||
/ DIV [3, 0.0001220703125] |
/ DIV [3, 0.0001220703125] |
||
+ ADD [3.0001220703125] |
+ ADD [3.0001220703125] |
||
value = 3.0001220703125</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
Revision as of 14:56, 6 December 2011
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(); a = stack.pop() stack.append( a ** b )
def op_mul(stack):
b = stack.pop(); a = stack.pop() stack.append( a * b )
def op_div(stack):
b = stack.pop(); a = stack.pop() stack.append( a / b )
def op_add(stack):
b = stack.pop(); a = stack.pop() stack.append( a + b )
def op_sub(stack):
b = stack.pop(); a = stack.pop() 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 = [max(len(y) for y in x) 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
See Parsing/RPN/Ruby
Relevant output from test suite is
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] value = 3.0001220703125
Tcl
<lang tcl># Helper proc pop stk {
upvar 1 $stk s set val [lindex $s end] set s [lreplace $s end end] return $val
}
proc evaluate rpn {
set stack {} foreach token $rpn {
set act "apply" switch $token { "^" { # Non-commutative operation set a [pop stack] lappend stack [expr {[pop stack] ** $a}] } "/" { # Non-commutative, special float handling set a [pop stack] set b [expr {[pop stack] / double($a)}] if {$b == round($b)} {set b [expr {round($b)}]} lappend stack $b } "*" { # Commutative operation lappend stack [expr {[pop stack] * [pop stack]}] } "-" { # Non-commutative operation set a [pop stack] lappend stack [expr {[pop stack] - $a}] } "+" { # Commutative operation lappend stack [expr {[pop stack] + [pop stack]}] } default { set act "push" lappend stack $token } } puts "$token\t$act\t$stack"
} return [lindex $stack end]
}
puts [evaluate {3 4 2 * 1 5 - 2 3 ^ ^ / +}]</lang> Output:
3 push 3 4 push 3 4 2 push 3 4 2 * apply 3 8 1 push 3 8 1 5 push 3 8 1 5 - apply 3 8 -4 2 push 3 8 -4 2 3 push 3 8 -4 2 3 ^ apply 3 8 -4 8 ^ apply 3 8 65536 / apply 3 0.0001220703125 + apply 3.0001220703125 3.0001220703125