This converts an infix expression into reverse polish notation (postFix)
45+502*60 becomes 45 502 60 * +
(45+502)*60 becomes 45 502 + 60 *
At this stage it only deals with the operators * / + -
It also deals with negation so -4 becomes 4! or -(3+2) becomes 3 2 + !
It does not accept variable names or floating point numbers only integer digits.
Invalid characters like a-z or A-Z etc will be ignored.
You can add more test expressions in the data statements after the line 'TEST DATA
As you tap the space key another item is processed and the stack contents displayed.
It ends with the answer on the number stack and the postfix version of the infix input printed.
Later I hope to add other operators like ^ <> >= <= AND OR as well as functions like SQR( SIN( and so on ...
Code: Select all
screenres 640,480,32
dim shared as string oprStk(100) 'operator stack
dim shared as integer oprCnt 'number of items on stack
dim shared as string numStk(100) 'operand stack
dim shared as integer numCnt 'number of operands on operand stack
dim shared as integer flag 'flag=1 if last item was a number
dim shared as integer p 'point to current position in expr
dim shared as string expr 'current expression string
dim shared as string ch 'current character
dim shared as string item 'extracted item
dim shared as string op 'operator taken from stack
dim shared as string outString 'postFix version of infix expression
dim shared as integer bracketCount 'increments for ( and decrements for )
sub displayStacks()
'print operator stack
cls
locate 1,1
print expr
print
print "operator stack [";
if oprCnt<>0 then
for i as integer = 0 to oprCnt-1
print oprStk(i);" ";
next i
print " ]"
end if
print
print "number stack [";
if numCnt<>0 then
for i as integer = 0 to numCnt-1
print numStk(i);" ";
next i
print " ]"
end if
sleep
end sub
function precedence(op as string) as integer
if op="+" then return 1
if op="-" then return 1
if op="*" then return 2
if op="/" then return 2
if op="(" then return 0
if op="!" then return 9
return 0
end function
sub compute(op as string)
dim as integer num1,num2,num3
if numCnt=0 then print "ERROR NO DATA":sleep:end
if op = "!" then 'negate top of stack
numStk(numCnt-1)= str(-val(numStk(numCnt-1)))
print "! ";
else
if numCnt<2 then
print "ERROR INSUFFICIENT DATA"
print op,p
sleep
end
end if
'pop to numbers
numCnt = numCnt - 1
num2 = val(numStk(numCnt))
numCnt = numCnt - 1
num1 = val(numStk(numCnt))
if op = "+" then
num3 = num1 + num2
end if
if op = "-" then
num3 = num1 - num2
end if
if op = "*" then
num3 = num1 * num2
end if
if op = "/" then
num3 = num1 \ num2 'do integer divide
end if
print num1;" ";num2;" ";op;" "; 'postscript output
'push number
numStk(numCnt)= str(num3)
numCnt = numCnt + 1
end if
end sub
sub eval()
'reset values
outString = ""
oprCnt = 0
numCnt = 0
flag = 0
p = 0
while p < len(expr)
item = ""
ch = chr(expr[p]) 'get next character
while ch = " " 'skip leading spaces
p = p + 1
ch = chr(expr[p])
wend
if ch = "-" and flag = 0 then
oprStk(oprCnt)="!"
oprCnt = oprCnt + 1
p = p + 1
ch = chr(expr[p])
end if
if ch >= "0" and ch <= "9" then ' isNumber(ch)
item = ch
p = p + 1
ch = chr(expr[p]) 'get next character
while ch >="0" and ch <= "9" ' isNumber(ch)
item = item + ch
p = p + 1
ch = chr(expr[p])
wend
outString = outString & item & " "
flag = 1
'push number on stack
numStk(numCnt) = item
numCnt = numCnt + 1
elseif ch="+" or ch="-" or ch="*" or ch="/" then 'isOperator(ch)
item = ch
p = p + 1 'get next character
ch = chr(expr[p])
while ch ="+" or ch="-" or ch="*" or ch="/"
item = item + ch
p = p + 1
ch = chr(expr[p])
wend
'pop operators with lower precedence item operator
while precedence(item) <= precedence(oprStk(oprCnt-1) ) and oprCnt>0
oprCnt = oprCnt - 1
op = oprStk(oprCnt)
compute(op) 'compute
outString = outString & op & " "
wend
'push item onto operator stack
oprStk(oprCnt)=item
oprCnt = oprCnt + 1
flag = 0
elseif ch = "(" then 'stack it on oprStk
item = ch
oprStk(oprCnt)= ch
oprCnt = oprCnt + 1
p = p + 1
flag = 0
bracketCount = bracketCount + 1
elseif ch = ")" then
'make sure a ( actually exists
if bracketCount = 0 then
print "ERROR ( bracket missing ":sleep:end
end if
'pop items off operator stack until "(" found
oprCnt = oprCnt - 1
op = oprStk(oprCnt)
while op <> "("
outString = outString & op & " "
compute(op) 'compute
oprCnt = oprCnt - 1
op = oprStk(oprCnt)
wend
p = p + 1
flag = 0
bracketCount = bracketCount - 1
else
print "invalid character ";
item = ch 'invalid character
p = p + 1
flag = 0
end if
displayStacks()
wend
'unstack rest of operator stack
while oprCnt<>0
oprCnt = oprCnt - 1
op = oprStk(oprCnt)
compute(op) 'compute
displayStacks()
outString = outString & op & " "
wend
if bracketCount<>0 then
print "ERROR missing bracket/s":sleep:end
end if
end sub
'MAIN LOOP
print -45+3*22/5
print -(45 + 3)*22/ 5
sleep
print
read expr
while expr<>"DONE"
print
print expr
print
eval()
print
print outString
sleep
read expr
wend
'TEST DATA
data "-45+3*22/5"
data "-(45 + 3)*22/ 5"
data "DONE"