Numeric/String Eval function

[Ed Davis]

Hi @Ed Davis

I am trying to understand how you are parsing in Eval and I start around Expect, a couple of lines then goto by Sub or Function someplace else, a couple of lines, then someplace else... and this isn't spaghetti code but the effect on following it for understanding seems the same.

I am naming the opposite of spaghetti code,  shattered code, so refactored, so splintered and broken up... it's a nightmare to follow.

Not saying it's a bad thing, in fact I am wondering if it is some sign of being better for computers and efficiencies even if human understanding is made difficult.

But I am not familiar with the variables yet, it's like watching for first time a sitcom or soap opera that has been going for years.

It is based on this technique:  https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm - specifically Precedence Climbing.  Recursive Descent, Precedence Climbing, Shunting Yard, and Pratt Parsing basically all do the same thing, just expressed differently.  Of all of those, Precedence Climbing is the most understandable to me, so that is why I use it.

Here (updated this morning) is the same general algorithm, boiled down to just the bare essentials - a little over 100 lines of code, not counting comments.  Hopefully, it is much easier to follow.  And after reading the above article, it will make sense.  Or maybe look at this before, and then read the article :)

Code: QB64: [Select]

1. 'Simple Eval function
2. '
3. 'Compiles with QB64 and FreeBasic (-lang qb).
4. '
5. 'Accepts */+-^ and parenthesis.
6. '
7. 'Precedence:
8. '   unary +,-
9. '   *, /
10. '   +, -
11. '
12. 'Example:
13. '
14. 'a$ = "1+2*3+(5-1)"
15. 'print eval#(a$)
16. '
17. 'Written by Ed Davis.  Contact: ed_davis2 at that yahoo place.
18. 'Use at your own risk.
19. '
20. option _explicit ' drop the "_" for FreeBasic
21.  
22. declare function expr#(p as integer)
23. declare function eval#
24.  
25. dim shared userstr as string, sym as string
26.  
27. do
28.     line input "Enter expression:", userstr
29.     if userstr = "" then exit do
30.     print eval#
31. loop
32.  
33. ' lexical analyzer functions
34.  
35. function isdigit%(ch as string)
36.     isdigit% = left$(ch, 1) >= "0" and left$(ch, 1) <= "9"
37. end function
38.  
39. function isnumeric%(ch as string)
40.     isnumeric% = isdigit(ch) or left$(ch, 1) = "."
41. end function
42.  
43. sub takechar
44.     sym = sym + left$(userstr, 1)
45.     userstr = right$(userstr, len(userstr) - 1)
46. end sub
47.  
48. sub nextsym
49.     sym = "": userstr = ltrim$(userstr)
50.     call takechar
51.     select case sym
52.         case "(", ")", "+", "-", "*", "/"  'all set
53.         case "0" to "9"
54.             while isdigit%(userstr)
55.                 call takechar
56.             wend
57.             if left$(userstr, 1) = "." then
58.                 call takechar
59.  
60.                 while isdigit%(userstr)
61.                     call takechar
62.                 wend
63.             end if
64.         case "."
65.             while isdigit%(userstr)
66.                 call takechar
67.             wend
68.         case ""
69.         case else
70.             print "unrecognized character:", sym
71.             sym = ""
72.     end select
73. end sub
74.  
75. ' Main expression parsing routine
76. function expr#(p as integer)
77.     dim n as double, n2 as double, op as string, q as integer, prec as integer
78.  
79.     ' handle numeric operands - numbers and unary operators
80.     prec = 0: if sym = "+" or sym = "-" then prec = 3
81.     if prec > 0 then
82.         op = sym: call nextsym
83.         select case op          ' unary operators
84.             case "-" : n = -expr#(prec)
85.             case "+" : n =  expr#(prec)
86.         end select
87.     elseif sym = "(" then
88.         call nextsym: n = expr#(0)
89.         if sym <> ")" then
90.             print "expecting ')'"
91.         else
92.             call nextsym
93.         end if
94.     elseif isnumeric%(sym) then
95.         n = val(sym): call nextsym
96.     else
97.         print "syntax error: expecting a primary, found:", sym
98.     end if
99.  
100.     ' binary operators
101.     do  ' while binary operator and precedence of sym >= p
102.         select case sym
103.             case "+", "-" : prec = 1
104.             case "*", "/" : prec = 2
105.             case else :     prec = 0 ' not a binary operator
106.         end select
107.  
108.         if prec = 0 or prec < p then exit do
109.  
110.         op = sym: call nextsym: q = prec + 1
111.  
112.         n2 = expr#(q)
113.         select case op
114.             case "*" : n = n * n2
115.             case "/" : n = n / n2
116.             case "+" : n = n + n2
117.             case "-" : n = n - n2
118.             case else: print "syntax error: expecting a binary operator, found:", sym
119.         end select
120.     loop
121.  
122.     expr# = n
123. end function
124.  
125. function eval#
126.     call nextsym
127.     eval# = expr#(0)
128.     if sym <> "" then print "error: extra input found: "; sym; userstr
129. end function

[Aurel]

Yes Ed like Precedence Climbing but i like Recursive Descent. because i understand that one better
but yes all of them doing the same thing ...
@Ed ..program work fine as usual !!!

[bplus]

@Ed Davis  Oh you've updated this morning, I just had a revelation myself this morning.
https://www.qb64.org/forum/index.php?topic=2308.msg130620#msg130620