Arithmetic evaluation: Difference between revisions
Content added Content deleted
(+Icon+Unicon) |
|||
Line 944: | Line 944: | ||
Right expr -> evaluate expr |
Right expr -> evaluate expr |
||
Left _ -> error "Did not parse"</lang> |
Left _ -> error "Did not parse"</lang> |
||
== Icon and Unicon == |
|||
A compact recursive descent parser using Hansen's device. This program |
|||
* handles left and right associativity and different precedences, |
|||
* accepts integers, reals, and radix constants. |
|||
* accepts the Icon operators + - * / % (remainder) and ^ (exponentiation) |
|||
* can easily be extended to use other Icon operators (and should be able to handle mutiple character operators) |
|||
* uses Icon style type coercion |
|||
* accepts single unary operators ( ++3 will break it) |
|||
* represents the AST is a nested list. |
|||
==={{header|Icon}}=== |
|||
<lang Icon>procedure main() #: simple arithmetical parser / evaluator |
|||
write("Usage: Input expression = Abstract Syntax Tree = Value, ^Z to end.") |
|||
repeat { |
|||
writes("Input expression : ") |
|||
if not writes(line := read()) then break |
|||
if map(line) ? { (x := E()) & pos(0) } then |
|||
write(" = ", showAST(x), " = ", evalAST(x)) |
|||
else write(" rejected") |
|||
} |
|||
end |
|||
procedure evalAST(X) #: return the evaluated AST |
|||
local x |
|||
if type(X) == "list" then { |
|||
x := evalAST(get(X)) |
|||
while x := get(X)(x, evalAST(get(X) | stop("Malformed AST."))) |
|||
} |
|||
return \x | X |
|||
end |
|||
procedure showAST(X) #: return a string representing the AST |
|||
local x,s |
|||
s := "" |
|||
every x := !X do |
|||
s ||:= if type(x) == "list" then "(" || showAST(x) || ")" else x |
|||
return s |
|||
end |
|||
global token |
|||
record HansonsDevice(precedence,associativity) |
|||
procedure opinfo() |
|||
static O |
|||
initial { |
|||
O := HansonsDevice([],table(&null)) # parsing table |
|||
put(O.precedence, [ "+", "-" ], [ "*", "/", "%" ], [ "^" ] ) # Lowest to Highest precedence |
|||
every O.associativity[!!O.precedence] := 1 # default to 1 for LEFT associativity |
|||
O.associativity["^"] := 0 # RIGHT associativity |
|||
} |
|||
return O |
|||
end |
|||
procedure E(k) #: Expression |
|||
local lex, pL |
|||
static opT |
|||
initial opT := opinfo() |
|||
/k := 1 |
|||
lex := [] |
|||
if not ( pL := opT.precedence[k] ) then # this op at this level? |
|||
put( lex, F() ) |
|||
else { |
|||
put( lex, E(k+1) ) |
|||
while put( lex, token := =!pL ) do |
|||
put( lex, E(k+opT.associativity[token]) ) |
|||
} |
|||
suspend if *lex = 1 then lex[1] else lex # strip useless [] |
|||
end |
|||
procedure F() #: Factor |
|||
suspend 2( ="-(", [-1,"*",E()], =")") | 2( =("+("|"("), E() , =")") | ( =("-" | "+" | "") || V() ) |
|||
end |
|||
procedure V() #: Value |
|||
local r |
|||
suspend ( =(r := 1 to 36) || ="r" || tab(many((&digits || &lcase)[1:r+1])) ) | (tab(many(&digits)) || ((="." || tab(many(&digits))) | "")) |
|||
end</lang> |
|||
Sample Output: |
|||
<pre>#matheval.exe |
|||
Usage: Input expression = Abstract Syntax Tree = Value, ^Z to end. |
|||
Input expression : 1 |
|||
1 = 1 = 1 |
|||
Input expression : -1 |
|||
-1 = -1 = -1 |
|||
Input expression : (-15/2.0) |
|||
(-15/2.0) = -15/2.0 = -7.5 |
|||
Input expression : -(15/2.0) |
|||
-(15/2.0) = -1*(15/2.0) = -7.5 |
|||
Input expression : 2+(3-4)*6/5^2^3%3 |
|||
2+(3-4)*6/5^2^3%3 = 2+((3-4)*6/(5^(2^3))%3) = 2 |
|||
Input expression : 1+2+3+4 |
|||
1+2+3+4 = 1+2+3+4 = 10 |
|||
Input expression : ((((2))))+3*5 |
|||
((((2))))+3*5 = 2+(3*5) = 17 |
|||
Input expression : 3r10*3 |
|||
3r10*3 = 3r10*3 = 9 |
|||
Input expression : ^Z</pre> |
|||
==={{header|Unicon}}=== |
|||
This Icon solution works in Unicon. |
|||
=={{header|J}}== |
=={{header|J}}== |