simple expression evaluator demo

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

simple expression evaluator demo

Post by BasicCoder2 »

THIS IS AN UPDATE:
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"
Last edited by BasicCoder2 on May 22, 2015 4:13, edited 6 times in total.
marcov
Posts: 3455
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: expression evaluator

Post by marcov »

Expression evaluators are fun to write. I fondly remember my attempts. The first were all adhoc, and the first with a bit of theory (and something that isolated tokenization from parsing) was a bit one of two of the rites of passage into adult programming-hood for me. Your seems to have a similar setup (two stacks) as my first serious attempt, except I was set on calculating the final sum.

The two stacks should at least make it possible to get nesting parentheses right (and from the code I'd say it does), and I also see some unary handling.

Some tips:

Keep in mind "-" are actually two operators, negation (aka unary minus) and subtraction (binary minus), but that minus can happen inside tokens as the sign of the exponent of a literal.

Strictly speaking unary plus exists too, but is usually not needed

e.g.

unary minus: -10+3*30 10+-4 which you already do. IIRC I had problems with the first char being unary minus.
unary plus: 10++2 easy if you already have unary minus. (flag?)
minus inside token: 1.0E-4
caseih
Posts: 2157
Joined: Feb 26, 2007 5:32

Re: expression evaluator

Post by caseih »

For doing adhoc parsing, I find that recursive descent parsers are the easiest to write. Many years ago I wrote a mathematical expression parser that dealt with orders of operation and precedence. Each level of precedence was it's own recursive function. Was a fun exercise.
marcov
Posts: 3455
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: expression evaluator

Post by marcov »

In retrospect, I think the stack method is pretty much a de-recursified recursive descent, probably with the same weaknesses and strengths, I just happened to end up with it because of the example source that I found. (and maybe it avoided recursion because it was for a 16-bit compiler)

IIRC I was mainly searching for something that could change infix to an array of variant records (=unions in C) that could be quickly evaluated (e.g. for drawing graphs from formulas entered by the user).
Last edited by marcov on Apr 27, 2015 16:22, edited 1 time in total.
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: expression evaluator

Post by BasicCoder2 »

An expression evaluator was one of the key functions that was required by even a simple BASIC interpreter. The routine itself was adapted from an article in a computer magazine however it didn't handle variables. Having just written a simple Editor/Assembler for the C64 I wanted to improve it with an evaluator routine. The Editor/Assembler was itself written in machine code and I was using it to assemble improved versions of itself. I had also begun writing a simple BASIC-like interpreter which also required an evaluator. There have been times when other projects might have required an evaluator which handles variables as well as constants such as in a spread sheet.
RockTheSchock
Posts: 252
Joined: Mar 12, 2006 16:25

Re: expression evaluator

Post by RockTheSchock »

I know that it's fun to write your own expression evaluator. I once tried it with QB:
http://forum.qbasic.at/viewtopic.php?t=8538

But if it's more than just for fun, maybe just use a script language like lua or squirrel.
http://www.freebasic.net/forum/viewtopi ... 15#p202993

With lua it's easy to make a sandbox with an own enviroment.
http://stackoverflow.com/questions/1224 ... er-6982080
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: expression evaluator

Post by BasicCoder2 »

@RockTheSchock,
I assume from looking at your code that your expression evaluator outputs an Assembler version of the expression. I am unable to run it to find out.
I am unfamiliar with any script languages.
RockTheSchock
Posts: 252
Joined: Mar 12, 2006 16:25

Re: expression evaluator

Post by RockTheSchock »

BasicCoder2 wrote:@RockTheSchock,
I assume from looking at your code that your expression evaluator outputs an Assembler version of the expression.
Well i modified it a bit so it should run with fbc -lang qb. The assembler output isn't right for a bit more complex expressions, but hey it's one of my early work.
BasicCoder2 wrote:I am unfamiliar with any script languages.
Well, if you use a script language as evaluator you just need to know how to prepare the expression and get the value back. Maybe you want to know exactly which operators/math functions can be used and extend the missing ones, but that's it. It's very easy with Squirrel or Lua.
marcov
Posts: 3455
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: expression evaluator

Post by marcov »

Can you lazy evaluate with Lua? IOW that lua calls you back to get the value for a variable? Or must you preload all data into lua space before calculation? (even if the expression might not contain it?)

(e.g. I only calculate the average gray area of an image if the expression the user enters really uses it)
Last edited by marcov on Apr 29, 2015 10:43, edited 1 time in total.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: expression evaluator

Post by dodicat »

RockTheShock described Lua a while back.
The expression parser is faster than VBscript (with the disphelper lib)
I did a quick Lua script eval a while back (When Rock~ was discussing it)
Only thing is, I never got round to eliminating (math.) before each maths function.

Maybe RockTheSchock could do this??

PARSER:

Code: Select all

#Include Once "Lua/lua.bi"
#Include Once "Lua/lauxlib.bi"
#Include Once "Lua/lualib.bi"

Function Eval(ByVal Expression As String,StringVariable As String,DoubleVariable As Double) As Double
    static as string funclast,func
    static Lua As lua_State Ptr 
    if funclast<>expression then
        lua=luaL_newstate
        luaL_openlibs(Lua)
        func = "function " + "f" +"("+StringVariable+")" +Chr(13)+Chr(10) _
        + "   return " + Expression +Chr(13)+Chr(10) _
        + "end"
        
        Print  func:print
        If luaL_dostring(Lua,func) Then
             PRINT "Error: " & *lua_tostring(Lua, -1),__LINE__      
             sleep 
        EndIf
    EndIf
    funclast=expression
    lua_getglobal(Lua, "f")
    lua_pushnumber(Lua, DoubleVariable)
    IF lua_pcall(Lua, 1, 1, 0) Then
        Print "Error: " & *lua_tostring(Lua, -1),__LINE__
        sleep
    EndIf
    Eval = lua_tonumber(Lua, -1)
    lua_pop(Lua, 1)
End Function
'================================================================

#define map(a,b,x,c,d) ((d)-(c))*((x)-(a))/((b)-(a))+(c)
dim as integer w,h
screeninfo w,h
screenres w,h
Width ,h\16 'make the font slightly larger
dim as string fn
dim as single lx,hx,ly,hy
dim as integer xval,yval
dim as integer count
do
    count=0
    read fn
    if fn="end" then exit do
    read lx
    read hx
    read ly
    read hy
   cls
 '================== the vewing box =============  
line(.1*w,.1*h)-(.9*w,.9*h),,bf
draw string(.1*w,.5*h),str(lx),5
draw string(.9*w-20,.5*h),str(hx),5
draw string(.5*w,.1*h),str(hy),5
draw string(.5*w,.9*h-20),str(ly),5
draw string(.45*w,.1*h+20),fn,0
'===============================================
'plotter
for x as single=lx to hx step (hx-lx)/1000
    count+=1
     var value=eval(fn,"x",x)
     
     xval=map(lx,hx,x,.1*w,.9*w)
     yval=map(hy,ly,value,.1*h,.9*h)'cartesian
     
     if count=1 then
     pset(xval,yval),0
 else
     line -(xval,yval),0
  end if   
    next x
sleep
loop until inkey=chr(27)
locate 2,2
print "Done"
 sleep
 const pi=4*atn(1)
 'data function(in x),lowerX,upperX,lowerY,upperY (cartesian co-ordinates)
 data "math.sin(x)",-10,10,-1.5,1.5
 data "math.cos(x)",0,2*pi,-2,2
 data "x^2",-5,5,0,25
 data "math.sin(x)/x",-20,20,-1,2
 data "3*math.sin(3*x)+2*math.cos(2*x)+math.sin(x)",-5,5,-10,10
 data "(((((-2*x+5)*x)+7)*x-3)*x+9)+3",-5,5,-100,100
 data "2*math.random()-2*math.random()",0,8,-2,2
 data "1/math.exp(x^2)",-3,3,-1.5,1.5
 data "1/(1+x^2)",-3,3,-1.5,1.5
 data "end"
 
 
'_END

  
RockTheSchock
Posts: 252
Joined: Mar 12, 2006 16:25

Re: expression evaluator

Post by RockTheSchock »

Sandbox is set to accept only math functions either with math prefix or without.

sandbox.lua

Code: Select all

env = _ENV.math
env.math = _ENV.math

function run(code)	
   f, message = load(code,"sandbox","t",env)   
   if not f then return nil, message end   
   return pcall(f)
end

Replace eval function with this one!

Code: Select all

Function Eval(ByVal Expression As String,StringVariable As String,DoubleVariable As Double) As Double
	static as string funclast,func
	static Lua As lua_State Ptr
	if funclast<>expression then
		lua=luaL_newstate
		luaL_openlibs(Lua)

		If luaL_dofile(Lua,"sandbox.lua") Then
			PRINT "Error: " & *lua_tostring(Lua, -1),__LINE__
			sleep
		EndIf

		func = "function f("+StringVariable+") " _
		+ "return (" + Expression + ") end"

		lua_getglobal(Lua, "run")
		lua_pushstring(Lua,func)
		If lua_pcall(Lua, 1, 1, 0) Then
			Print "Error: " & *lua_tostring(Lua, -1),__LINE__
			sleep
		EndIf
	EndIf
	funclast=expression

	lua_getglobal(Lua, "env")
	lua_getfield(Lua, -1 ,"f")

	lua_pushnumber(Lua,DoubleVariable)
	If lua_pcall(Lua, 1, 1, 0) Then
		Print "Error: " & *lua_tostring(Lua, -1),__LINE__
		sleep
	EndIf
	Eval = lua_tonumber(Lua, -1)
	lua_pop(Lua, 1)
End Function
Cherry
Posts: 358
Joined: Oct 23, 2007 12:06
Location: Austria
Contact:

Re: expression evaluator

Post by Cherry »

Code: Select all

? (3-2-2)+2
 3 2 2 - -  2?
Why the question mark there at the end?

Same for the exclamation mark here:

Code: Select all

? (1-2)-3
 1 2 -  3!
And the code crashes on invalid things like ")2)"
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: expression evaluator

Post by BasicCoder2 »

@Cherry,
Thank you for testing the code.
I think I have found and corrected the bug.
I have made the changes in the code in the first post.
As for it crashing on invalid expressions I have yet to add checks that the input is a valid expression.
In the example you gave I guess the check would be,
IF current item is a "(" and the previous item was a number then ERROR
However it could be a function such as SIN( or some user defined function
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: expression evaluator

Post by BasicCoder2 »

UPDATE:
There has been a rewrite of the expression evaluator demo program which I have placed in the first post of this thread.
I hope it is easier to read and it even has some error checking although invalid expressions are still possible.
Work in progress :)
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: expression evaluator

Post by BasicCoder2 »

dodicat wrote:RockTheShock described Lua a while back.
You guys know so much that I feel rather inadequate!!
I have just run your program and was surprised to see it worked!! I expected a "Lua not here error".
Problem is I really know nothing about Lua and hadn't heard of it until you mentioned it.

Here was a suggestion I found on the internet. I think it probably only works with a QBASIC interpreter.

Code: Select all

'http://computer-programming-forum.com/47-c-language/1fd632b8b92bb09f-2.htm
PRINT "Enter an expression:"
dim as string E$
INPUT E$ 
OPEN "TEMP.BAS" FOR OUTPUT AS #1 
PRINT #1, "PRINT " + E$
PRINT #1, "RUN "+CHR$(34)+"THISPROG.BAS"+CHR$(34) 
CLOSE #1 
RUN "TEMP.BAS" 
SLEEP
Post Reply