Arithmetic evaluation: Difference between revisions
→{{header|C++}}
Alextretyak (talk | contribs) m (→{{header|11l}}) |
|||
| (27 intermediate revisions by 18 users not shown) | |||
Line 1:
{{task}}Create a program which parses and evaluates arithmetic expressions.
;Requirements:
Line 25:
=={{header|11l}}==
[[wp:Pratt parser|Pratt parser]]
<
String id
Int lbp
Line 140:
L(expr_str) [‘-2 / 2 + 4 + 3 * 2’,
‘2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10’]
print(expr_str‘ = ’parse(expr_str).eval())</
{{out}}
<pre>
Line 154:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - A68RS has not implemented forward declarations}}
<
MODE FIXED = LONG REAL; # numbers in the format 9,999.999 #
Line 295:
index error:
printf(("Stack over flow"))
)</
{{out}}
<pre>
euler's number is about: 2.71828182845899446428546958
</pre>
=={{header|Amazing Hopper}}==
Hopper no soporta números muy grandes, por decisión de diseño, pero es posible realizar una aproximación aplicando el Límite de Euler para calcular un factorial de un número real, hecho para uno de los ejemplos.
<syntaxhighlight lang="c">
#include <basico.h>
#proto verificarconstante(_X_)
#synon _verificarconstante se verifica constante en
#proto verificarfunción(_X_)
#synon _verificarfunción se verifica función en
algoritmo
pila de trabajo 50
números (largo de datos)
decimales '13'
preparar datos(DATA_EXPRESIONES)
obtener tamaño de datos, guardar en 'largo de datos'
imprimir ("Negativos deben escribirse entre parentesis\nEjemplo: (-3)\n\n")
iterar
matrices ( pila, p, q )
cadenas (expresión)
obtener dato, copiar en 'expresión'
ir a subs ( convierte a matriz --> convierte a notación polaca \
--> evalúa expresión --> despliega resultados )
--largo de datos
mientras ' largo de datos'
terminar
subrutinas
convierte a matriz:
argumentos 'expr'
transformar(" ","",\
transformar("(-","(0-",expr)), guardar en 'expr'
l=0, #( l = len(expr) )
v="", num="", cte=""
para cada caracter (v, expr, l)
cuando ( #(typechar(v,"digit") || v==".")){
num, v, concatenar esto, guardar en 'num'
continuar
}
cuando ( #(typechar(v,"alpha") )){
cte, v, concatenar esto, guardar en 'cte'
continuar
}
cuando (num) {num, meter en 'q', num=""}
cuando (cte) {cte, meter en 'q', cte=""}
v, meter en 'q'
siguiente
cuando (num) {num, meter en 'q'}
cuando (cte) {cte, meter en 'q'}
"(", meter en 'pila'
")", meter en 'q'
// imprimir( "Q = {", q, "}\n" )
retornar
convierte a notación polaca:
l="", m=""
iterar mientras '#( not(is empty(q)) )'
sw = 1
///imprimir("P = ",p,"\nQ = ",q,"\nPILA = ",pila,NL)
extraer tope 'q' para 'l'
// ¿es un operando?
cuando ' #(not( occurs(l,"+-*^/)(%") )) ' {
si ' se verifica constante en (l) '
meter en 'p'
sino si ' se verifica función en (l) '
l, meter en 'pila'
sino
#( number(l) ), meter en 'p'
fin si
continuar
}
// es un simbolo...
// es un parentesis izquierdo?
cuando ( #( l=="(" ) ) {
l, meter en 'pila'
continuar
}
// es un operador?
cuando ( #( occurs(l,"+-*^/%")) ) {
iterar mientras ' sw '
extraer cabeza 'pila' para 'm'
cuando ' #(m=="(") '{
m,l, apilar en 'pila'
sw=0, continuar
}
cuando ' #(l=="^") '{
si ' #(m=="^") '
//m,l, apilar en 'p'
m, meter en 'p'
sino
m,l, apilar en 'pila'
sw=0
fin si, continuar
}
cuando ' #(l=="*") ' {
si ' #(occurs(m, "^*/%"))'
m, meter en 'p'
sino
m,l, apilar en 'pila'
sw=0
fin si, continuar
}
//cuando ' #(l=="/") ' {
// decisión de diseño para resto módulo
cuando ' #( occurs(l,"/%")) ' {
si ' #( occurs(m, "/^*%") )'
m, meter en 'p'
l, meter en 'pila'
sino
m,l, apilar en 'pila'
fin si
sw=0, continuar
}
cuando ' #(occurs(l, "+-"))' {
m, meter en 'p'
// saber si ya hay un símbolo "-" en pila
tmp=0
tope(pila), mover a 'tmp'
si ' #( occurs(tmp,"+-") ) '
extraer cabeza (pila)
meter en 'p'
fin si
l, meter en 'pila'
sw=0
}
reiterar
si ' #( length (pila)==0 ) '
"(", meter en 'pila'
fin si
continuar
}
// es un paréntesis derecho?
cuando( #(l==")") ) {
extraer cabeza (pila) para 'm'
iterar mientras ' #( m<>"(") '
m, meter en 'p'
extraer cabeza 'pila' para 'm'
reiterar
}
reiterar
retornar
evalúa expresión:
l = " ", a=0, b=0
iterar mientras ' #( not(is empty(p)) ) '
extraer tope 'p' para 'l'
si ' es numérico (l) '
l, meter en 'pila'
sino
si ' se verifica función en (l) '
extraer cabeza 'pila' para 'b'
seleccionar 'l'
caso ("sqrt"){ #(sqrt(b)), salir }
caso ("log"){ #(log10(b)), salir }
caso ("ln"){ #(log(b)), salir }
caso ("fact"){
si ' #(int(b)<>b) ' // límite de Euler
x=0,i=2, xb=1,
// aproximación muy burda.
#basic{
b = b + 1
x = fact(163)*(163^b)
xb = b*(b+1)
while( i<=163 )
xb = xb * ( i+b )
i+=1
wend
x/xb
}
sino // normal
#(fact(b))
fin si
salir
}
fin seleccionar
sino
extraer cabeza 'pila' para 'b'
extraer cabeza 'pila' para 'a'
seleccionar 'l'
caso ("+"){ #(a+b), salir }
caso ("-"){ #(a-b), salir }
caso ("*"){ #(a*b), salir }
// n/0 = inf, no es necesario detectar esto:
caso ("/"){ #(a/b), salir }
caso ("^"){ #(a^b), salir }
caso ("%"){ #(a%b), salir }
fin seleccionar
fin si
meter en 'pila'
fin si
reiterar
retornar
despliega resultados:
imprimir(expresión," : ", \
tomar si( #(length(pila)==1),pila, \
#(utf8("expresión mal formada!"))), NL)
retornar
verificar constante (x)
seleccionar 'x'
caso ("pi"){ M_PI, 1, salir }
caso ("e") { M_E, 1, salir }
caso ("phi"){ M_PHI, 1, salir }
// etcétera...
caso por defecto{ 0, salir }
fin seleccionar
retornar
verificar función (f)
seleccionar 'f'
caso ("sqrt"){ '1', salir }
caso ("log"){ '1', salir }
caso ("ln"){ '1', salir }
caso ("fact"){ '1', salir }
// etcétera...
caso por defecto { '0', salir }
fin seleccionar
retornar
DATA_EXPRESIONES:
datos("((30+4.5) * ( 7 / 9.67 )+3)-4*(-1)") //31.9741468459168
datos("1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1") // 60!
datos("(1 - 5) * 2 / (20 + 1)") // -8/21
datos("(3 * 2) - (1 + 2) / (4") // error!
datos("(3 * 2) a - (1 + 2) / 4") // error!
datos("(6^2)*2/3") //24
datos("6^2*2/3") //24
datos("(6^2)*2/0") //inf
datos("2 * (3 + ((5) / (7 - 11)))") // 3.5
datos("1 - 5 * 2 / 20 + 1") //1,5!
datos ("(1 + 2) * 10 / 100") // 0.3
datos("1+3.78") // 4.78
datos("2.5 * 2 + 2 * pi") // 11.28
datos("1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10") // 71
datos("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.7182818284589946
datos("((11+15)*15)*2-(3)*4*1") // 768
datos(" 2*(-3)-(-4)+(-0.25)") //-2.25
datos(" 2-25 % 3+1") // 2
datos(" 2-(25 % 3)+1") // 2
datos(" (2-25) % (3+1)") // -3
datos(" 2- 25 % 3 % 2") // 1
datos(" 2- 25 / 3 % 2") // 1.66666
datos(" 2- ((25 / 3) % 2)") // 1.66666
datos(" 2- 25 / 3 / 2") // 2.166666
datos(" (-23) %3") // -2
datos(" (6*pi-1)^0.5-e") // 1,506591651...
datos("2^2^3^4")
datos("(4-2*phi)*pi") // 2,3999632297286
datos("( (1+sqrt(5))/2)^(2/pi)") // 1.3584562741830
datos("1-(1+ln(ln(2)))/ln(2)") // 0.0860713320559
datos("pi / (2 * ln(1+sqrt(2)))") // 1,7822139781 ....
datos("( (e^(pi/8)) * sqrt(pi)) /(4 * (2^(3/4)) * (fact(1/4))^2) ") //0,47494 93799...
datos(" fact(1/2)") // 0.906402477055...
back
</syntaxhighlight>
{{out}}
<pre>
Negativos deben escribirse entre parentesis
Ejemplo: (-3)
((30+4.5) * ( 7 / 9.67 )+3)-4*(-1) : 31.9741468459168
1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1 : 60.0000000000000
(1 - 5) * 2 / (20 + 1) : -0.3809523809524
(3 * 2) - (1 + 2) / (4 : expresión mal formada!
(3 * 2) a - (1 + 2) / 4 : expresión mal formada!
(6^2)*2/3 : 24.0000000000000
6^2*2/3 : 24.0000000000000
(6^2)*2/0 : inf
2 * (3 + ((5) / (7 - 11))) : 3.5000000000000
1 - 5 * 2 / 20 + 1 : 1.5000000000000
(1 + 2) * 10 / 100 : 0.3000000000000
1+3.78 : 4.7800000000000
2.5 * 2 + 2 * pi : 11.2831853071796
1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10 : 71.0000000000000
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.7182818284590
((11+15)*15)*2-(3)*4*1 : 768.0000000000000
2*(-3)-(-4)+(-0.25) : -2.2500000000000
2-25 % 3+1 : 2.0000000000000
2-(25 % 3)+1 : 2.0000000000000
(2-25) % (3+1) : -3.0000000000000
2- 25 % 3 % 2 : 1.0000000000000
2- 25 / 3 % 2 : 1.6666666666667
2- ((25 / 3) % 2) : 1.6666666666667
2- 25 / 3 / 2 : -2.1666666666667
(-23) %3 : -2.0000000000000
(6*pi-1)^0.5-e : 1.5065916514856
2^2^3^4 : 16777216.0000000000000
(4-2*phi)*pi : 2.3999632297286
( (1+sqrt(5))/2)^(2/pi) : 1.3584562741830
1-(1+ln(ln(2)))/ln(2) : 0.0860713320559
pi / (2 * ln(1+sqrt(2))) : 1.7822139781915
( (e^(pi/8)) * sqrt(pi)) /(4 * (2^(3/4)) * (fact(1/4))^2) : 0.4831858606252
fact(1/2) : 0.8761319893678
</pre>
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<syntaxhighlight lang="autohotkey">/*
hand coded recursive descent parser
expr : term ( ( PLUS | MINUS ) term )* ;
Line 452 ⟶ 782:
}
#include calclex.ahk</
calclex.ahk<
{
stringo := string ; store original string
Line 519 ⟶ 849:
string := "pos= " token.pos "`nvalue= " token.value "`ntype= " token.type
return string
}</
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
PRINT "Input = " Expr$
AST$ = FNast(Expr$)
Line 580 ⟶ 910:
ENDIF
UNTIL FALSE
= num$</
{{out}}
<pre>
Line 592 ⟶ 922:
=={{header|C++}}==
{{works with|g++|clang++}}
This version does not require boost.
It works by:
- converting infix strings to postfix strings using shunting yard algorithm
- converting postfix expression to list of tokens
- builds AST bottom up from list of tokens
- evaluates expression tree by performing postorder traversal.
<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
template <class T>
class stack {
private:
vector<T> st;
T sentinel;
public:
stack() { sentinel = T(); }
bool empty() { return st.empty(); }
void push(T info) { st.push_back(info); }
T& top() {
if (!st.empty()) {
return st.back();
}
return sentinel;
}
T pop() {
T ret = top();
if (!st.empty()) st.pop_back();
return ret;
}
};
//determine associativity of operator, returns true if left, false if right
bool leftAssociate(char c) {
switch (c) {
case '^': return false;
case '*': return true;
case '/': return true;
case '%': return true;
case '+': return true;
case '-': return true;
default:
break;
}
return false;
}
//determins precedence level of operator
int precedence(char c) {
switch (c) {
case '^': return 7;
case '*': return 5;
case '/': return 5;
case '%': return 5;
case '+': return 3;
case '-': return 3;
default:
break;
}
return 0;
}
//converts infix expression string to postfix expression string
string shuntingYard(string expr) {
stack<char> ops;
string output;
for (char c : expr) {
if (c == '(') {
ops.push(c);
} else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '%') {
if (precedence(c) < precedence(ops.top()) ||
(precedence(c) == precedence(ops.top()) && leftAssociate(c))) {
output.push_back(' ');
output.push_back(ops.pop());
output.push_back(' ');
ops.push(c);
} else {
ops.push(c);
output.push_back(' ');
}
} else if (c == ')') {
while (!ops.empty()) {
if (ops.top() != '(') {
output.push_back(ops.pop());
} else {
ops.pop();
break;
}
}
} else {
output.push_back(c);
}
}
while (!ops.empty())
if (ops.top() != '(')
output.push_back(ops.pop());
else ops.pop();
cout<<"Postfix: "<<output<<endl;
return output;
}
struct Token {
int type;
union {
double num;
char op;
};
Token(double n) : type(0), num(n) { }
Token(char c) : type(1), op(c) { }
};
//converts postfix expression string to vector of tokens
vector<Token> lex(string pfExpr) {
vector<Token> tokens;
for (int i = 0; i < pfExpr.size(); i++) {
char c = pfExpr[i];
if (isdigit(c)) {
string num;
do {
num.push_back(c);
c = pfExpr[++i];
} while (i < pfExpr.size() && isdigit(c));
tokens.push_back(Token(stof(num)));
i--;
continue;
} else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '%') {
tokens.push_back(Token(c));
}
}
return tokens;
}
//structure used for nodes of expression tree
struct node {
Token token;
node* left;
node* right;
node(Token tok) : token(tok), left(nullptr), right(nullptr) { }
};
//builds expression tree from vector of tokens
node* buildTree(vector<Token> tokens) {
cout<<"Building Expression Tree: "<<endl;
stack<node*> sf;
for (int i = 0; i < tokens.size(); i++) {
Token c = tokens[i];
if (c.type == 1) {
node* x = new node(c);
x->right = sf.pop();
x->left = sf.pop();
sf.push(x);
cout<<"Push Operator Node: "<<sf.top()->token.op<<endl;
} else
if (c.type == 0) {
sf.push(new node(c));
cout<<"Push Value Node: "<<c.num<<endl;
continue;
}
}
return sf.top();
}
//evaluate expression tree, while anotating steps being performed.
int recd = 0;
double eval(node* x) {
recd++;
if (x == nullptr) {
recd--;
return 0;
}
if (x->token.type == 0) {
for (int i = 0; i < recd; i++) cout<<" ";
cout<<"Value Node: "<<x->token.num<<endl;
recd--;
return x->token.num;
}
if (x->token.type == 1) {
for (int i = 0; i < recd; i++) cout<<" ";
cout<<"Operator Node: "<<x->token.op<<endl;
double lhs = eval(x->left);
double rhs = eval(x->right);
for (int i = 0; i < recd; i++) cout<<" ";
cout<<lhs<<" "<<x->token.op<<" "<<rhs<<endl;
recd--;
switch (x->token.op) {
case '^': return pow(lhs, rhs);
case '*': return lhs*rhs;
case '/':
if (rhs == 0) {
cout<<"Error: divide by zero."<<endl;
} else
return lhs/rhs;
case '%':
return (int)lhs % (int)rhs;
case '+': return lhs+rhs;
case '-': return lhs-rhs;
default:
break;
}
}
return 0;
}
int main() {
string expr = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
cout<<eval(buildTree(lex(shuntingYard(expr))))<<endl;
return 0;
}
Output:
Postfix: 3 4 2 * 1 5 - 2 3^^/+
Building Expression Tree:
Push Value Node: 3
Push Value Node: 4
Push Value Node: 2
Push Operator Node: *
Push Value Node: 1
Push Value Node: 5
Push Operator Node: -
Push Value Node: 2
Push Value Node: 3
Push Operator Node: ^
Push Operator Node: ^
Push Operator Node: /
Push Operator Node: +
Operator Node: +
Value Node: 3
Operator Node: /
Operator Node: *
Value Node: 4
Value Node: 2
4 * 2
Operator Node: ^
Operator Node: -
Value Node: 1
Value Node: 5
1 - 5
Operator Node: ^
Value Node: 2
Value Node: 3
2 ^ 3
-4 ^ 8
8 / 65536
3 + 0.00012207
3.00012
</syntaxhighlight>
{{Works with|g++|4.1.2 20061115 (prerelease) (SUSE Linux)}}
{{libheader|Boost.Spirit|1.8.4}}
<
#include <boost/spirit/tree/ast.hpp>
#include <string>
Line 710 ⟶ 1,291:
}
}
};</
=={{header|Clojure}}==
<
+ 1, - 1})
Line 765 ⟶ 1,346:
user> (evaluate "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1")
60</
=={{header|Common Lisp}}==
Line 783 ⟶ 1,364:
This implementation can read integers, and produce integral and rational values.
<
(labels ((whitespace-p (char)
(find char #(#\space #\newline #\return #\tab)))
Line 868 ⟶ 1,449:
(loop for token = (tokenize-stream in)
until (null token)
collect token)))))))</
Examples
Line 912 ⟶ 1,493:
=={{header|D}}==
After the AST tree is constructed, a visitor pattern is used to display the AST structure and calculate the expression value.
<
std.exception, std.traits;
Line 1,132 ⟶ 1,713:
immutable exp = (args.length > 1) ? args[1 .. $].join(' ') : exp0;
new AST().parse(exp).CalcVis; // Should be 60.
}</
{{out}}
<pre> ........................................................+.
Line 1,154 ⟶ 1,735:
=={{header|Dyalect}}==
<
with Lookup
type Token(val, Char kind) with Lookup
func Token.ToString() => this.val.ToString()
Line 1,269 ⟶ 1,852:
print( eval("(1+33.23)*7") )
print( eval("1+33.23*7") )</
{{out}}
Line 1,280 ⟶ 1,863:
While the task requirements specify not evaluating using the language's built-in eval, they don't say that you have to write your own ''parser''...
<
def LiteralExpr := <elang:evm.makeLiteralExpr>.asType()
def arithEvaluate(expr :String) {
Line 1,297 ⟶ 1,880:
return evalAST(ast)
}</
Parentheses are handled by the parser.
<
# value: 3
Line 1,308 ⟶ 1,891:
? arithEvaluate("(1 + 2 / 2) * (5 + 5)")
# value: 20.0</
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
subr nch
if inp_ind > len inp$[]
ch$ = strchar 0
else
ch$ = inp$[inp_ind]
inp_ind += 1
.
ch = strcode ch$
.
#
subr ntok
while ch$ = " "
nch
.
if ch >= 48 and ch <= 58
tok$ = "n"
s$ = ""
while ch >= 48 and ch <= 58 or ch$ = "."
s$ &= ch$
nch
.
tokv = number s$
elif ch = 0
tok$ = "end of text"
else
tok$ = ch$
nch
.
.
subr init0
astop$[] = [ ]
astleft[] = [ ]
astright[] = [ ]
err = 0
.
proc init s$ . .
inp$[] = strchars s$
inp_ind = 1
nch
ntok
init0
.
proc ast_print nd . .
write "AST:"
for i to len astop$[]
write " ( "
write astop$[i] & " "
write astleft[i] & " "
write astright[i]
write " )"
.
print " Start: " & nd
.
func node .
astop$[] &= ""
astleft[] &= 0
astright[] &= 0
return len astop$[]
.
#
funcdecl parse_expr .
#
func parse_factor .
if tok$ = "n"
nd = node
astop$[nd] = "n"
astleft[nd] = tokv
ntok
elif tok$ = "("
ntok
nd = parse_expr
if tok$ <> ")"
err = 1
print "error: ) expected, got " & tok$
.
ntok
else
err = 1
print "error: factor expected, got " & tok$
.
return nd
.
func parse_term .
ndx = parse_factor
while tok$ = "*" or tok$ = "/"
nd = node
astleft[nd] = ndx
astop$[nd] = tok$
ntok
astright[nd] = parse_factor
ndx = nd
.
return ndx
.
func parse_expr .
ndx = parse_term
while tok$ = "+" or tok$ = "-"
nd = node
astleft[nd] = ndx
astop$[nd] = tok$
ntok
astright[nd] = parse_term
ndx = nd
.
return ndx
.
func parse s$ .
init s$
return parse_expr
.
func eval nd .
if astop$[nd] = "n"
return astleft[nd]
.
le = eval astleft[nd]
ri = eval astright[nd]
a$ = astop$[nd]
if a$ = "+"
return le + ri
elif a$ = "-"
return le - ri
elif a$ = "*"
return le * ri
elif a$ = "/"
return le / ri
.
.
repeat
inp$ = input
until inp$ = ""
print "Inp: " & inp$
nd = parse inp$
ast_print nd
if err = 0
print "Eval: " & eval nd
.
print ""
.
input_data
4 *
4.2 * ((5.3+8)*3 + 4)
2.5 * 2 + 2 * 3.14
</syntaxhighlight>
{{out}}
<pre>
Inp: 4 * 6
AST: 2 ( n 4 0 ) ( * 1 3 ) ( n 6 0 )
Eval: 24
Inp: 4.2 * ((5.3+8)*3 + 4)
AST: 2 ( n 4.20 0 ) ( * 1 8 ) ( n 5.30 0 ) ( + 3 5 ) ( n 8 0 ) ( * 4 7 ) ( n 3 0 ) ( + 6 9 ) ( n 4 0 )
Eval: 184.38
Inp: 2.5 * 2 + 2 * 3.14
AST: 4 ( n 2.50 0 ) ( * 1 3 ) ( n 2 0 ) ( + 2 6 ) ( n 2 0 ) ( * 5 7 ) ( n 3.14 0 )
Eval: 11.28
</pre>
=={{header|Elena}}==
ELENA
<
import extensions;
import extensions'text;
class Token
{
}
class Node
{
}
class SummaryNode : Node
{
}
class DifferenceNode : Node
{
}
class ProductNode : Node
{
}
class FractionNode : Node
{
}
class Expression
{
object Right
}
singleton operatorState
{
^ weak
^ weak
}
singleton tokenState
{
^ weak
^ weak
^ weak
^ weak
^ weak
^ weak
}
singleton startState
{
^ weak
^ weak
^ weak
}
class Scope
{
}
class Parser
{
var
expression.Top := self.append(/*expression.Top*/t, SummaryNode.new(level))
}
expression.Top := self.append(expression.Top, DifferenceNode.new(level))
}
expression.Top := self.append(expression.Top, ProductNode.new(level))
}
expression.Top := self.append(expression.Top, FractionNode.new(level))
}
expression.Top := self.append(expression.Top, Expression.new(level))
}
append(object lastNode, object newNode)
{
if(nil == lastNode)
if (newNode.Level <= lastNode.Level)
var parent := lastNode;
while (nil != current && newNode.Level > current.Level)
if (nil
{
else
{
newNode.Left := current; parent.Right := newNode
^ lastNode
run(text)
{
var scope
^ scope.Number
}
}
public program()
{
}</
=={{header|Elixir}}==
In Elixir AST is a built-in feature.
<syntaxhighlight lang="elixir">
defmodule Ast do
def main do
expr = IO.gets("Give an expression:\n") |> String.Chars.to_string |> String.trim
case Code.string_to_quoted(expr) do
{:ok, ast} ->
IO.puts("AST is: " <> inspect(ast))
{result, _} = Code.eval_quoted(ast)
IO.puts("Result = #{result}")
{:error, {_meta, message_info, _token}} ->
IO.puts(message_info)
end
end
end
</syntaxhighlight>
{{out}}
<pre>
>elixir -e Ast.main()
Give an expression:
2*(4 - 1)
AST is: {:*, [line: 1], [2, {:-, [line: 1], [4, 1]}]}
Result = 6
>elixir -e Ast.main()
Give an expression:
2*(4 - 1) + (
missing terminator: ) (for "(" starting at line 1)
</pre>
=={{header|Emacs Lisp}}==
<
;; -*- mode: emacs-lisp; lexical-binding: t -*-
;;> ./arithmetic-evaluation '(1 + 2) * 3'
Line 1,748 ⟶ 2,527:
(terpri)))
(setq command-line-args-left nil)
</syntaxhighlight>
{{out}}
Line 1,770 ⟶ 2,549:
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM EVAL
Line 2,004 ⟶ 2,783:
IF NERR>0 THEN PRINT("Internal Error #";NERR) ELSE PRINT("Value is ";DB#) END IF
END PROGRAM
</syntaxhighlight>
This solution is based on a stack: as a plus there is a power (^) operator. Unary operator "-" is accepted. Program shows the stack after every operation and you must press a key to go on (this feature can be avoided by removing the final REPEAT..UNTIL loop at the end of "DISEGNA_STACK" procedure).
Line 2,011 ⟶ 2,790:
<code>AbstractSyntaxTree.fs</code>:
<
type Expression =
Line 2,018 ⟶ 2,797:
| Minus of Expression * Expression
| Times of Expression * Expression
| Divide of Expression * Expression</
<code>Lexer.fsl</code>:
<
module Lexer
Line 2,044 ⟶ 2,823:
| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine; token lexbuf }
| eof { EOF }
| _ { failwithf "unrecognized input: '%s'" <| lexeme lexbuf }</
<code>Parser.fsy</code>:
<
open AbstractSyntaxTree
%}
Line 2,072 ⟶ 2,851:
| Expr TIMES Expr { Times ($1, $3) }
| Expr DIVIDE Expr { Divide ($1, $3) }
| LPAREN Expr RPAREN { $2 } </
<code>Program.fs</code>:
<
open Lexer
open Parser
Line 2,095 ⟶ 2,874:
|> parse
|> eval
|> printfn "%d"</
=={{header|Factor}}==
<
IN: rosetta.arith
Line 2,139 ⟶ 2,918:
: evaluate ( string -- result )
expr-ast eval-ast ;</
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">
'Arithmetic evaluation
'
Line 2,338 ⟶ 3,117:
if sym <> done_sym then error_msg("unexpected input")
loop
</syntaxhighlight>
{{out}}
Line 2,346 ⟶ 3,125:
> 71
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_window = 1
begin enum 1
_expressionLabel
_expressionFld
_resultLabel
end enum
void local fn BuildUI
editmenu 1
window _window, @"Arithmetic Evaluation", (0,0,522,61)
textlabel _expressionLabel, @"Expression:", (18,23,74,16)
textfield _expressionFld,,, (98,20,300,21)
textlabel _resultLabel,, (404,23,100,16)
WindowMakeFirstResponder( _window, _expressionFld )
end fn
void local fn EvaluateExpression( string as CFStringRef )
ExpressionRef expression = fn ExpressionWithFormat( string )
textlabel _resultlabel, fn StringWithFormat( @"= %@", fn ExpressionValueWithObject( expression, NULL, NULL ) )
end fn
void local fn DoDialog( ev as long, tag as long )
select ( ev )
case _btnClick : fn EvaluateExpression( textfield(tag) )
end select
end fn
fn BuildUI
on dialog fn DoDialog
HandleEvents
</syntaxhighlight>
[[file:Arithmetic expression FB.png]]
=={{header|Go}}==
Line 2,353 ⟶ 3,169:
=={{header|Groovy}}==
Solution:
<
ADD('+', 2),
SUBTRACT('-', 2),
Line 2,496 ⟶ 3,312:
}
return elements[0] instanceof List ? parse(elements[0]) : elements[0]
}</
Test:
<
def ex = parse(it)
print """
Line 2,534 ⟶ 3,350:
try { testParse('1++') } catch (e) { println e }
try { testParse('*1') } catch (e) { println e }
try { testParse('/ 1 /') } catch (e) { println e }</
{{out}}
Line 2,603 ⟶ 3,419:
=={{header|Haskell}}==
<
import Text.Parsec
Line 2,649 ⟶ 3,465:
main :: IO ()
main = print $ solution "(1+3)*7"</
{{Out}}
<pre>28</pre>
Line 2,665 ⟶ 3,481:
* Notice that the code looks remarkably like a typical grammar, rather than being an opaque cryptic solution
* Does not rely on any library to silently solve 1/2 the problem; in fact, this code would probably suit being put into a library almost verbatim
<
write("Usage: Input expression = Abstract Syntax Tree = Value, ^Z to end.")
repeat {
Line 2,765 ⟶ 3,581:
procedure exponent()
suspend tab(any('eE')) || =("+" | "-" | "") || digits() | ""
end</
{{out|Sample Output}}
Line 2,797 ⟶ 3,613:
The implementation here uses a shift/reduce parser to build a tree structure for evaluation (a tree structure which J happens to support for evaluation):
<
eval=:monad define
'gerund structure'=:y
Line 2,862 ⟶ 3,678:
coerase tmp
r
)</
example use:
<
2.2</
You can also display the syntax tree, for example:
<
┌─────────────────────────────────────────────────────┬───────────────────┐
│┌───┬───────┬───┬───────┬───┬─┬───────┬───┬───────┬─┐│┌───────┬─┬───────┐│
Line 2,877 ⟶ 3,693:
││ │└─────┘│ │└─────┘│ │ │└─────┘│ │└─────┘│ ││ │
│└───┴───────┴───┴───────┴───┴─┴───────┴───┴───────┴─┘│ │
└─────────────────────────────────────────────────────┴───────────────────┘</
At the top level, the first box is a list of terminals, and the second box represents their parsed structure within the source sentence, with numbers indexing the respective terminals. Within the list of terminals - each terminal is contained with a box
=={{header|Java}}==
Line 2,885 ⟶ 3,701:
Uses the [[Arithmetic/Rational/Java|BigRational class]] to handle arbitrary-precision numbers (rational numbers since basic arithmetic will result in rational values).
<
public class ArithmeticEvaluation {
Line 3,049 ⟶ 3,865:
}
}
}</
{{out}}
Line 3,064 ⟶ 3,880:
Spaces are removed, expressions like <code>5--1</code> are treated as <code>5 - -1</code>
<
s = s.replace(/\s/g,'').replace(/^\+/,'');
var rePara = /\([^\(\)]*\)/;
Line 3,118 ⟶ 3,934:
}
}
}</
Line 3,130 ⟶ 3,946:
=={{header|jq}}==
[[Category:PEG]]
This entry highlights the use of a [[:Category:PEG|PEG]] grammar expressed in jq.
=== PEG operations ===
<
def plus(E): E | (plus(E) // . );
def optional(E): E // .;
def amp(E): . as $in | E | $in;
def neg(E): select( [E] == [] );</
=== Helper functions ===
<
select(.remainder | startswith($s))
| .result += [$s]
Line 3,163 ⟶ 3,979:
def parseNumber($re):
consume($re)
| .result = .result + [.match|tonumber] ;</
=== PEG Grammar ===
The PEG grammar for arithmetic expressions follows the one given at the Raku entry.<
def ws: consume(" *");
Line 3,178 ⟶ 3,994:
Product | ws | star( (literal("+") // literal("-")) | Product);
Sum;</
=== Evaluation ===
<
def eval:
if type == "array" then
Line 3,202 ⟶ 4,018:
{remainder: String}
| Expr.result
| eval;</
=== Example ===
Line 3,212 ⟶ 4,028:
From Javascript entry.
<
function evalArithmeticExp(s) {
s = s.replace(/\s/g,'').replace(/^\+/,'');
Line 3,288 ⟶ 4,104:
evalArithmeticExp('2*-3--4+-0.25') ==> -2.25
=!EXPECTEND!=
*/</
{{out}}
Line 3,301 ⟶ 4,117:
=={{header|Julia}}==
Julia's homoiconic nature and strong metaprogramming facilities make AST/Expression parsing and creation as accessible and programmatic as other language features
<
"2 * (3 -1) + 2 * 5"
Line 3,341 ⟶ 4,157:
julia> eval(parse("2 * (3 + ((5) / (7 - 11)))"))
3.5</
=={{header|Kotlin}}==
{{trans|JavaScript}}
<
/* if string is empty, returns zero */
Line 3,430 ⟶ 4,246:
"1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1"
).forEach { println("$it = ${evalArithmeticExp(it)}") }
}</
{{out}}
Line 3,447 ⟶ 4,263:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
'[RC] Arithmetic evaluation.bas
'Buld the tree (with linked nodes, in array 'cause LB has no pointers)
Line 3,683 ⟶ 4,499:
addOpNode = newNode
end function
</syntaxhighlight>
{{out}}
Line 3,701 ⟶ 4,517:
=={{header|Lua}}==
<
P, R, C, S, V = lpeg.P, lpeg.R, lpeg.C, lpeg.S, lpeg.V
Line 3,740 ⟶ 4,556:
end
print(eval{expression:match(io.read())})</
=={{header|M2000 Interpreter}}==
Line 3,746 ⟶ 4,562:
All visible variables can be used, and all known functions, internal and user (if they are visible at that point). Global variables and functions are always visible.
<syntaxhighlight lang="m2000 interpreter">
y=100
Module CheckEval {
Line 3,759 ⟶ 4,575:
}
Call CheckEval
</syntaxhighlight>
New version of the task program. Based on BBC Basic. Exclude the final use of Eval() function (we use it for test only)
The Ast is a stack object which have strings and numbers. String are operators. This stack has all members in a RPN form. So it is easy to extract numbers and push them to reg (a stack also), and process the operators as they pop from the stack. There is no unary operator.
So the Ast isn't a tree here, it is a flat list.
<syntaxhighlight lang="m2000 interpreter">
Module CheckAst {
class EvalAst {
private:
Function Ast(&in$) {
object Ast=stack, op=stack
Do
stack Ast {stack .Ast1(&in$)}
in$=Trim$(in$)
oper$=left$(in$,1)
if Instr("+-", oper$)>0 else exit
if len(oper$)>0 then stack op {push oper$}
in$=Mid$(in$, 2)
stack Ast {stack op} // dump op to end of stack Ast
=Ast
}
Function Ast1(&in$) {
object Ast=stack, op=stack
Do
stack Ast {stack .Ast2(&in$)}
in$=Trim$(in$)
oper$=left$(in$,1)
if Instr("*/", oper$)>0 else exit
if len(oper$)>0 then stack op {push oper$}
in$=Mid$(in$, 2)
stack Ast {stack op}
=Ast
}
Function Ast2(&in$) {
}
Function GetNumber (&in$) {
Def ch$, num$
Do
ch$=left$(in$,1)
if instr("0123456789", ch$)>0 else exit
num$+=ch$
in$=Mid$(in$, 2)
until len(in$)=0
=stack:=val(num$)
}
public:
value () {
=.Ast(![])
}
}
Ast=EvalAst()
Expr$ = "1+2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10"
// Expr$="1/2+(4-3)/2+1/2"
print "Result through eval$:";eval(Expr$)
print "Expr :";Expr$
mres=Ast(&Expr$)
print "RPN :";array(stack(mres))#str$()
reg=stack
stack mres {
while not empty
if islet then
read op$
stack reg {
select case op$
case "+"
push number+number
case "-"
shift 2:push number-number
case "*"
push number*number
case "/"
shift 2:push number/number // shif 2 swap top 2 values
end select
}
else
read v
stack reg {push v}
end if
end while
}
if len(reg)<>1 then Error "Wrong Evaluation"
print "Result :";stackitem(reg)
}
CheckAst
</syntaxhighlight>
{{out}}
<pre>
Result through eval$:71
Expr : 1+2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10
RPN : 1 2 3 4 5 * 6 7 8 * * + 9 - + 10 / * +
Result :71
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
parse[string_] :=
Module[{e},
Line 3,853 ⟶ 4,712:
evaluate[{"*", a_, b_}] := evaluate[a]*evaluate[b];
evaluate[{"/", a_, b_}] := evaluate[a]/evaluate[b];
evaluate[string_String] := evaluate[parse[string]]</
Example use:
<
evaluate["-1+2(3+4*-5/6)"]</
{{out}}
Line 3,864 ⟶ 4,723:
=={{header|MiniScript}}==
<
Expr.eval = 0
Line 3,926 ⟶ 4,785:
print ast.eval
end while
</syntaxhighlight>
{{out}}
<pre>Enter expression: 200*42
Line 3,945 ⟶ 4,804:
This implementation uses a Pratt parser.
<
import os
Line 4,095 ⟶ 4,954:
# In the end, we print out the result.
echo ==ast</
=={{header|OCaml}}==
<
| Const of float
| Sum of expression * expression (* e1 + e2 *)
Line 4,137 ⟶ 4,996:
let parse_expression = parser [< e = parse_expr; _ = Stream.empty >] -> e
let read_expression s = parse_expression(lexer(Stream.of_string s))</
Using the function <code>read_expression</code> in an interactive loop:
<
while true do
print_string "Expression: ";
Line 4,149 ⟶ 5,008:
let res = eval expr in
Printf.printf " = %g\n%!" res;
done</
Compile with:
Line 4,155 ⟶ 5,014:
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
expressions = .array~of("2+3", "2+3/4", "2*3-4", "2*(3+4)+5/6", "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", "2*-3--4+-.25")
loop input over expressions
Line 4,391 ⟶ 5,250:
raise syntax 98.900 array("Invalid expression")
return expression
</syntaxhighlight>
{{out}}
<pre>
Line 4,408 ⟶ 5,267:
The <code>Do</code> procedure automatically threads the input state through a sequence of procedure calls.
<
fun {Expr X0 ?X}
Line 4,495 ⟶ 5,354:
{Inspector.configure widgetShowStrings true}
{Inspect AST}
{Inspect {Eval AST}}</
To improve performance, the number of choice points should be limited, for example by reading numbers deterministically instead.
Line 4,504 ⟶ 5,363:
=={{header|Perl}}==
<
# Evaluates an arithmetic expression like "(1+3)*7" and returns
# its value.
Line 4,564 ⟶ 5,423:
my ($op, @operands) = @$ast;
$_ = ev_ast($_) foreach @operands;
return $ops{$op}->(@operands);}}</
=={{header|Phix}}==
Line 4,571 ⟶ 5,430:
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.
<!--<
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Arithmetic_evaluation.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 4,791 ⟶ 5,650:
<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>
<!--</
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}}
Line 4,863 ⟶ 5,722:
result: 16406262
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">main =>
print("Enter an expression: "),
Str = read_line(),
Exp = parse_term(Str),
Res is Exp,
printf("Result = %w\n", Res).
</syntaxhighlight>
=={{header|PicoLisp}}==
Line 4,868 ⟶ 5,736:
(numbers and transient symbols). From that, a recursive descendent parser can
build an expression tree, resulting in directly executable Lisp code.
<
(let *L (str Str "")
(aggregate) ) )
Line 4,890 ⟶ 5,758:
((= "+" X) (term))
((= "-" X) (list '- (term)))
((= "(" X) (prog1 (aggregate) (pop '*L)))) ) )</
{{out}}
<
-> (+ (+ 1 2) (/ (* 3 (- 4)) (+ 1 2)))
: (ast "(1+2+3)*-4/(1+2)")
-> (/ (* (+ (+ 1 2) 3) (- 4)) (+ 1 2))</
=={{header|Pop11}}==
<
/* Uncomment the following to parse data from standard input
Line 5,048 ⟶ 5,916:
;;; Test it
arith_eval(do_expr()) =></
=={{header|Prolog}}==
{{works with|SWI Prolog 8.1.19}}
<
numeric(X) :- 48 =< X, X =< 57.
not_numeric(X) :- 48 > X ; X > 57.
Line 5,102 ⟶ 5,970:
% Example use
% calculator("(3+50)*7-9", X).</
=={{header|Python}}==
Line 5,108 ⟶ 5,976:
<br>A subsequent example uses Pythons' ast module to generate the abstract syntax tree.
<
class AstNode(object):
Line 5,223 ⟶ 6,091:
expr = raw_input("Expression:")
astTree = Lex( expr, Yaccer())
print expr, '=',astTree.eval()</
===ast standard library module===
Python comes with its own [http://docs.python.org/3.1/library/ast.html#module-ast ast] module as part of its standard libraries. The module compiles Python source into an AST tree that can in turn be compiled to bytecode then executed.
<
>>>
>>> expr="2 * (3 -1) + 2 * 5"
Line 5,250 ⟶ 6,118:
>>> code_object = compile(node, filename='<string>', mode='eval')
>>> eval(code_object)
16</
=={{header|Racket}}==
<
(require parser-tools/yacc
Line 5,289 ⟶ 6,157:
(displayln (parse (λ () (lex i)))))
(calc "(1 + 2 * 3) - (1+2)*-3")</
=={{header|Raku}}==
Line 5,295 ⟶ 6,163:
{{Works with|rakudo|2018.03}}
<syntaxhighlight lang="raku"
grammar expr {
Line 5,338 ⟶ 6,206:
say ev '1 + 2 - 3 * 4 / 5'; # 0.6
say ev '1 + 5*3.4 - .5 -4 / -2 * (3+4) -6'; # 25.5
say ev '((11+15)*15)* 2 + (3) * -4 *1'; # 768</
=={{header|REXX}}==
Line 5,355 ⟶ 6,223:
:::* 12.3D+44 ("double" precision)
:::* 12.3Q+44 ("extended" or "quad" precision)
<
nchars = '0123456789.eEdDqQ' /*possible parts of a number, sans ± */
e='***error***'; $=" "; doubleOps= '&|*/'; z= /*handy─dandy variables.*/
Line 5,470 ⟶ 6,338:
return substr(x, Nj, 1) /* [↑] ignore any blanks in expression*/
end /*Nj*/
return $ /*reached end-of-tokens, return $. */</
To view a version of the above REXX program, see this version which has much more whitespace: ──► [[Arithmetic_evaluation/REXX]]. <br>
<br>
Line 5,477 ⟶ 6,345:
<pre>
answer──► 1
</pre>
=={{header|RPL}}==
This expression evaluator generates the AST through an RPN converter based on the shunting-yard algorithm.
<code>LEXER</code> is defined at [[Parsing/Shunting-yard algorithm#RPL|Parsing/Shunting-yard algorithm]]
{{works with|HP|48}}
≪ '''IF''' OVER '''THEN'''
"^*/+-" DUP 5 PICK POS SWAP ROT POS
{ 4 3 3 2 2 } { 1 0 0 0 0 }
→ o2 o1 prec rasso
≪ '''IF''' o2 '''THEN'''
prec o1 GET prec o2 GET
'''IF''' rasso o1 GET '''THEN''' < '''ELSE''' ≤ '''END'''
'''ELSE''' 0 '''END'''
≫
'''ELSE''' DROP 0 '''END'''
≫ ‘<span style="color:blue>POPOP?</span>’ STO
<span style="color:grey>@ ''( op → Boolean )''</span>
≪ { } "" → infix postfix token
≪ 0
1 infix SIZE '''FOR''' j
infix j GET 'token' STO
1 SF
'''CASE'''
"^*/+-" token →STR POS '''THEN'''
1 CF
'''WHILE''' token <span style="color:blue>POPOP?</span> '''REPEAT'''
'postfix' ROT STO+ 1 - '''END'''
token SWAP 1 + '''END'''
"(" token == '''THEN'''
token SWAP 1 + '''END'''
")" token == '''THEN'''
'''WHILE''' DUP 1 FS? AND '''REPEAT'''
'''IF''' OVER "(" ≠ '''THEN'''
'postfix' ROT STO+
'''ELSE''' SWAP DROP 1 CF '''END'''
1 -
'''END'''
'''END'''
1 FS? '''THEN''' 'postfix' token STO+ '''END'''
'''END'''
'''NEXT'''
'''WHILE''' DUP '''REPEAT'''
'postfix' ROT STO+ 1 - '''END'''
DROP
≫ ≫ ‘<span style="color:blue>→RPN</span>’ STO
<span style="color:grey>@ ''( { infixed tokens } → { postfixed tokens )''</span>
≪ DUP SIZE → len
≪ '''IF''' len '''THEN'''
DUP len GET SWAP
'''IF''' len 1 ≠ '''THEN''' 1 len 1 - SUB '''ELSE''' DROP { } '''END'''
'''IF''' OVER TYPE '''THEN'''
<span style="color:blue>→AST</span> <span style="color:blue>→AST</span>
4 ROLLD ROT ROT 3 →LIST SWAP
'''END'''
'''ELSE''' "Err" SWAP '''END'''
≫ ≫ ‘<span style="color:blue>→AST</span>’ STO
<span style="color:grey>@ ''( { postfixed tokens } → { AST } )''</span>
≪ DUP 1 GET
'''IF''' DUP TYPE '''THEN''' <span style="color:blue>AST→N</span> '''END'''
OVER 3 GET
'''IF''' DUP TYPE '''THEN''' <span style="color:blue>AST→N</span> '''END'''
ROT 2 GET "≪" SWAP + "≫" + STR→ EVAL
≫ ‘<span style="color:blue>AST→N</span>' STO
<span style="color:grey>@ ''( { AST } → value )''</span>
≪ <span style="color:blue>LEXER</span> <span style="color:blue>→RPN</span>
<span style="color:blue>→AST</span> DROP DUP <span style="color:grey>@ DUP is just here to leave the AST in the stack</span>
<span style="color:blue>AST→N</span>
≫ ‘<span style="color:blue>AEVAL</span>’ STO
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" <span style="color:blue>AEVAL</span>
{{out}}
<pre>
2: { 3 "+" { { 4 "*" 2 } "/" { { 1 "-" 5 } "^" { 2 "^" 3 } } } }
1: 3.00012207031
</pre>
=={{header|Ruby}}==
Function to convert infix arithmetic expression to binary tree. The resulting tree knows how to print and evaluate itself. Assumes expression is well-formed (matched parens, all operators have 2 operands). Algorithm: http://www.seas.gwu.edu/~csci131/fall96/exp_to_tree.html
<
class TreeNode
Line 5,580 ⟶ 6,528:
node_stack.last
end</
Testing:
<
puts("Original: " + exp)
Line 5,589 ⟶ 6,537:
puts("Infix: " + tree.to_s(:infix))
puts("Postfix: " + tree.to_s(:postfix))
puts("Result: " + tree.eval.to_s)</
{{out}}
<pre>Original: 1 + 2 - 3 * (4 / 6)
Line 5,598 ⟶ 6,546:
=={{header|Rust}}==
<
Line 5,771 ⟶ 6,719:
}
</syntaxhighlight>
=={{header|Scala}}==
Line 5,777 ⟶ 6,725:
is practically non-existent, to avoid obscuring the code.
<
package org.rosetta.arithmetic_evaluator.scala
Line 5,824 ⟶ 6,772:
}
}
</syntaxhighlight>
Example:
Line 5,853 ⟶ 6,801:
The parse function uses a recursive-descent parser to follow the precedence rules.
<
(import (scheme base)
(scheme char)
Line 5,949 ⟶ 6,897:
(newline))
'("1 + 2" "20+4*5" "1/2+5*(6-3)" "(1+3)/4-1" "(1 - 5) * 2 / (20 + 1)"))
</syntaxhighlight>
{{out}}
Line 5,963 ⟶ 6,911:
=={{header|Sidef}}==
{{trans|JavaScript}}
<
func evalExp(s) {
Line 6,018 ⟶ 6,966:
return Number(evalExp(s))
}</
Testing the function:
<
['2+3' => 5],
['-4-3' => -7],
Line 6,033 ⟶ 6,981:
assert_eq(num, res)
"%-45s == %10g\n".printf(expr, num)
}</
=={{header|Standard ML}}==
This implementation uses a [https://en.wikipedia.org/wiki/Recursive_descent_parser recursive descent parser]. It first lexes the input. The parser builds a Abstract Syntax Tree (AST) and the evaluator evaluates it. The parser uses sub categories.
The parsing is a little bit tricky because the grammar is left recursive.
<
datatype expression =
Con of int (* constant *)
Line 6,106 ⟶ 7,054:
case parseE (lex (explode str)) of
(exp, nil) => eval exp
| _ => raise Error "not parseable stuff at the end"</
=={{header|Tailspin}}==
<
def ops: ['+','-','*','/'];
data binaryExpression <{left: <node>, op: <?($ops <[<=$::raw>]>)>, right: <node>}>
data node <binaryExpression|"1">
Line 6,119 ⟶ 7,067:
rule addition: {left:<addition|multiplication|term> (<WS>?) op:<'[+-]'> (<WS>?) right:<multiplication|term>}
rule multiplication: {left:<multiplication|term> (<WS>?) op:<'[*/]'> (<WS>?) right:<term>}
rule term: <INT"1"|parentheses>
rule parentheses: (<'\('> <WS>?) <addition|multiplication|term> (<WS>? <'\)'>)
end parseArithmetic
templates evaluateArithmetic
<´node´ {op: <='+'>}> ($.left -> evaluateArithmetic) + ($.right -> evaluateArithmetic) !
<´node´ {op: <='-'>}> ($.left -> evaluateArithmetic) - ($.right -> evaluateArithmetic) !
<´node´ {op: <='*'>}> ($.left -> evaluateArithmetic) * ($.right -> evaluateArithmetic) !
<´node´ {op: <='/'>}> ($.left -> evaluateArithmetic) ~/ ($.right -> evaluateArithmetic) !
otherwise $ !
end evaluateArithmetic
def ast: '(100 - 5 * (2+3*4) + 2) / 2' -> parseArithmetic;
'$ast;
' -> !OUT::write
'$ast -> evaluateArithmetic;
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
{left={left={left=100"1", op=-, right={left=5"1", op=*, right={left=2"1", op=+, right={left=3"1", op=*, right=4"1"}}}}, op=+, right=2"1"}, op=/, right=2"1"}
16"1"
</pre>
If we don't need to get the AST, we could just evaluate right away:
<
composer calculator
(<WS>?) <addition|multiplication|term> (<WS>?)
Line 6,164 ⟶ 7,110:
'
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>16</pre>
Line 6,173 ⟶ 7,119:
in a form that it can be immediately eval-led,
using Tcl's prefix operators.
<
proc ast str {
Line 6,216 ⟶ 7,162:
} \n] {
puts "$test ..... [eval $test] ..... [eval [eval $test]]"
}</
{{out}}
<pre>
Line 6,232 ⟶ 7,178:
Use TXR text pattern matching to parse expression to a Lisp AST, then evaluate with <code>eval</code>:
<
@(define space)@/ */@(end)
@(define mulop (nod))@\
Line 6,284 ⟶ 7,230:
erroneous suffix "@bad"
@ (end)
@(end)</
Run:
Line 6,294 ⟶ 7,240:
=={{header|Ursala}}==
with no error checking other than removal of spaces
<
#import nat
#import flo
Line 6,315 ⟶ 7,260:
traverse = *^ ~&v?\%ep ^H\~&vhthPX '+-*/'-$<plus,minus,times,div>@dh
evaluate = traverse+ parse+ lex</
test program:
<
test = evaluate*t
Line 6,334 ⟶ 7,279:
5-3*2
(1+1)*(2+3)
(2-4)/(3+5*(8-1))]-</
{{out}}
<pre>
Line 6,354 ⟶ 7,299:
{{trans|Kotlin}}
{{libheader|Wren-pattern}}
<
/* if string is empty, returns zero */
Line 6,443 ⟶ 7,388:
"1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10",
"1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1"
].each { |s| System.print("%(s) = %(evalArithmeticExp.call(s))") }</
{{out}}
Line 6,458 ⟶ 7,403:
1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1 = 60
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">def \Node\ Left, Data, Right;
def IntSize = 4;
int Stack(16);
int SP; \stack pointer
proc Push(N);
int N;
[Stack(SP):= N; SP:= SP+1];
func Pop;
[SP:= SP-1; return Stack(SP)];
func Precedence(Op);
int Op;
case Op of
^+, ^-: return 2;
^*, ^/: return 3;
^^: return 4
other [];
proc PostOrder(Node); \Traverse tree at Node in postorder, and
int Node, Top; \ return its evaluation on the stack
[if Node # 0 then
[PostOrder(Node(Left));
PostOrder(Node(Right));
case Node(Data) of
^+: [Top:= Pop; Push(Pop+Top)];
^-: [Top:= Pop; Push(Pop-Top)];
^*: [Top:= Pop; Push(Pop*Top)];
^/: [Top:= Pop; Push(Pop/Top)]
other Push(Node(Data) - ^0); \convert ASCII to binary
];
];
char Str;
int Token, Op1, Op2, Node;
[Str:= "3 + 4 * 2 / ( 1 - 5 ) "; \RPN: 342*15-/+
Text(0, Str);
\Convert infix expression to RPN (postfix) using shunting-yard algorithm
SP:= 0;
OpenO(8); \discard (overwrite) arguments in RPi's command line
loop [repeat Token:= Str(0); Str:= Str+1;
until Token # ^ ; \strip out space characters
case Token of
^+, ^-, ^*, ^/, ^^:
[Op1:= Token;
loop [if SP <= 0 then quit; \stack is empty
Op2:= Stack(SP-1);
if Op2 = ^( then quit;
if Precedence(Op2) < Precedence(Op1) then quit;
if Precedence(Op2) = Precedence(Op1) then
if Op1 = ^^ then quit;
ChOut(8, Pop);
];
Push(Op1);
];
^(: Push(Token);
^): [while SP > 0 and Stack(SP-1) # ^( do
ChOut(8, Pop);
Pop; \discard left parenthesis
];
$A0: quit \terminating space with its MSB set
other ChOut(8, Token); \output the single-digit number
];
while SP > 0 do ChOut(8, Pop); \output any remaining operators
\Build AST from RPN expression
OpenI(8); \(for safety)
loop [Token:= ChIn(8);
if Token = $1A\EOF\ then quit
else if Token >= ^0 and Token <= ^9 then
[Node:= Reserve(3*IntSize);
Node(Data):= Token;
Node(Left):= 0;
Node(Right):= 0;
Push(Node);
]
else \must be an operator
[Node:= Reserve(3*IntSize);
Node(Data):= Token;
Node(Right):= Pop;
Node(Left):= Pop;
Push(Node);
];
];
\Evaluate expression in AST
PostOrder(Pop);
Text(0, "= ");
IntOut(0, Pop);
]</syntaxhighlight>
{{out}}
<pre>
t.txt"a</pre>
=={{header|zkl}}==
In zkl, the compiler stack is part of the language and is written in zkl so ...
<
Compiler.Parser.parseText("1+3*7").dump();</
The ASTs look like
{{out}}
Line 6,484 ⟶ 7,523:
</pre>
Evaluating them is just moving up the stack:
<
Compiler.Compiler.compileText("1+3*7").__constructor(); vm.regX;</
{{out}}
<pre>
Line 6,493 ⟶ 7,532:
=={{header|ZX Spectrum Basic}}==
<
20 LET s$="": REM last symbol
30 LET pc=0: REM parenthesis counter
Line 6,524 ⟶ 7,563:
300 PRINT FLASH 1;"Invalid symbol ";c$;" detected in pos ";n: BEEP 1,-25
310 STOP
</syntaxhighlight>
{{omit from|gnuplot}}
| |||