Parsing/RPN calculator algorithm

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

<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