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.


#define NULL 0
 
type node
    'implement the stack as a linked list
    n as double
    p as node ptr
end type
 
function spctok( byref s as string ) as string
    'returns everything in the string up to the first space
    'modifies the original string to begin at the fist non-space char after the first space
    dim as string r
    dim as double i = 1
    while mid(s,i,1)<>" " and i<=len(s)
        r += mid(s,i,1)
        i+=1
    wend
    do 
        i+=1
    loop until mid(s,i,1)<>" " or i >= len(s)
    s = right(s,len(s)-i+1)
    return r
end function
 
sub print_stack( byval S as node ptr )
    'display everything on the stack
    print "Stack   <---   ";
    while S->p <> NULL
        S = S->p
        print S->n;"   ";
    wend
    print
end sub
 
sub push( byval S as node ptr, v as double )
    'push a value onto the stack
    dim as node ptr x
    x = allocate(sizeof(node))
    x->n = v
    x->p = S->p
    S->p = x
end sub
 
function pop( byval S as node ptr ) as double
    'pop a value from the stack
    if s->P = NULL then return -99999
    dim as double r = S->p->n
    dim as node ptr junk = S->p
    S->p = S->p->p
    deallocate(junk)
    return r
end function
 
dim as string s = "3 4 2 * 1 5 - 2 3 ^ ^ / +", c
dim as node StackHead
 
while len(s) > 0
    c = spctok(s)
    print "Token: ";c;"  ";
    select case c
        case "+"
            push(@StackHead, pop(@StackHead) + pop(@StackHead))
            print "Operation +     ";
        case "-"
            push(@StackHead, -(pop(@StackHead) - pop(@StackHead)))
            print "Operation -     ";
        case "/"
            push(@StackHead, 1./(pop(@StackHead) / pop(@StackHead)))
            print "Operation /     ";
        case "*"
            push(@StackHead, pop(@StackHead) * pop(@StackHead))
            print "Operation *     ";
        case "^"
            push(@StackHead, pop(@StackHead) ^ pop(@StackHead))
            print "Operation ^     ";
        case else
            push(@StackHead, val(c))
            print "Operation push  ";
    end select
    print_stack(@StackHead)
wend