Task

Create a stack-based evaluator for an expression in   reverse Polish notation (RPN)   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 ^ ^ / + 

 Print or display the output here


Notes

    ^    means exponentiation in the expression above.
    /    means division.


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.


1000 DECLARE EXTERNAL SUB rpn
1010 PUBLIC NUMERIC R(64)                             ! stack
1020 PUBLIC STRING expn$                              ! for keyboard input
1030 PUBLIC NUMERIC i, lenn, n, true, false           ! global values
1040 LET true = -1
1050 LET false = 0
1060 DO
1070    PRINT "enter an RPN expression:"
1080    INPUT expn$
1090    IF LEN( expn$ ) = 0 THEN EXIT DO 
1100    PRINT "expn: ";expn$      
1110    CALL rpn( expn$ )
1120 LOOP
1130 END
1140 !
1150 ! interpret reverse polish (postfix) expression
1160 EXTERNAL SUB rpn( expn$ )
1170 DECLARE EXTERNAL FUNCTION is_digit, get_number
1180 DECLARE EXTERNAL SUB print_stack
1190 DECLARE STRING ch$
1200 LET expn$ = expn$ & " "                          ! must terminate line with space
1210 LET lenn = LEN( expn$ )
1220 LET i = 0
1230 LET n = 1
1240 LET R(n) = 0.0                                   ! push zero for unary operations
1250 DO
1260    IF i >= lenn THEN EXIT DO                     ! at end of line
1270    LET i = i + 1
1280    IF expn$(i:i) <> " " THEN                     ! skip white spaces
1290       IF is_digit( expn$(i:i) ) = true THEN      ! push number onto stack
1300          LET n = n + 1
1310          LET R(n) = get_number
1320          CALL print_stack
1330       ELSEIF expn$(i:i) = "+" then               ! add and pop stack
1340          IF n < 2 THEN
1350             PRINT "stack underflow"
1360          ELSE
1370             LET R(n-1) = R(n-1) + R(n)
1380             LET n = n - 1
1390             CALL print_stack
1400          END IF
1410       ELSEIF expn$(i:i) = "-" then               ! subtract and pop stack
1420          IF n < 2 THEN
1430             PRINT "stack underflow"
1440          ELSE
1450             LET R(n-1) = R(n-1) - R(n)
1460             LET n = n - 1
1470             CALL print_stack
1480          END IF
1490       ELSEIF expn$(i:i) = "*" then               ! multiply and pop stack
1500          IF n < 2 THEN
1510             PRINT "stack underflow"
1520          ELSE
1530             LET R(n-1) = R(n-1) * R(n)
1540             LET n = n - 1
1550             CALL print_stack
1560          END IF
1570       ELSEIF expn$(i:i) = "/" THEN               ! divide and pop stack
1580          IF n < 2 THEN
1590             PRINT "stack underflow"
1600          ELSE
1610             LET R(n-1) = R(n-1) / R(n)
1620             LET n = n - 1
1630             CALL print_stack
1640          END IF
1650       ELSEIF expn$(i:i) = "^" THEN               ! raise to power and pop stack
1660          IF n < 2 THEN
1670             PRINT "stack underflow"
1680          ELSE
1690             LET R(n-1) = R(n-1) ^ R(n)
1700             LET n = n - 1
1710             CALL print_stack
1720          END IF
1730       ELSE
1740          PRINT REPEAT$( " ", i+5 ); "^ error"
1750          EXIT DO 
1760       END IF
1770    END IF
1780 LOOP
1790 PRINT "result: "; R(n)                           ! end of main program
1800 END SUB
1810 !
1820 ! extract a number from a string
1830 EXTERNAL FUNCTION get_number
1840 DECLARE EXTERNAL FUNCTION is_digit
1850 LET j = 1                                        ! start of number string
1860 DECLARE STRING number$                           ! buffer for conversion
1870 DO                                               ! get integer part
1880    LET number$(j:j) = expn$(i:i)
1890    LET i = i + 1
1900    LET j = j + 1
1910    IF is_digit( expn$(i:i) ) = false THEN
1920       IF expn$(i:i) = "." then          
1930          LET number$(j:j) = expn$(i:i)           ! include decimal point
1940          LET i = i + 1
1950          LET j = j + 1
1960          DO WHILE is_digit( expn$(i:i) ) = true  ! get fractional part
1970             LET number$(j:j) = expn$(i:i)
1980             LET i = i + 1
1990             LET j = j + 1
2000          LOOP
2010       END IF
2020       EXIT DO
2030    END IF
2040 LOOP
2050 LET get_number = VAL( number$ )
2060 END FUNCTION
2070 !
2080 ! check for digit character
2090 EXTERNAL FUNCTION is_digit( ch$ )
2100 IF "0" <= expn$(i:i) AND expn$(i:i) <= "9" THEN
2110    LET is_digit = true
2120 ELSE
2130    LET is_digit = false
2140 END IF
2150 END FUNCTION
2160 !
2170 EXTERNAL SUB print_stack
2180 PRINT expn$(i:i);"    ";
2190 FOR ptr=n TO 2 STEP -1
2200    PRINT USING "-----%.####":R(ptr);
2210 NEXT ptr
2220 PRINT
2230 END SUB