Need a fast infix math evaluator

Post by **Dare2** » Sat Mar 11, 2006 5:19 am

Threads like this are few and far between!

This is really good and useful/informative in a number of ways.

Thanks to all who are making it so!

mike74 · Post by **mike74** » Thu Apr 06, 2006 9:14 pm

I took the liberty of modifying Flype's code slightly and adding some of my own to make an expression evaluator that can operate on numbers with up to 6 digits after the decimal and produce a result that is correct up to 6 digits after the decimal. It uses quads for the operations to avoid potential problems with floating point precision and returns a string instead of a possibly imprecise float. I'm sure it can be improved upon speedwise, especially through the use of pointers and ascii codes as in Flype's code, and it shouldn't be too hard to make it more general for a certain number of decimal places. Two last things: Your expression should be enclosed in parentheses and I'm not guaranteeing anything! Here it is:

Code: Select all

Declare.q Expression() 

Global *expr.BYTE 

Procedure Expected(string.s) 
  MessageRequester("Error","Expected : "+string+", Got : "+Chr(*expr\b)) 
  End 
EndProcedure 
Procedure Match(b.b) 
  If *expr\b = b 
    *expr + 1 
  Else 
    Expected(Chr(b)) 
  EndIf 
EndProcedure 
Procedure.q GetNum() 
  Protected Temp.s 
  If (*expr\b < '0') And (*expr\b > '9') 
    Expected("Integer") 
  EndIf 
  While ((*expr\b >= '0' And *expr\b <= '9') Or *expr\b = '.') 
    Temp + Chr(*expr\b) 
    *expr + 1 
  Wend 
  ProcedureReturn ValF(Temp) 
EndProcedure 
Procedure.q Factor() 
  Protected Value.q 
  If (*expr\b >= '0' And *expr\b <= '9') 
    ProcedureReturn GetNum() 
  Else 
    Match('(') 
    Value = Expression() 
    Match(')') 
  EndIf 
  ProcedureReturn Value 
EndProcedure 
Procedure.q Term() 
  Protected Value.q 
  Value = Factor() 
  While (*expr\b = '*' Or *expr\b = '/') 
    If *expr\b = '*' 
      *expr + 1: Value * Factor() 
    Else 
      *expr + 1: factval.q = factor()
      If ((value % factval) * 2 >= factval)
        value = Value / Factval + 1
      Else: Value / Factval: EndIf
    EndIf 
  Wend 
  ProcedureReturn Value 
EndProcedure 
Procedure.q Expression() 
  Protected Value.q 
  If *expr\b = '-' 
    *expr + 1: Value = -Term() 
  Else 
    Value = Term() 
  EndIf 
  While (*expr\b = '+' Or *expr\b = '-') 
    If *expr\b = '+' 
      *expr + 1: Value + Term() 
    Else 
      *expr + 1: Value - Term() 
    EndIf 
  Wend 
  ProcedureReturn Value 
EndProcedure 
Procedure.s Solve(input.s) 
  *expr = @Input
  qstr.s = StrQ(Expression())
  If Len(qstr) >= 6: rtrnstr.s = Left(qstr, (Len(qstr) - 6)) + "." + Right(qstr, 6)
    Else: rtrnstr = ".": For t = 1 To (6 - Len(qstr)): rtrnstr + "0": Next t: rtrnstr + qstr: EndIf
  ProcedureReturn rtrnstr
EndProcedure 

Procedure.s stringeval(in.s)
    lastfound = 1: multcnt = 0: divcnt = 0: lastop.s = ""
    For j = 1 To Len(in)
        founddec = 0: foundnum = 0: fact$ = ""
        getchar.s = Mid(in, j, 1)
        If getchar = "*" Or getchar = "/" Or getchar = "+" Or getchar = "-" Or getchar = "(" Or getchar = ")"
            If getchar = "/": divcnt = 1: EndIf
            If (getchar = "*" And multcnt > 0) Or (getchar = "/" Or getchar = "+" Or getchar = "-" Or getchar = ")")
                For x = 1 To multcnt: fact$ + "*1/1000000": Next x
                If divcnt = 1: fact$ + "*1*1000000": EndIf
                multcnt = 0: divcnt = 0
            Else
                fact$ = "*1"
            EndIf
            If lastop = "/": fact$ = "*1": EndIf
            For y = (j - 1) To 1 Step -1
                k.s = Mid(in, y, 1)
                If Str(Val(k)) <> k And k <> ".": Break: Else
                    foundnum = 1
                    If k = ".": part$ = part$ + Mid(in, lastfound, (j - lastfound)) + Space(7 - (j - y)) + fact$ + getchar
                        lastfound = j + 1: founddec = 1: Break: EndIf
                EndIf
            Next y
            If founddec = 0 And foundnum = 1: part$ = part$ + Mid(in, lastfound, (j - lastfound)) + Space(6) + fact$ + getchar: lastfound = j + 1: EndIf
            lastop = getchar
            If lastop = "*": multcnt = multcnt + 1: EndIf
        EndIf
    Next j
    part$ = RemoveString(ReplaceString(part$, " ", "0"), "0.")
    part$ = RemoveString(part$, ".")
ProcedureReturn part$
EndProcedure
string2eval.s = "(2*0.03/6*0.7)"
Debug stringeval(string2eval)
result.s = solve(stringeval(string2eval))
Debug result

dracflamloc · Post by **dracflamloc** » Fri Apr 07, 2006 2:35 am

Every thing is welcome and appreciated!

aston · Post by **aston** » Tue Dec 10, 2013 8:00 pm

hi to all!
I am looking into Trond evaluator and i can say that is really very fast
and almost the simpliest one we can find on net.
Is anyone maybe add variable name(LookUp) in it?
I have try with procedure GetNum() but it looks that not work.
In my tests i use asc() insted of poke and peek...
anyone ?

aston · Post by **aston** » Tue Dec 10, 2013 8:19 pm

sorry i forget to post code,here is ...

Code: Select all

OpenConsole()

Global Look.s
Look.s = " " ; Yes, that space is IMPORTANT!!!! Remove and DIE!!!
Global Stream.s
Global StreamPos.l        ; Read position in stream

Procedure.s VisibleToken(s.s)
  Select s.s
    Case #CR$
      s.s = "newline"
    Case #LF$
      s.s = "newline"
    Case ""
      s.s = "nothing"
  EndSelect
  ProcedureReturn s.s
EndProcedure

;Cleanup then end
Procedure Finish()
  PrintN("Ending.")
  Input()
  End
EndProcedure

;Report an error
Procedure Error(s.s)
  PrintN("Error: " + s + ".")
EndProcedure

;Report an error and abort
Procedure Abort(s.s)
  Error(s.s)
  Finish()
EndProcedure

;Report what was expected
Procedure Expected(expected.s)
  Abort("Expected: " + expected + ", got '" + VisibleToken(Look) + "'")
EndProcedure

;Read a character into Look
Goto GetChar_End
GetChar:
  PokeB(@Look, PeekB(@Stream + StreamPos))
  StreamPos + 1
  Return
GetChar_End:

;Match a specific input character
Procedure Match(s.s)
  If Look <> s.s
    Expected("'"+s.s+"'")
  Else
    !CALL l_getchar
  EndIf
EndProcedure

;Get a number
Procedure.f GetNum()
  Protected Temp.s
  If (PeekB(@Look) < 48 And PeekB(@Look) > 57)
    Expected("Integer")
  EndIf
;  While (PeekB(@Look) > 47 And PeekB(@Look) < 58 Or PeekB(@Look) = '.')   ; Works not
  While ((PeekB(@Look) > 47 And PeekB(@Look) < 58) Or PeekB(@Look) = '.') ; Works
    Temp + Look
    !CALL l_getchar
  Wend
  ProcedureReturn ValF(Temp)
EndProcedure

Procedure.f GetVar()
  Protected Temp.s
  If (PeekB(@Look) < 96 And PeekB(@Look) > 123)
    Expected("Variable")
  EndIf
;  While (PeekB(@Look) > 47 And PeekB(@Look) < 58 Or PeekB(@Look) = '.')   ; Works not
  While ((PeekB(@Look) > 96 And PeekB(@Look) < 123) ) ; Works
    Temp + Look
    !CALL l_getchar
  Wend
  MessageRequester("TEMP",Temp)
  ; is this place good to get variable value from external proceduere like GetVarValue()?
  ProcedureReturn ValF(Temp)
EndProcedure


;-----

Declare.f Expression()

Procedure.f Factor()
  Protected Value.f
  If (PeekB(@Look) > 47 And PeekB(@Look) < 58)
    ProcedureReturn GetNum()
  EndIf
  If (PeekB(@Look) > 96 And PeekB(@Look) < 123)
    MessageRequester("","is variable...")
    ProcedureReturn GetVar()
  EndIf
  If look
    Match("(")
    Value = Expression()
    Match(")")
  EndIf
  ProcedureReturn Value
EndProcedure

Procedure.f Term()
  Protected Value.f
  Value = Factor()
  While (Look = "*" Or Look = "/")
    If Look = "*"
      !CALL l_getchar
      Value * Factor()
    Else
      !CALL l_getchar
      Value / Factor()
    EndIf
  Wend
  ProcedureReturn Value
EndProcedure

Procedure.f Expression()
  Protected Value.f
  If (Look = "-")
    !CALL l_getchar
    Value = -Term()
  Else
    Value = Term()
  EndIf
  While (Look = "+" Or Look = "-")
    If Look = "+"
      !CALL l_getchar
      Value + Term()
    Else
      !CALL l_getchar
      Value - Term()
    EndIf
  Wend
  ProcedureReturn Value
EndProcedure

Procedure.f Solve(s.s)
  Stream = ReplaceString(s.s, " ", "")
  StreamPos = 0
  !CALL l_getchar
  Temp.f = Expression()
  If StreamPos < Len(Stream) ; Error check, you
    Expected("nothing")      ; can remove them if you don't
  EndIf                      ; need the check
  ProcedureReturn Temp.f
EndProcedure

#Tries = 100000

time = GetTickCount_()
For I = 0 To #Tries
  Solve("100+1")
Next
MessageRequester("", Str(GetTickCount_()-time))

PrintN(StrF( Solve("(1+2)*abc") ))
;PrintN(StrF( Solve("(1+2)*3") ))
Input()

Danilo · Post by **Danilo** » Wed Dec 11, 2013 8:05 am

aston wrote:hi to all!
I am looking into Trond evaluator and i can say that is really very fast
and almost the simpliest one we can find on net.
Is anyone maybe add variable name(LookUp) in it?
I have try with procedure GetNum() but it looks that not work.
In my tests i use asc() insted of poke and peek...
anyone ?

If I understand correctly, you want to use variables within expressions?

aston wrote:sorry i forget to post code,here is ...

Your code did not work here. (EDIT: Sorry, had Unicode enabled by default. Your code works with Unicode disabled)

You could try the following code, if speed is not the most important thing for you:

Code: Select all

DisableDebugger ; for time measurement

XIncludeFile "Evaluate.pbi" ; http://danilo.purearea.net/EvaluateExpression.zip

OpenConsole()

#Tries = 100000

Define i, start_time = ElapsedMilliseconds()

For i = 1 To #Tries
  Evaluate("100+1")
Next

Define end_time = ElapsedMilliseconds()-start_time

;MessageRequester("", Str(end_time)+" ms ("+Str(#Tries)+" tries)" )
PrintN( Str(end_time)+" ms ("+Str(#Tries)+" tries)" )

PrintN( Evaluate("100+1")     )

EvaluateVariables("abc") = "10"
PrintN( Evaluate("(1+2)*abc") )

PrintN( Evaluate("(1+2)*3")   )
Input()

Unfortunately it takes round about 275 milliseconds here to evaluate "100+1" 100.000 times. Don't know if this
is fast enough for you, but at least it works cross-platform in Ascii/Unicode mode, has the variables support
you want, and it even supports some more operators.

aston · Post by **aston** » Wed Dec 11, 2013 1:27 pm

Hi danilo
Yes i don't need unicode or any other complex stuff.
ok i see your evaluator is on pureArea...thanks!
Speed is not critical and if you say that it takes 275 ms that is very fine for me.

Important thing is that there is no any kind of memory leaks
thanks again!

EDIT..
Uff your code is cool but is little bit to complex for me to understand...
Is there any simple evaluator created in more classic way...
thanks!

Danilo · Post by **Danilo** » Wed Dec 11, 2013 7:50 pm

aston wrote:EDIT..
Uff your code is cool but is little bit to complex for me to understand...
Is there any simple evaluator created in more classic way...

Your last code with added map SolveVariables() for procedure GetVar():

Code: Select all

OpenConsole()

Global Look.s
Look.s = " " ; Yes, that space is IMPORTANT!!!! Remove and DIE!!!
Global Stream.s
Global StreamPos.l        ; Read position in stream

Procedure.s VisibleToken(s.s)
  Select s.s
    Case #CR$
      s.s = "newline"
    Case #LF$
      s.s = "newline"
    Case ""
      s.s = "nothing"
  EndSelect
  ProcedureReturn s.s
EndProcedure

;Cleanup then end
Procedure Finish()
  PrintN("Ending.")
  Input()
  End
EndProcedure

;Report an error
Procedure Error(s.s)
  PrintN("Error: " + s + ".")
EndProcedure

;Report an error and abort
Procedure Abort(s.s)
  Error(s.s)
  Finish()
EndProcedure

;Report what was expected
Procedure Expected(expected.s)
  Abort("Expected: " + expected + ", got '" + VisibleToken(Look) + "'")
EndProcedure

;Read a character into Look
Goto GetChar_End
GetChar:
  PokeB(@Look, PeekB(@Stream + StreamPos))
  StreamPos + 1
  Return
GetChar_End:

;Match a specific input character
Procedure Match(s.s)
  If Look <> s.s
    Expected("'"+s.s+"'")
  Else
    !CALL l_getchar
  EndIf
EndProcedure

;Get a number
Procedure.f GetNum()
  Protected Temp.s
  If (PeekB(@Look) < 48 And PeekB(@Look) > 57)
    Expected("Integer")
  EndIf
;  While (PeekB(@Look) > 47 And PeekB(@Look) < 58 Or PeekB(@Look) = '.')   ; Works not
  While ((PeekB(@Look) > 47 And PeekB(@Look) < 58) Or PeekB(@Look) = '.') ; Works
    Temp + Look
    !CALL l_getchar
  Wend
  ProcedureReturn ValF(Temp)
EndProcedure

Global NewMap SolveVariables.s() ; ADDED BY DANILO

Procedure.f GetVar()
  Protected Temp.s
  If (PeekB(@Look) < 96 And PeekB(@Look) > 123)
    Expected("Variable")
  EndIf
;  While (PeekB(@Look) > 47 And PeekB(@Look) < 58 Or PeekB(@Look) = '.')   ; Works not
  While ((PeekB(@Look) > 96 And PeekB(@Look) < 123) ) ; Works
    Temp + Look
    !CALL l_getchar
  Wend
  ; MessageRequester("TEMP",Temp)
  ; is this place good to get variable value from external proceduere like GetVarValue()?
  ProcedureReturn ValF(SolveVariables(Temp)) ; CHANGED BY DANILO
EndProcedure


;-----

Declare.f Expression()

Procedure.f Factor()
  Protected Value.f
  If (PeekB(@Look) > 47 And PeekB(@Look) < 58)
    ProcedureReturn GetNum()
  EndIf
  If (PeekB(@Look) > 96 And PeekB(@Look) < 123)
    ;MessageRequester("","is variable...")
    ProcedureReturn GetVar()
  EndIf
  If look
    Match("(")
    Value = Expression()
    Match(")")
  EndIf
  ProcedureReturn Value
EndProcedure

Procedure.f Term()
  Protected Value.f
  Value = Factor()
  While (Look = "*" Or Look = "/")
    If Look = "*"
      !CALL l_getchar
      Value * Factor()
    Else
      !CALL l_getchar
      Value / Factor()
    EndIf
  Wend
  ProcedureReturn Value
EndProcedure

Procedure.f Expression()
  Protected Value.f
  If (Look = "-")
    !CALL l_getchar
    Value = -Term()
  Else
    Value = Term()
  EndIf
  While (Look = "+" Or Look = "-")
    If Look = "+"
      !CALL l_getchar
      Value + Term()
    Else
      !CALL l_getchar
      Value - Term()
    EndIf
  Wend
  ProcedureReturn Value
EndProcedure

Procedure.f Solve(s.s)
  Stream = ReplaceString(s.s, " ", "")
  StreamPos = 0
  !CALL l_getchar
  Temp.f = Expression()
  If StreamPos < Len(Stream) ; Error check, you
    Expected("nothing")      ; can remove them if you don't
  EndIf                      ; need the check
  ProcedureReturn Temp.f
EndProcedure

#Tries = 100000

time = ElapsedMilliseconds()
For I = 0 To #Tries
  Solve("100+1")
Next
MessageRequester("", Str(ElapsedMilliseconds()-time))

SolveVariables("abc") = "1.5"
PrintN(StrF( Solve("(1+2)*abc") ))
PrintN(StrF( Solve("(1+2)*3") ))
PrintN(StrF( Solve("x + y") ))
Input()

This returns 0 for unknown variables: PrintN(StrF( Solve("x + y") ))
Add an error message if the map element TEMP can't be found, to change this behavior:

Code: Select all

Procedure.f GetVar()
  Protected Temp.s
  If (PeekB(@Look) < 96 And PeekB(@Look) > 123)
    Expected("Variable")
  EndIf
;  While (PeekB(@Look) > 47 And PeekB(@Look) < 58 Or PeekB(@Look) = '.')   ; Works not
  While ((PeekB(@Look) > 96 And PeekB(@Look) < 123) ) ; Works
    Temp + Look
    !CALL l_getchar
  Wend
  ; MessageRequester("TEMP",Temp)
  ; is this place good to get variable value from external proceduere like GetVarValue()?
  If FindMapElement(SolveVariables(),Temp)=0
      ; output Error
      Abort( "Variable '"+Temp+"' not initialized." )
  EndIf
  ProcedureReturn ValF(SolveVariables(Temp)) ; CHANGED BY DANILO
EndProcedure

aston · Post by **aston** » Wed Dec 11, 2013 11:02 pm

Yes that is , it is really the simpliest solution !
Thank you very much Danilo

aston · Post by **aston** » Sat Dec 14, 2013 7:23 pm

hi again...
I really don't bothering you with problems.
But i must ask something ...
I think that some of you guys here( in first place i mean ) on people who have
experience with scripting languages or are authors of them.
Why this type or similar types of expression evaluators produce very
high memory usage when is used inside loops.
if i use anything else inside loop what is not calcualtion then there is no
memory leak...
i hope that my question is not too stupid...

acreis · Post by **acreis** » Mon Dec 16, 2013 8:26 pm

Don't worry, your question is not stupid, and there is no reason for memory leaks if your code is correct.

Best Regards

Danilo · Post by **Danilo** » Tue Dec 17, 2013 7:56 am

aston wrote:Why this type or similar types of expression evaluators produce very
high memory usage when is used inside loops.
if i use anything else inside loop what is not calcualtion then there is no
memory leak...
i hope that my question is not too stupid...

How do you test for memory leaks? Can you give some code?

Sometimes OS memory management allocates more and more fresh
memory blocks on the heap, but it is not a real memory leak, and the memory
is released by the OS later. It is not so easy sometimes, so best you can do is
provide some example code where you see the possible leak, and at the same
time we could see how you measure the memory usage.

For example, on Windows you should call EmptyWorkingSet_() and HeapCompact_()
right before measuring memory usage (for debugging only) when looking for memory leaks,
to prevent the OS behavior I talked about.

With PureBasic itself, you should disable the debugger when looking for memory leaks,
as the debugger could disturb memory usage statistics. The debugger could collect infos
or strings get added to the debug output window (and those strings occupy some memory).

Also PB version, and Operating System and its version are important when looking for such issues,
as there are many possible combinations (Win95 - Win8.1, GNU/Linux X.XX, Mac OS X version XX.XX,
latest PB 5.21 LTS or any older version).

aston · Post by **aston** » Fri Jan 17, 2014 8:54 am

How do you test for memory leaks?

heh..by looking into task manager....eh...

By the way ...anyone maybe have a idea how to add into this tronD based
parser possibility to detect function like sin(90) ?
thanks in advance

aston · Post by **aston** » Tue Jan 21, 2014 5:40 pm

anyone ?

Tenaja · Post by **Tenaja** » Tue Jan 21, 2014 6:17 pm

aston wrote:anyone ?

This is taken from mike74's code at the top of page 4. It is not tested to be finished; I leave that to you. I just wanted to point you in the right direction.

Code: Select all

Procedure.q Factor()
	Protected Value.q
	
	If (*expr\b >= '0' And *expr\b <= '9')
		ProcedureReturn GetNum()
	ElseIf *expr\b = 's'
		Match('s')
		Match('(')
		Value = Sin(Expression())
		Match(')')
	Else
		Match('(')
		Value = Expression()
		Match(')')
	EndIf
	ProcedureReturn Value
EndProcedure

PureBasic Forums - English

Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator

Re: Need a fast infix math evaluator