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