Rosetta Code

Arithmetic evaluation: Difference between revisions

Page Discussion

Arithmetic evaluation (view source)

Revision as of 13:36, 25 May 2021

37,414 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
(Added Wren)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 4,447:
plus this as asked for has an AST, whereas Phix uses cross-linked flat IL.
See also [[Arithmetic_evaluation/Phix]] for a translation of the D entry.
<!--<lang Phix>(phixonline)-->
<lang Phix>-- demo\rosetta\Arithmetic_evaluation.exw
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Arithmetic_evaluation.exw</span>
sequence opstack = {} -- atom elements are literals,
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
-- sequence elements are subexpressions
-- on completion length(opstack) should be 1
<span style="color: #004080;">sequence</span> <span style="color: #000000;">opstack</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #000080;font-style:italic;">-- atom elements are literals,
object token
-- sequence elements are subexpressions
 
constant op_p_p = 0 -- on 1:completion expressionslength(opstack) storedshould asbe op,p1,p21</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">token</span>
-- p_op_p -- 0: expressions stored as p1,op,p2
-- p_p_op -- -1: expressions stored as p1,p2,op
<span style="color: #008080;">constant</span> <span style="color: #000000;">op_p_p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- 1: expressions stored as op,p1,p2
 
-- p_op_p -- 0: expressions stored as p1,op,p2
object op = 0 -- 0 if none, else "+", "-", "*", "/", "^", "%", or "u-"
-- p_p_op -- -1: expressions stored as p1,p2,op</span>
 
string s -- the expression being parsed
<span style="color: #004080;">object</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- 0 if none, else "+", "-", "*", "/", "^", "%", or "u-"</span>
integer ch
integer sidx
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #000080;font-style:italic;">-- the expression being parsed</span>
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span>
procedure err(string msg)
<span style="color: #004080;">integer</span> <span style="color: #000000;">sidx</span>
printf(1,"%s\n%s^ %s\n\nPressEnter...",{s,repeat(' ',sidx-1),msg})
{} = wait_key()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">err</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">msg</span><span style="color: #0000FF;">)</span>
abort(0)
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n%s^ %s\n\nPressEnter..."</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">msg</span><span style="color: #0000FF;">})</span>
end procedure
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
 
<span style="color: #7060A8;">abort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
procedure nxtch(object msg="eof")
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
sidx += 1
if sidx>length(s) then
<span style="color: #008080;">procedure</span> <span style="color: #000000;">nxtch</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">msg</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"eof"</span><span style="color: #0000FF;">)</span>
if string(msg) then err(msg) end if
<span style="color: #000000;">sidx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
ch = -1
<span style="color: #008080;">if</span> <span style="color: #000000;">sidx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
else
<span style="color: #008080;">if</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">msg</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">err</span><span style="color: #0000FF;">(</span><span style="color: #000000;">msg</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
ch = s[sidx]
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
end if
<span style="color: #008080;">else</span>
end procedure
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
procedure skipspaces()
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
while find(ch," \t\r\n")!=0 do nxtch(0) end while
end procedure
<span style="color: #008080;">procedure</span> <span style="color: #000000;">skipspaces</span><span style="color: #0000FF;">()</span>
 
<span style="color: #008080;">while</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\t'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\r'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">})!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span> <span style="color: #000000;">nxtch</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
procedure get_token()
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
atom n, fraction
integer dec
<span style="color: #008080;">procedure</span> <span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
skipspaces()
<span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fraction</span>
if ch=-1 then token = "eof" return end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">dec</span>
if ch>='0' and ch<='9' then
<span style="color: #000000;">skipspaces</span><span style="color: #0000FF;">()</span>
n = ch-'0'
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"eof"</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
while 1 do
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">>=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'9'</span> <span style="color: #008080;">then</span>
nxtch(0)
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">-</span><span style="color: #008000;">'0'</span>
if ch<'0' or ch>'9' then exit end if
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
n = n*10+ch-'0'
<span style="color: #000000;">nxtch</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">or</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'9'</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if ch='.' then
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">-</span><span style="color: #008000;">'0'</span>
dec = 1
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
fraction = 0
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'.'</span> <span style="color: #008080;">then</span>
while 1 do
<span style="color: #000000;">dec</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
nxtch(0)
<span style="color: #000000;">fraction</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
if ch<'0' or ch>'9' then exit end if
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
fraction = fraction*10 + ch-'0'
<span style="color: #000000;">nxtch</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
dec *= 10
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">or</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'9'</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #000000;">fraction</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fraction</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">-</span><span style="color: #008000;">'0'</span>
n += fraction/dec
<span style="color: #000000;">dec</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
-- if find(ch,"eE") then -- you get the idea
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">fraction</span><span style="color: #0000FF;">/</span><span style="color: #000000;">dec</span>
-- end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
token = n
<span style="color: #000080;font-style:italic;">-- if find(ch,"eE") then -- you get the idea
return
-- end if</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
if find(ch,"+-/*()^%")=0 then err("syntax error") end if
<span style="color: #008080;">return</span>
token = s[sidx..sidx]
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
nxtch(0)
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+-/*()^%"</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">err</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"syntax error"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">..</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]</span>
end procedure
<span style="color: #000000;">nxtch</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">return</span>
procedure Match(string t)
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
if token!=t then err(t&" expected") end if
get_token()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Match</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">t</span> <span style="color: #008080;">then</span> <span style="color: #000000;">err</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">&</span><span style="color: #008000;">" expected"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
procedure PopFactor()
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
object p1, p2 = opstack[$]
if op="u-" then
<span style="color: #008080;">procedure</span> <span style="color: #000000;">PopFactor</span><span style="color: #0000FF;">()</span>
p1 = 0
<span style="color: #004080;">object</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">opstack</span><span style="color: #0000FF;">[$]</span>
else
<span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"u-"</span> <span style="color: #008080;">then</span>
opstack = opstack[1..$-1]
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
p1 = opstack[$]
<span style="color: #008080;">else</span>
end if
<span style="color: #000000;">opstack</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">opstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
if op_p_p=1 then
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">opstack</span><span style="color: #0000FF;">[$]</span>
opstack[$] = {op,p1,p2} -- op_p_p
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
elsif op_p_p=0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">op_p_p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
opstack[$] = {p1,op,p2} -- p_op_p
<span style="color: #000000;">opstack</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- op_p_p</span>
else -- -1
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op_p_p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
opstack[$] = {p1,p2,op} -- p_p_op
<span style="color: #000000;">opstack</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- p_op_p</span>
end if
<span style="color: #008080;">else</span> <span style="color: #000080;font-style:italic;">-- -1</span>
op = 0
<span style="color: #000000;">opstack</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- p_p_op</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
procedure PushFactor(atom t)
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
if op!=0 then PopFactor() end if
opstack = append(opstack,t)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">PushFactor</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">PopFactor</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #000000;">opstack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">opstack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
procedure PushOp(string t)
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
if op!=0 then PopFactor() end if
op = t
<span style="color: #008080;">procedure</span> <span style="color: #000000;">PushOp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">PopFactor</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span>
procedure Factor()
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
if atom(token) then
PushFactor(token)
<span style="color: #008080;">forward</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">Expr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
if ch!=-1 then
get_token()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Factor</span><span style="color: #0000FF;">()</span>
end if
<span style="color: #008080;">if</span> <span style="color: #004080;">atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
elsif token="-" then
<span style="color: #000000;">PushFactor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">)</span>
get_token()
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
-- Factor()
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
Expr(3) -- makes "-3^2" yield -9 (ie -(3^2)) not 9 (ie (-3)^2).
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if op!=0 then PopFactor() end if
<span style="color: #008080;">elsif</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"+"</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (ignore)</span>
if integer(opstack[$]) then
<span style="color: #000000;">nxtch</span><span style="color: #0000FF;">()</span>
opstack[$] = -opstack[$]
<span style="color: #000000;">Factor</span><span style="color: #0000FF;">()</span>
else
<span style="color: #008080;">elsif</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"-"</span> <span style="color: #008080;">then</span>
PushOp("u-")
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
end if
<span style="color: #000080;font-style:italic;">-- Factor()</span>
elsif token="(" then
<span style="color: #000000;">Expr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- makes "-3^2" yield -9 (ie -(3^2)) not 9 (ie (-3)^2).</span>
get_token()
<span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">PopFactor</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Expr(0)
<span style="color: #008080;">if</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">opstack</span><span style="color: #0000FF;">[$])</span> <span style="color: #008080;">then</span>
Match(")")
<span style="color: #000000;">opstack</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">opstack</span><span style="color: #0000FF;">[$]</span>
elsif token="+" then -- (ignore)
<span style="color: #008080;">else</span>
nxtch()
<span style="color: #000000;">PushOp</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"u-"</span><span style="color: #0000FF;">)</span>
Factor()
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
else
<span style="color: #008080;">elsif</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"("</span> <span style="color: #008080;">then</span>
err("syntax error")
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
end if
<span style="color: #000000;">Expr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #000000;">Match</span><span style="color: #0000FF;">(</span><span style="color: #008000;">")"</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">else</span>
constant {operators,
<span style="color: #000000;">err</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"syntax error"</span><span style="color: #0000FF;">)</span>
precedence,
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
associativity} = columnize({{"^",3,0},
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
{"%",2,1},
{"*",2,1},
<span style="color: #008080;">constant</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">operators</span><span style="color: #0000FF;">,</span>
{"/",2,1},
<span style="color: #000000;">precedence</span><span style="color: #0000FF;">,</span>
{"+",1,1},
<span style="color: #000000;">associativity</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({{</span><span style="color: #008000;">"^"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span>
{"-",1,1},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"%"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
$})
<span style="color: #0000FF;">{</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
 
<span style="color: #0000FF;">{</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
procedure Expr(integer p)
<span style="color: #0000FF;">{</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
--
<span style="color: #0000FF;">{</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
-- Parse an expression, using precedence climbing.
<span style="color: #0000FF;">$})</span>
--
-- p is the precedence level we should parse to, eg/ie
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Expr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
-- 4: Factor only (may as well just call Factor)
<span style="color: #000080;font-style:italic;">--
-- 3: "" and ^
-- Parse an expression, using precedence climbing.
-- 2: "" and *,/,%
--
-- 1: "" and +,-
-- p is the precedence level we should parse to, eg/ie
-- 0: full expression (effectively the same as 1)
-- 4: Factor only (may as well just call Factor)
-- obviously, parentheses override any setting of p.
-- 3: "" and ^
--
-- 2: "" and *,/,%
integer k, thisp
-- 1: "" and +,-
Factor()
-- 0: full expression (effectively the same as 1)
while 1 do
-- obviously, parentheses override any setting of p.
k = find(token,operators) -- *,/,+,-
--</span>
if k=0 then exit end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">thisp</span>
thisp = precedence[k]
<span style="color: #000000;">Factor</span><span style="color: #0000FF;">()</span>
if thisp<p then exit end if
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
get_token()
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">,</span><span style="color: #000000;">operators</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- *,/,+,-</span>
Expr(thisp+associativity[k])
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
PushOp(operators[k])
<span style="color: #000000;">thisp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">precedence</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
end while
<span style="color: #008080;">if</span> <span style="color: #000000;">thisp</span><span style="color: #0000FF;"><</span><span style="color: #000000;">p</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end procedure
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
 
<span style="color: #000000;">Expr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">thisp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">associativity</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">])</span>
function eval(object s)
<span style="color: #000000;">PushOp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">operators</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">])</span>
object lhs, rhs
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
string op
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
if atom(s) then
return s
<span style="color: #008080;">function</span> <span style="color: #000000;">evaluate</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #004080;">object</span> <span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rhs</span>
if op_p_p=1 then -- op_p_p
<span style="color: #004080;">string</span> <span style="color: #000000;">op</span>
{op,lhs,rhs} = s
<span style="color: #008080;">if</span> <span style="color: #004080;">atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
elsif op_p_p=0 then -- p_op_p
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
{lhs,op,rhs} = s
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
else -- -1 -- p_p_op
<span style="color: #008080;">if</span> <span style="color: #000000;">op_p_p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- op_p_p</span>
{lhs,rhs,op} = s
<span style="color: #0000FF;">{</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
end if
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op_p_p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- p_op_p</span>
if sequence(lhs) then lhs = eval(lhs) end if
<span style="color: #0000FF;">{</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
if sequence(rhs) then rhs = eval(rhs) end if
<span style="color: #008080;">else</span> <span style="color: #000080;font-style:italic;">-- -1 -- p_p_op</span>
if op="+" then
<span style="color: #0000FF;">{</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
return lhs+rhs
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
elsif op="-" then
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">lhs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">evaluate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return lhs-rhs
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">rhs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">evaluate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
elsif op="*" then
<span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"+"</span> <span style="color: #008080;">then</span>
return lhs*rhs
<span style="color: #008080;">return</span> <span style="color: #000000;">lhs</span><span style="color: #0000FF;">+</span><span style="color: #000000;">rhs</span>
elsif op="/" then
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"-"</span> <span style="color: #008080;">then</span>
return lhs/rhs
<span style="color: #008080;">return</span> <span style="color: #000000;">lhs</span><span style="color: #0000FF;">-</span><span style="color: #000000;">rhs</span>
elsif op="^" then
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"*"</span> <span style="color: #008080;">then</span>
return power(lhs,rhs)
<span style="color: #008080;">return</span> <span style="color: #000000;">lhs</span><span style="color: #0000FF;">*</span><span style="color: #000000;">rhs</span>
elsif op="%" then
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"/"</span> <span style="color: #008080;">then</span>
return remainder(lhs,rhs)
<span style="color: #008080;">return</span> <span style="color: #000000;">lhs</span><span style="color: #0000FF;">/</span><span style="color: #000000;">rhs</span>
elsif op="u-" then
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"^"</span> <span style="color: #008080;">then</span>
return -rhs
<span style="color: #008080;">return</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">)</span>
else
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"%"</span> <span style="color: #008080;">then</span>
?9/0
<span style="color: #008080;">return</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"u-"</span> <span style="color: #008080;">then</span>
end function
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">rhs</span>
 
<span style="color: #008080;">else</span>
s = "3+4+5+6*7/1*5^2^3"
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span>
sidx = 0
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
nxtch()
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
get_token()
Expr(0)
<span style="color: #000080;font-style:italic;">--s = "1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10" -- 71
if op!=0 then PopFactor() end if
--s = "1+1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+1/15)/14)/13)/12)/11)/10)/9)/8)/7)/6)/5)/4)/3)/2" -- 2.718281828
if length(opstack)!=1 then err("some error") end if
--s = "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1" --60
puts(1,"AST (flat): ")
--s = "1 - 5 * 2 / 20 + 1" -- 1.5
?opstack[1]
--s = "(1 - 5) * 2 / (20 + 1)" -- -0.380952381
puts(1,"AST (tree):\n")
--s = "2 * (3 + ((5) / (7 - 11)))" -- 3.5
ppEx(opstack[1],{pp_Nest,6})
--s = "(2 + 3) / (10 - 5)" -- 1
puts(1,"result: ")
--s = "(3 * 2) a - (1 + 2) / 4" -- syntax error
?eval(opstack[1])
--s = "(3 * 2) - (1 + 2) / (4" -- ) expected
{} = wait_key()</lang>
--s = "1 + 2" -- 3
--s = "(1 + 2) * 10 / 100" -- 0.3
--s = "(1 + 2 / 2) * (5 + 5)" -- 20
--s = "2*-3--4+-0.25" -- -2.25
--s = "((11+15)*15)*2-(3)*4*1" -- 768
--s = "((11+15)*15)* 2 + (3) * -4 *1" -- 768
--s = "(((((1)))))" -- 1
--s = "-35" -- -35
--s = "-30 + -5" -- -35
--s = "-(-30 + -5)" -- 35
--s = "-(3^2)"
--s = "-3^2"
--s = "-15/2.0" -- -7.5
--s = "-(15/2.0)" -- -7.5
--s = "1+2+3+4" -- 10
--s = "((((2))))+3*5" -- 17
--s = "1+2*3/(4-5+6)" -- 2.2
--s = "2+3" -- 5
--s = "2+3/4" -- 2.75
--s = "2*3-4" -- 2
--s = "2*(3+4)+5/6" -- 14.8333
--s = "-2 / 2 + 4 + 3 * 2" -- 9
--s = "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10" -- 7000
--s = "2*-3--4+-0.25" -- -2.25
--s = "(((2 * -3) - -4) + -1/4)" -- -2.25
--s = "2+(3-4)*6/5^2^3%3" -- 1.99998464
--s = "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1" -- 60</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"3+4+5+6*7/1*5^2^3"</span> <span style="color: #000080;font-style:italic;">-- 16406262
--?3+4+5+6*7/1*power(5,power(2,3))
--?((3+4)+5)+(((6*7)/1)*power(5,power(2,3)))</span>
<span style="color: #000000;">sidx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">nxtch</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">Expr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">PopFactor</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">opstack</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">err</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"some error"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"expression: \"%s\"\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"AST (flat): "</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">opstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"AST (tree):\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">ppEx</span><span style="color: #0000FF;">(</span><span style="color: #000000;">opstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9999</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"result: "</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">evaluate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">opstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">--/*
I added a flag (for this task) to store the ast nodes as op_p_p, p_op_p, or p_p_op, whichever you prefer.
with op_p_p:
AST (flat): {"+",{"+",{"+",3,4},5},{"*",{"/",{"*",6,7},1},{"^",5,{"^",2,3}}}}
AST (tree):
{"+",
{"+",
{"+",
3,
4},
5},
{"*",
{"/",
{"*",
6,
7},
1},
{"^",
5,
{"^",
2,
3}}}}
result: 16406262
with p_op_p:
AST (flat): {{{3,"+",4},"+",5},"+",{{{6,"*",7},"/",1},"*",{5,"^",{2,"^",3}}}}
AST (tree):
{{{3,
"+",
4},
"+",
5},
"+",
{{{6,
"*",
7},
"/",
1},
"*",
{5,
"^",
{2,
"^",
3}}}}
result: 16406262
and lastly with p_p_op:
16406262
AST (flat): {{{3,4,"+"},5,"+"},{{{6,7,"*"},1,"/"},{5,{2,3,"^"},"^"},"*"},"+"}
AST (tree):
{{{3,
4,
"+"},
5,
"+"},
{{{6,
7,
"*"},
1,
"/"},
{5,
{2,
3,
"^"},
"^"},
"*"},
"+"}
result: 16406262
--*/</span>
<!--</lang>-->
I added a flag (for this task) to store the ast nodes as op_p_p, p_op_p, or p_p_op, whichever you prefer.
{{out}}
Petelomax
7,804

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/50755"