115 lines
2.6 KiB
Text
115 lines
2.6 KiB
Text
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
|