Arithmetic evaluation: Difference between revisions
→{{header|C++}}
(→{{header|jq}}: Category:PEG) |
|||
| (18 intermediate revisions by 12 users not shown) | |||
Line 299:
<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>
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)}}
Line 1,311 ⟶ 1,892:
? arithEvaluate("(1 + 2 / 2) * (5 + 5)")
# value: 20.0</syntaxhighlight>
=={{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
<syntaxhighlight lang="elena">import system'routines;
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()
{
}</syntaxhighlight>
=={{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}}==
Line 2,348 ⟶ 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 3,763 ⟶ 4,577:
</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}}==
Line 5,488 ⟶ 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>
Line 6,135 ⟶ 7,072:
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
Line 6,362 ⟶ 7,299:
{{trans|Kotlin}}
{{libheader|Wren-pattern}}
<syntaxhighlight lang="
/* if string is empty, returns zero */
Line 6,466 ⟶ 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}}==
| |||