Task

Given the operator characteristics and input from the Shunting-yard algorithm page and tables, use the algorithm to show the changes in the operator stack and RPN output
as each individual token is processed.

 Assume an input of a correct, space separated, string of tokens representing an infix expression
 Generate a space separated output string representing the RPN
 Test with the input string:
  3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3  
 print and display the output here.
 Operator precedence is given in this table:


 operator 
 precedence 
 associativity 
 operation


  ^  
 4 
 right 
 exponentiation


  *  
 3 
 left 
 multiplication


  /  
 3 
 left 
 division


  +  
 2 
 left 
 addition


  -  
 2 
 left 
 subtraction



Extra credit
Add extra text explaining the actions and an optional comment for the action on receipt of each token.



Note
The handling of functions and arguments is not required.



See also

 Parsing/RPN calculator algorithm for a method of calculating a final value from this output RPN expression.
 Parsing/RPN to infix conversion.


 
global stack$,queue$ 
stack$=""
queue$=""
 
in$ = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
print "Input:"
print in$
 
token$ = "#"
print "No", "token", "stack", "queue"
 
while 1
    i=i+1
    token$ = word$(in$, i)
    if token$ = "" then i=i-1: exit while
    print i, token$, reverse$(stack$), queue$
 
    select case
    case token$ = "("
        call stack.push token$
 
    case token$ = ")"
        while stack.peek$() <> "("
            'if stack is empty
            if stack$="" then print "Error: no matching '(' for token ";i: end
            call queue.push stack.pop$()
        wend
        discard$=stack.pop$()   'discard "("
 
    case isOperator(token$)
        op1$=token$
        while(isOperator(stack.peek$()))
            op2$=stack.peek$()
            select case
            case op2$<>"^" and precedence(op1$) = precedence(op2$)
                '"^" is the only right-associative operator
                call queue.push stack.pop$()
            case precedence(op1$) < precedence(op2$)
                call queue.push stack.pop$()
            case else
                exit while
            end select
        wend
        call stack.push op1$
 
    case else   'number
        'actually, wrong operator could end up here, like say %
        'If the token is a number, then add it to the output queue.
        call queue.push token$
    end select
 
wend
 
while stack$<>""
    if stack.peek$() = "(" then print "no matching ')'": end
    call queue.push stack.pop$()
wend
 
print "Output:"
while queue$<>""
    print queue.pop$();" ";
wend
print
 
end
 
'------------------------------------------
function isOperator(op$)
    isOperator = instr("+-*/^", op$)<>0 AND len(op$)=1
end function
 
function precedence(op$)
    if isOperator(op$) then
        precedence = 1 _
            + (instr("+-*/^", op$)<>0) _
            + (instr("*/^", op$)<>0) _
            + (instr("^", op$)<>0)
    end if
end function
 
'------------------------------------------
sub stack.push s$
    stack$=s$+"|"+stack$ 
end sub
 
sub queue.push s$
    queue$=queue$+s$+"|"
end sub
 
function queue.pop$()
    'it does return empty on empty stack or queue
    queue.pop$=word$(queue$,1,"|")
    queue$=mid$(queue$,instr(queue$,"|")+1)
end function
 
function stack.pop$()
    'it does return empty on empty stack or queue
    stack.pop$=word$(stack$,1,"|")
    stack$=mid$(stack$,instr(stack$,"|")+1)
end function
 
function stack.peek$()
    'it does return empty on empty stack or queue
    stack.peek$=word$(stack$,1,"|")
end function
 
function reverse$(s$)
    reverse$ = ""
    token$="#"
    while token$<>""
        i=i+1
        token$=word$(s$,i,"|")
        reverse$ = token$;" ";reverse$
    wend
end function
 