Need a fast infix math evaluator

[dracflamloc]

I managed to get it down to 150 on this comp by removing your function handling code

[Trond]

Then it's not a scripting language anymore and it's alot harder, but you could combine mashine with scripting code, only using compiled stuff for mathematic functions, and JITC are really cool I think

A real compiler is much easier than a JIT compiler since you don't have to check whether something is already compiled or not, you simply compile everything and pass it on to the assembler for assembly. In a JIT compiler you need to compile directly to assembled code or bundle an assembler and God knows what you don't have to do.

[dracflamloc]

Anyway, Xombie I found a bug in your code. It can't handle "-10" as an input!

[Trond]

Anyway, Xombie I found a bug in your code. It can't handle "-10" as an input!

Neither can mine.

[dracflamloc]

Really? Because I've been using it and it works for me?

[Trond]

Really? Because I've been using it and it works for me?

No, it returns zero always. This fixed version can also handle it correctly if the contents of a parenthesis is -something, so you can do funky stuff like "100*(-(-(-1)))". It also has improved error handling so it aborts on stuff like "100~garbagefasd" (at some speed expense, this should though be countered almost completely by a speed increase caused by the fix of the -x bug).

Fixed (twice):

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 

;----- 

Declare.f Expression() 

Procedure.f Factor() 
  Protected Value.f
  If (PeekB(@Look) > 47 And PeekB(@Look) < 58) 
    ProcedureReturn GetNum() 
  Else 
    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("100*(5+3)+1") ))

Input()

[dracflamloc]

Hm. Must have been in a change I made that made it sometimes work... But thanks for the fix. Thats awesome =)

BUg I found:
When the Stream = "100*(5+3)+1"

It spits out the error:

Expected: nothing, got ')'

[Trond]

Hm. Must have been in a change I made that made it sometimes work... But thanks for the fix. Thats awesome =)

BUg I found:
When the Stream = "100*(5+3)+1"

It spits out the error:

Expected: nothing, got ')'

Yes, there was logic with where I placed the error check. It's fixed now.

[dracflamloc]

Nice. I like the new version. Very quick on the complex operations.

Xombies new code is pretty amazing on the single operations.

I appreciate all the work you guys are doing on these. Lets me concentrate on the actual scripting language more

[Xombie]

I updated my code again. Which was good because I had a suuuuper bad logic error that I didn't catch in the older code. I wasn't evaluating items from left to right when they were the same operator level. Pretty bad mistake there.

Out of curiousity - what are you using all of this stuff for?

[Killswitch]

I think he's writing an interpreted scripting langauge for PB.

Thanks to this thread I've started rewriting my RPN functions because they're slowness make me feel inadequete . My latest code can change 100+1 to 100 1 + in about 250 milliseconds - a lot better than the original 792ish milliseconds but still not fast enough!

[dracflamloc]

Yes I'm creating a scripting language. Did you not see the thread here that says "DracScript preview" =)

http://www.purebasic.fr/english/viewtopic.php?t=20213

[Flype]

@trond

i studied your code, and i wondered how many millisecs i can save
by using a structured pointer rather than the line !CALL l_get_char.

the result is much more readable, shorter, a little faster, and not using asm.

Code: Select all

Declare.f 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.f 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.f Factor()
  Protected Value.f
  If (*expr\b >= '0' And *expr\b <= '9')
    ProcedureReturn GetNum()
  Else
    Match('(')
    Value = Expression()
    Match(')')
  EndIf
  ProcedureReturn Value
EndProcedure
Procedure.f Term()
  Protected Value.f
  Value = Factor()
  While (*expr\b = '*' Or *expr\b = '/')
    If *expr\b = '*'
      *expr + 1
      Value * Factor()
    Else
      *expr + 1
      Value / Factor()
    EndIf
  Wend
  ProcedureReturn Value
EndProcedure
Procedure.f Expression()
  Protected Value.f
  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.f Solve(input.s)
  *expr = @input
  ProcedureReturn Expression()
EndProcedure

;=================================

time.l = ElapsedMilliseconds()

For i = 0 To 100000
  result.f = Solve("100*(5+3)+1")
Next

MessageRequester(Str(ElapsedMilliseconds()-time),StrF(result))

i hope it works as well as the previous one.

[Flype]

just an observation:

this code runs a little bit faster in 3.94 than in 4.0 (on my AMD 1.2Ghz)
:roll:

PB3.94 = 1280 ms
PB4.0.6 = 1332 ms

[dracflamloc]

Nifty. Try plugging it into the scripting engine I just release for me!