math - operan - Code Golf: evaluador de expresiones matemáticas(que respeta PEMDAS)
orden de expresiones algebraicas ejemplos (18)
Te desafío a escribir un evaluador de expresiones matemáticas que respete PEMDAS (orden de las operaciones: paréntesis, exponenciación, multiplicación, división, suma, resta) sin usar expresiones regulares, una función preexistente de tipo "Eval ()", una biblioteca de análisis , etc.
Vi un desafío de evaluador preexistente en SO ( here ), pero que específicamente requería una evaluación de izquierda a derecha.
Muestra de entradas y salidas:
"-1^(-3*4/-6)" -> "1"
"-2^(2^(4-1))" -> "256"
"2*6/4^2*4/3" -> "1"
Escribí un evaluador en C #, pero me gustaría ver lo mal que se compara con los de los programadores más inteligentes en sus idiomas de elección.
Relacionado:
Aclaraciones:
Hagamos de esto una función que acepte un argumento de cadena y devuelva un resultado de cadena.
En cuanto a por qué no regexes, bueno, eso es para nivelar el campo de juego. Creo que debería haber un desafío por separado para "la expresión regular más compacta".
Usar StrToFloat () es aceptable. Al "analizar la biblioteca" quise excluir elementos como los analizadores gramaticales de propósito general, también para nivelar el campo de juego.
Flotadores de soporte.
Soporta paretheses, exponenciación y los cuatro operadores aritméticos.
Proporcione la multiplicación y la división con la misma precedencia.
Dar suma y resta igual precedencia.
Para simplificar, puede suponer que todas las entradas están bien formadas.
No tengo preferencia sobre si su función acepta cosas tales como ".1" o "1e3" como números válidos, pero si los acepta ganaría puntos de brownie. ;)
Para casos divididos por cero, quizás podría devolver "NaN" (suponiendo que desea implementar el manejo de errores).
C # (con mucho LINQ), 150 líneas
Ok, implemento una biblioteca de combinador de analizador monádico, y luego uso esa biblioteca para resolver este problema. En total, se trata de 150 líneas de código. (Esto es básicamente una transliteración directa de mi solución de F #).
Supongo que la exponenciación se asocia a la derecha, y los otros operadores se asocian a la izquierda. Todo funciona en System.Doubles. No hice ningún manejo de errores para entradas malas o dividir por cero.
using System;
using System.Collections.Generic;
using System.Linq;
class Option<T>
{
public T Value { get; set; }
public Option(T x) { Value = x; }
}
delegate Option<KeyValuePair<T,List<char>>> P<T>(List<char> input);
static class Program
{
static List<T> Cons<T>(T x, List<T> xs)
{
var r = new List<T>(xs);
r.Insert(0, x);
return r;
}
static Option<T> Some<T>(T x) { return new Option<T>(x); }
static KeyValuePair<T,List<char>> KVP<T>(T x, List<char> y)
{ return new KeyValuePair<T,List<char>>(x,y); }
// Core Parser Library
static P<T> Fail<T>() { return i => null; }
static P<U> Select<T, U>(this P<T> p, Func<T, U> f)
{
return i =>
{
var r = p(i);
if (r == null) return null;
return Some(KVP(f(r.Value.Key),(r.Value.Value)));
};
}
public static P<V> SelectMany<T, U, V>(this P<T> p, Func<T, P<U>> sel, Func<T, U, V> prj)
{
return i =>
{
var r = p(i);
if (r == null) return null;
var p2 = sel(r.Value.Key);
var r2 = p2(r.Value.Value);
if (r2 == null) return null;
return Some(KVP(prj(r.Value.Key, r2.Value.Key),(r2.Value.Value)));
};
}
static P<T> Or<T>(this P<T> p1, P<T> p2)
{
return i =>
{
var r = p1(i);
if (r == null) return p2(i);
return r;
};
}
static P<char> Sat(Func<char,bool> pred)
{
return i =>
{
if (i.Count == 0 || !pred(i[0])) return null;
var rest = new List<char>(i);
rest.RemoveAt(0);
return Some(KVP(i[0], rest));
};
}
static P<T> Return<T>(T x)
{
return i => Some(KVP(x,i));
}
// Auxiliary Parser Library
static P<char> Digit = Sat(Char.IsDigit);
static P<T> Lit<T>(char c, T r)
{
return from dummy in Sat(x => x == c)
select r;
}
static P<List<T>> Opt<T>(P<List<T>> p)
{
return p.Or(Return(new List<T>()));
}
static P<List<T>> Many<T>(P<T> p)
{
return Many1<T>(p).Or(Return(new List<T>()));
}
static P<List<T>> Many1<T>(P<T> p)
{
return from x in p
from xs in Many(p)
select Cons(x, xs);
}
static P<T> Chainl1<T>(this P<T> p, P<Func<T, T, T>> op)
{
return from x in p
from r in Chainl1Helper(x, p, op)
select r;
}
static P<T> Chainl1Helper<T>(T x, P<T> p, P<Func<T, T, T>> op)
{
return (from f in op
from y in p
from r in Chainl1Helper(f(x, y), p, op)
select r)
.Or(Return(x));
}
static P<T> Chainr1<T>(this P<T> p, P<Func<T, T, T>> op)
{
return (from x in p
from r in (from f in op
from y in Chainr1(p, op)
select f(x, y))
.Or(Return(x))
select r);
}
static P<double> TryParse(string s)
{
double d;
if (Double.TryParse(s, out d)) return Return(d);
return Fail<double>();
}
static void Main(string[] args)
{
var Num = from sign in Opt(Lit(''-'', new List<char>(new []{''-''})))
from beforeDec in Many(Digit)
from rest in Opt(from dec in Lit(''.'',''.'')
from afterDec in Many(Digit)
select Cons(dec, afterDec))
let s = new string(Enumerable.Concat(sign,
Enumerable.Concat(beforeDec, rest))
.ToArray())
from r in TryParse(s)
select r;
// Expression grammar of this code-golf question
var AddOp = Lit(''+'', new Func<double,double,double>((x,y) => x + y))
.Or(Lit(''-'', new Func<double, double, double>((x, y) => x - y)));
var MulOp = Lit(''*'', new Func<double, double, double>((x, y) => x * y))
.Or(Lit(''/'', new Func<double, double, double>((x, y) => x / y)));
var ExpOp = Lit(''^'', new Func<double, double, double>((x, y) => Math.Pow(x, y)));
P<double> Expr = null;
P<double> Term = null;
P<double> Factor = null;
P<double> Part = null;
P<double> Paren = from _1 in Lit(''('', 0)
from e in Expr
from _2 in Lit('')'', 0)
select e;
Part = Num.Or(Paren);
Factor = Chainr1(Part, ExpOp);
Term = Chainl1(Factor, MulOp);
Expr = Chainl1(Term, AddOp);
Func<string,string> CodeGolf = s =>
Expr(new List<char>(s)).Value.Key.ToString();
// Examples
Console.WriteLine(CodeGolf("1.1+2.2+10^2^3")); // 100000003.3
Console.WriteLine(CodeGolf("10+3.14/2")); // 11.57
Console.WriteLine(CodeGolf("(10+3.14)/2")); // 6.57
Console.WriteLine(CodeGolf("-1^(-3*4/-6)")); // 1
Console.WriteLine(CodeGolf("-2^(2^(4-1))")); // 256
Console.WriteLine(CodeGolf("2*6/4^2*4/3")); // 1
}
}
F #, 589 caracteres
He comprimido golf mi solución anterior en esta gema:
let rec D a=function|c::s when System.Char.IsDigit c->D(c::a)s|s->a,s
and L p o s=
let rec K(a,s)=match o s with|None->a,s|Some(o,t)->let q,t=p t in K(o a q,t)
K(p s)
and E=L(L F (function|''*''::s->Some((*),s)|''/''::s->Some((/),s)|_->None))(
function|''+''::s->Some((+),s)|''-''::s->Some((-),s)|_->None)
and F s=match P s with|x,''^''::s->let y,s=F s in x**y,s|r->r
and P=function|''(''::s->let r,_::s=E s in r,s|s->(
let a,s=match(match s with|''-''::t->D[''-'']t|_->D[]s)with|a,''.''::t->D(''.''::a)t|r->r
float(new string(Seq.to_array(List.rev a))),s)
and G s=string(fst(E(Seq.to_list s)))
Pruebas:
printfn "%s" (G "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (G "10+3.14/2") // 11.57
printfn "%s" (G "(10+3.14)/2") // 6.57
printfn "%s" (G "-1^(-3*4/-6)") // 1
printfn "%s" (G "-2^(2^(4-1))") // 256
printfn "%s" (G "2*6/4^2*4/3") // 1
printfn "%s" (G "3-2-1") // 0
F #, 70 líneas
Ok, implemento una biblioteca de combinador de analizador monádico, y luego uso esa biblioteca para resolver este problema. En total, sigue siendo solo 70 líneas de código legible.
Supongo que la exponenciación se asocia a la derecha, y los otros operadores se asocian a la izquierda. Todo funciona en flotadores (System.Doubles). No hice ningún manejo de errores para entradas malas o dividir por cero.
// Core Parser Library
open System
let Fail() = fun i -> None
type ParseMonad() =
member p.Return x = fun i -> Some(x,i)
member p.Bind(m,f) = fun i ->
match m i with
| Some(x,i2) -> f x i2
| None -> None
let parse = ParseMonad()
let (<|>) p1 p2 = fun i ->
match p1 i with
| Some r -> Some(r)
| None -> p2 i
let Sat pred = fun i ->
match i with
| [] -> None
| c::cs -> if pred c then Some(c, cs) else None
// Auxiliary Parser Library
let Digit = Sat Char.IsDigit
let Lit (c : char) r =
parse { let! _ = Sat ((=) c)
return r }
let Opt p = p <|> parse { return [] }
let rec Many p = Opt (Many1 p)
and Many1 p = parse { let! x = p
let! xs = Many p
return x :: xs }
let Num = parse {
let! sign = Opt(Lit ''-'' [''-''])
let! beforeDec = Many Digit
let! rest = parse { let! dec = Lit ''.'' ''.''
let! afterDec = Many Digit
return dec :: afterDec } |> Opt
let s = new string(List.concat([sign;beforeDec;rest])
|> List.to_array)
match(try Some(float s) with e -> None)with
| Some(r) -> return r
| None -> return! Fail() }
let Chainl1 p op =
let rec Help x = parse { let! f = op
let! y = p
return! Help (f x y) }
<|> parse { return x }
parse { let! x = p
return! Help x }
let rec Chainr1 p op =
parse { let! x = p
return! parse { let! f = op
let! y = Chainr1 p op
return f x y }
<|> parse { return x } }
// Expression grammar of this code-golf question
let AddOp = Lit ''+'' (fun x y -> 0. + x + y)
<|> Lit ''-'' (fun x y -> 0. + x - y)
let MulOp = Lit ''*'' (fun x y -> 0. + x * y)
<|> Lit ''/'' (fun x y -> 0. + x / y)
let ExpOp = Lit ''^'' (fun x y -> Math.Pow(x,y))
let rec Expr = Chainl1 Term AddOp
and Term = Chainl1 Factor MulOp
and Factor = Chainr1 Part ExpOp
and Part = Num <|> Paren
and Paren = parse { do! Lit ''('' ()
let! e = Expr
do! Lit '')'' ()
return e }
let CodeGolf (s:string) =
match Expr(Seq.to_list(s.ToCharArray())) with
| None -> "bad input"
| Some(r,_) -> r.ToString()
// Examples
printfn "%s" (CodeGolf "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (CodeGolf "10+3.14/2") // 11.57
printfn "%s" (CodeGolf "(10+3.14)/2") // 6.57
printfn "%s" (CodeGolf "-1^(-3*4/-6)") // 1
printfn "%s" (CodeGolf "-2^(2^(4-1))") // 256
printfn "%s" (CodeGolf "2*6/4^2*4/3") // 1
El tipo de representación del analizador es
type P<''a> = char list -> option<''a * char list>
por cierto, uno común para los analizadores que no manejan errores.
J
:[[/%^(:[[+-/^,&i|:[$['' '']^j+0__:k<3:]]
C, 609 characters
(625 including formatted as below to avoid horizontal scrolling, 42 lines if I make it readable.)
double x(char*e,int*p);
D(char c){return c>=48&&c<=57;}
S(char c){return c==43||c==45;}
double h(char*e,int*p){double r=0,s=1,f=0,m=1;int P=*p;if(e[P]==40){
P++;r=x(e,&P);P++;}else if(D(e[P])||S(e[P])){s=S(e[P])?44-e[P++]:s;
while(D(e[P]))r=r*10+e[P++]-48;if(e[P]==46)while(D(e[++P])){f=f*10+e[P]-48;
m*=10;}r=s*(r+f/m);}*p=P;return r;}
double x(char*e,int*p){double r=0,t,d,x,s=1;do{char o=42;t=1;do{d=h(e,p);
while(e[*p]==94){(*p)++;x=h(e,p);d=pow(d,x);}t=o==42?t*d:t/d;o=e[*p];
if(o==42||o==47)(*p)++;else o=0;}while(o);r+=s*t;s=S(e[*p])?44-e[(*p)++]:0;
}while(s);return r;}
double X(char*e){int p=0;return x(e,&p);}
It''s my first code golf.
I''m parsing floats myself and the only library function I use is pow .
I corrected errors with multiple elevations to a power and handling of parentheses. I also made the main function X() that takes just a string as argument. It still returns a double, though.
Expanded
42 non-blank lines
double x(char*e, int*p);
D(char c) { return c>=48 && c<=57; }
S(char c) { return c==43 || c==45; }
double h(char*e, int*p) {
double r=0, s=1, f=0, m=1;
int P=*p;
if(e[P]==40) {
P++;
r=x(e, &P);
P++; }
else if(D(e[P]) || S(e[P])) {
s=S(e[P]) ? 44-e[P++] : s;
while(D(e[P]))
r=r*10+e[P++]-48;
if(e[P]==46)
while(D(e[++P])) {
f=f*10+e[P]-48;
m*=10; }
r=s*(r+f/m); }
*p=P;
return r; }
double x(char*e, int*p) {
double r=0, t, d, x, s=1;
do {
char o=42;
t=1;
do {
d=h(e, p);
while(e[*p]==94) {
(*p)++;
x=h(e, p);
d=pow(d, x); }
t=o==42 ? t*d : t/d;
o=e[*p];
if(o==42 || o==47) (*p)++;
else o=0;
} while(o);
r+=s*t;
s=S(e[*p]) ? 44-e[(*p)++] : 0;
} while(s);
return r; }
double X(char*e) {int p=0; return x(e, &p);}
F#, 52 lines
This one mostly eschews generality, and just focuses on writing a recursive descent parser to solve this exact problem.
open System
let rec Digits acc = function
| c::cs when Char.IsDigit(c) -> Digits (c::acc) cs
| rest -> acc,rest
let Num = function
| cs ->
let acc,cs = match cs with|''-''::t->[''-''],t |_->[],cs
let acc,cs = Digits acc cs
let acc,cs = match cs with
| ''.''::t -> Digits (''.''::acc) t
| _ -> acc, cs
let s = new string(List.rev acc |> List.to_array)
float s, cs
let Chainl p op cs =
let mutable r, cs = p cs
let mutable finished = false
while not finished do
match op cs with
| None -> finished <- true
| Some(op, cs2) ->
let r2, cs2 = p cs2
r <- op r r2
cs <- cs2
r, cs
let rec Chainr p op cs =
let x, cs = p cs
match op cs with
| None -> x, cs
| Some(f, cs) -> // TODO not tail-recursive
let y, cs = Chainr p op cs
f x y, cs
let AddOp = function
| ''+''::cs -> Some((fun x y -> 0. + x + y), cs)
| ''-''::cs -> Some((fun x y -> 0. + x - y), cs)
| _ -> None
let MulOp = function
| ''*''::cs -> Some((fun x y -> 0. + x * y), cs)
| ''/''::cs -> Some((fun x y -> 0. + x / y), cs)
| _ -> None
let ExpOp = function
| ''^''::cs -> Some((fun x y -> Math.Pow(x,y)), cs)
| _ -> None
let rec Expr = Chainl Term AddOp
and Term = Chainl Factor MulOp
and Factor = Chainr Part ExpOp
and Part = function
| ''(''::cs -> let r, cs = Expr cs
if List.hd cs <> '')'' then failwith "boom"
r, List.tl cs
| cs -> Num cs
let CodeGolf (s:string) =
Seq.to_list s |> Expr |> fst |> string
// Examples
printfn "%s" (CodeGolf "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (CodeGolf "10+3.14/2") // 11.57
printfn "%s" (CodeGolf "(10+3.14)/2") // 6.57
printfn "%s" (CodeGolf "-1^(-3*4/-6)") // 1
printfn "%s" (CodeGolf "-2^(2^(4-1))") // 256
printfn "%s" (CodeGolf "2*6/4^2*4/3") // 1
printfn "%s" (CodeGolf "3-2-1") // 0
C (277 caracteres)
#define V(c)D o;for(**s-40?*r=strtod(*s,s):(++*s,M(s,r)),o=**s?strchr(t,*(*s)++)-t:0;c;)L(r,&o,s);
typedef char*S;typedef double D;D strtod(),pow();S*t=")+-*/^",strchr();
L(D*v,D*p,S*s){D u,*r=&u;V(*p<o)*v=*p-1?*p-2?*p-3?*p-4?pow(*v,u):*v/u:
*v*u:*v-u:*v+u;*p=o;}M(S*s,D*r){V(o)}
La primera nueva línea es obligatoria y la he contado como un personaje.
Este es un enfoque completamente diferente de mi otra respuesta . Es más un enfoque funcional. En lugar de realizar token y bucles varias veces, este evalúa la expresión en una pasada, utilizando llamadas recursivas para operadores de mayor precedencia, utilizando efectivamente la pila de llamadas para almacenar el estado.
Para satisfacer a Straight ;) , esta vez he incluido declaraciones de strtod() , pow() y strchr() . Sacarlos ahorraría 26 caracteres.
El punto de entrada es M() . La cadena de entrada es el primer parámetro, y el doble de salida es el segundo parámetro. El punto de entrada solía ser E() , que devolvió una cadena, como pidió OP. Pero como la mía era la única implementación de C que lo hacía, decidí eliminarla (presión de grupo, y todo). Agregarlo de nuevo agregaría 43 caracteres:
E(S s,S r){D v;M(&s,&v);sprintf(r,"%g",v);}
A continuación está el código antes de que lo comprimí:
double strtod(),pow(),Solve();
int OpOrder(char op){
int i=-1;
while("/0)+-*/^"[++i] != op);
return i/2;
}
double GetValue(char **s){
if(**s == ''(''){
++*s;
return Solve(s);
}
return strtod(*s, s);
}
double Calculate(double left, char *op, char **s){
double right;
char rightOp;
if(*op == 0 || *op == '')'')
return left;
right = GetValue(s);
rightOp = *(*s)++;
while(OpOrder(*op) < OpOrder(rightOp))
right = Calculate(right, &rightOp, s);
switch(*op){
case ''+'': left += right; break;
case ''-'': left -= right; break;
case ''*'': left *= right; break;
case ''/'': left /= right; break;
case ''^'': left = pow(left, right); break;
}
*op = rightOp;
return left;
}
double Solve(char **s){
double value = GetValue(s);
char op = *(*s)++;
while(op != 0 && op != '')'')
value = Calculate(value, &op, s);
return value;
}
void Evaluate(char *expression, char *result){
sprintf(result, "%g", Solve(&expression));
}
Since the OP''s " reference implementation " is in C#, I wrote a semi-compressed C# version as well:
D P(D o){
return o!=6?o!=7&&o!=2?o<2?0:1:2:3;
}
D T(ref S s){
int i;
if(s[i=0]<48)
i++;
while(i<s.Length&&s[i]>47&s[i]<58|s[i]==46)
i++;
S t=s;
s=s.Substring(i);
return D.Parse(t.Substring(0,i));
}
D V(ref S s,out D o){
D r;
if(s[0]!=40)
r=T(ref s);
else{s=s.Substring(1);r=M(ref s);}
if(s=="")
o=0;
else{o=s[0]&7;s=s.Substring(1);}
return r;
}
void L(ref D v,ref D o,ref S s){
D p,r=V(ref s,out p),u=v;
for(;P(o)<P(p);)
L(ref r,ref p,ref s);
v = new Func<D>[]{()=>u*r,()=>u+r,()=>0,()=>u-r,()=>Math.Pow(u,r),()=>u/r}[(int)o-2]();
o=p;
}
D M(ref S s){
for(D o,r=V(ref s,out o);o>1)
L(ref r,ref o,ref s);
return r;
}
C (465 caracteres)
#define F for(i=0;P-8;i+=2)
#define V t[i
#define P V+1]
#define S V+2]),K(&L,4),i-=2)
#define L V-2]
K(double*t,int i){for(*++t=4;*t-8;*++t=V])*++t=V];}M(double*t){int i,p,b;
F if(!P)for(p=1,b=i;i+=2,p;)P?P-1||--p||(P=8,M(t+b+2),K(t+b,i-b),i=b):++p;
F P-6||(L=pow(L,S;F P-2&&P-7||(L*=(P-7?V+2]:1/S;F P-4&&(L+=(P-5?V+2]:-S;
F L=V];}E(char*s,char*r){double t[99];char*e,i=2,z=0;for(;*s;i+=2)V]=
strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;P=8;M(t+2);sprintf(r,"%g",*t);}
Se requieren las primeras cinco nuevas líneas, el resto está allí solo para facilitar la lectura. He contado los primeros cinco saltos como un personaje cada uno. Si quieres medirlo en líneas, fueron 28 líneas antes de eliminar todo el espacio en blanco, pero ese es un número bastante sin sentido. Podría haber sido cualquier cosa desde 6 líneas hasta un millón, dependiendo de cómo lo haya formateado.
El punto de entrada es E() (para "evaluar"). El primer parámetro es la cadena de entrada, y el segundo parámetro apunta a la cadena de salida, y debe ser asignado por la persona que llama (según los estándares habituales de C). Puede manejar hasta 47 tokens, donde un token es un operador (uno de " +-*/^() ") o un número de coma flotante. Los operadores de signo unarios no cuentan como un token separado.
Este código se basa libremente en un proyecto que hice hace muchos años como ejercicio. Saqué todo el manejo de errores y el espacio en blanco omitiendo y volviéndome a usar técnicas de golf. A continuación se encuentran las 28 líneas, con suficiente formato que pude escribir , pero probablemente no lo suficiente para leerlo . <math.h> <stdlib.h> , <stdio.h> y <math.h> (o ver la nota en la parte inferior).
Vea después del código una explicación de cómo funciona.
#define F for(i=0;P-8;i+=2)
#define V t[i
#define P V+1]
#define S V+2]),K(&L,4),i-=2)
#define L V-2]
K(double*t,int i){
for(*++t=4;*t-8;*++t=V])
*++t=V];
}
M(double*t){
int i,p,b;
F if(!P)
for(p=1,b=i;i+=2,p;)
P?P-1||--p||(P=8,M(t+b+2),K(t+b,i-b),i=b):++p;
F P-6||(L=pow(L,S;
F P-2&&P-7||(L*=(P-7?V+2]:1/S;
F P-4&&(L+=(P-5?V+2]:-S;
F L=V];
}
E(char*s,char*r){
double t[99];
char*e,i=2,z=0;
for(;*s;i+=2)
V]=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
P=8;
M(t+2);
sprintf(r,"%g",*t);
}
El primer paso es tokenizar. La matriz de dobles contiene dos valores para cada token, un operador ( P , porque O parece mucho a cero) y un valor ( V ). Esta tokenización es lo que se hace en el bucle for en E() . También trata con cualquier operador unario + y - , incorporándolos en la constante.
El campo "operador" de la matriz de tokens puede tener uno de los siguientes valores:
0 :
(
1 :)
2 :*
3 :+
4 : un valor constante de coma flotante
5 :-
6 :^
7 :/
8 : final de la cadena token
Este esquema fue en gran parte derivado por Daniel Martin , quien notó que los últimos 3 bits eran únicos en la representación ASCII de cada uno de los operadores en este desafío.
Una versión sin comprimir de E() se vería así:
void Evaluate(char *expression, char *result){
double tokenList[99];
char *parseEnd;
int i = 2, prevOperator = 0;
/* i must start at 2, because the EvalTokens will write before the
* beginning of the array. This is to allow overwriting an opening
* parenthesis with the value of the subexpression. */
for(; *expression != 0; i += 2){
/* try to parse a constant floating-point value */
tokenList[i] = strtod(expression, &parseEnd);
/* explanation below code */
if(parseEnd != expression && prevOperator != 4/*constant*/ &&
prevOperator != 1/*close paren*/){
expression = parseEnd;
prevOperator = tokenList[i + 1] = 4/*constant*/;
}else{
/* it''s an operator */
prevOperator = tokenList[i + 1] = *expression & 7;
expression++;
}
}
/* done parsing, add end-of-token-string operator */
tokenList[i + 1] = 8/*end*/
/* Evaluate the expression in the token list */
EvalTokens(tokenList + 2); /* remember the offset by 2 above? */
sprintf(result, "%g", tokenList[0]/* result ends up in first value */);
}
Como tenemos una entrada válida garantizada, la única razón por la que el análisis fallaría sería porque el próximo token es un operador. Si esto sucede, el puntero parseEnd será el mismo que tokenStart . También debemos manejar el caso donde el análisis tuvo éxito , pero lo que realmente queríamos era un operador. Esto ocurriría para los operadores de suma y resta, a menos que un operador de señal siga directamente. En otras palabras, dada la expresión " 4-6 ", queremos analizarlo como {4, -, 6} , y no como {4, -6} . Por otro lado, dado " 4+-6 ", deberíamos analizarlo como {4, +, -6} . La solución es bastante simple. Si el análisis falla O el token anterior era una constante o un paréntesis de cierre (de hecho una subexpresión que se evaluará a una constante), entonces el token actual es un operador, de lo contrario es una constante.
Después de realizar la tokenización, el cálculo y el plegado se realizan llamando a M() , que primero busca pares pareados de paréntesis y procesa las subexpresiones contenidas dentro al llamarse recursivamente. Luego procesa operadores, primera exponenciación, luego multiplicación y división juntas, y finalmente suma y resta juntas. Debido a que se espera una entrada bien formada (como se especifica en el desafío), no verifica explícitamente el operador de suma, ya que es el último operador legal después de que todos los demás se procesaron.
La función de cálculo, que carece de compresión de golf, se vería así:
void EvalTokens(double *tokenList){
int i, parenLevel, parenStart;
for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
if(tokenList[i + 1] == 0/*open paren*/)
for(parenLevel = 1, parenStart = i; i += 2, parenLevel > 0){
if(tokenList[i + 1] == 0/*another open paren*/)
parenLevel++;
else if(tokenList[i + 1] == 1/*close paren*/)
if(--parenLevel == 0){
/* make this a temporary end of list */
tokenList[i + 1] = 8;
/* recursively handle the subexpression */
EvalTokens(tokenList + parenStart + 2);
/* fold the subexpression out */
FoldTokens(tokenList + parenStart, i - parenStart);
/* bring i back to where the folded value of the
* subexpression is now */
i = parenStart;
}
}
for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
if(tokenList[i + 1] == 6/*exponentiation operator (^)*/){
tokenList[i - 2] = pow(tokenList[i - 2], tokenList[i + 2]);
FoldTokens(tokenList + i - 2, 4);
i -= 2;
}
for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
if(tokenList[i + 1] == 2/*multiplication operator (*)*/ ||
tokenList[i + 1] == 7/*division operator (/)*/){
tokenList[i - 2] *=
(tokenList[i + 1] == 2 ?
tokenList[i + 2] :
1 / tokenList[i + 2]);
FoldTokens(tokenList + i - 2, 4);
i -= 2;
}
for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
if(tokenList[i + 1] != 4/*constant*/){
tokenList[i - 2] +=
(tokenList[i + 1] == 3 ?
tokenList[i + 2] :
-tokenList[i + 2]);
FoldTokens(tokenList + i - 2, 4);
i -= 2;
}
tokenList[-2] = tokenList[0];
/* the compressed code does the above in a loop, equivalent to:
*
* for(i = 0; tokenList[i + 1] != 8; i+= 2)
* tokenList[i - 2] = tokenList[i];
*
* This loop will actually only iterate once, and thanks to the
* liberal use of macros, is shorter. */
}
Cierta cantidad de compresión probablemente haría que esta función sea más fácil de leer.
Una vez que se realiza una operación, los operandos y el operador se retiran de la lista de tokens por K() (llamado a través de la macro S ). El resultado de la operación se deja como una constante en lugar de la expresión plegada. En consecuencia, el resultado final se deja al principio de la matriz de tokens, por lo que cuando el control vuelve a E() , simplemente lo imprime en una cadena, aprovechando el hecho de que el primer valor en la matriz es el campo de valor de la simbólico.
Esta llamada a FoldTokens() tiene lugar después de que se haya realizado una operación ( ^ , * , / , + o - ), o después de que se haya procesado una subexpresión (rodeada de paréntesis). La rutina FoldTokens() garantiza que el valor resultante tenga el tipo de operador correcto (4) y luego copia el resto de la expresión más grande de la subexpresión. Por ejemplo, cuando se procesa la expresión " 2+6*4+1 ", EvalTokens() primero calcula 6*4 , dejando el resultado en lugar del 6 ( 2+24*4+1 ). FoldTokens() luego elimina el resto de la expresión secundaria " 24*4 ", dejando 2+24+1 .
void FoldTokens(double *tokenList, int offset){
tokenList++;
tokenList[0] = 4; // force value to constant
while(tokenList[0] != 8/*end of token string*/){
tokenList[0] = tokenList[offset];
tokenList[1] = tokenList[offset + 1];
tokenList += 2;
}
}
Eso es. Las macros están ahí para reemplazar las operaciones comunes, y todo lo demás es solo una compresión de golf de lo anterior.
strager insiste en que el código debe incluir sentencias #include , ya que no funcionará correctamente sin un adecuado desclasamiento directo del strtod y pow y funciones. Como el desafío solo requiere una función, y no un programa completo, sostengo que esto no debería ser requerido. Sin embargo, las declaraciones a futuro podrían agregarse a un costo mínimo agregando el siguiente código:
#define D double
D strtod(),pow();
Luego reemplazaría todas las instancias de " double " en el código con " D ". Esto agregaría 19 caracteres al código, elevando el total a 484. Por otro lado, también podría convertir mi función para devolver un doble en lugar de una cadena, como hizo él, que recortaría 15 caracteres, cambiando la E() Funcionan a esto:
D E(char*s){
D t[99];
char*e,i=2,z=0;
for(;*s;i+=2)
V]=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
P=8;
M(t+2);
return*t;
}
Esto haría que el tamaño total del código sea 469 caracteres (o 452 sin las declaraciones avanzadas de strtod y pow , pero con la macro D ). Incluso sería posible recortar 1 caracteres más requiriendo que la persona que llama pase un puntero a un doble para el valor de retorno:
E(char*s,D*r){
D t[99];
char*e,i=2,z=0;
for(;*s;i+=2)
V=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
P=8;
M(t+2);
*r=*t;
}
Dejaré que el lector decida qué versión es la adecuada.
C99 (565 caracteres)
Minificado
#include<stdio.h>
#include<string.h>
#include<math.h>
float X(char*c){struct{float f;int d,c;}N[99],*C,*E,*P;char*o="+-*/^()",*q,d=1,x
=0;for(C=N;*c;){C->f=C->c=0;if(q=strchr(o,*c)){if(*c<42)d+=*c-41?8:-8;else{if(C
==N|C[-1].c)goto F;C->d=d+(q-o)/2*2;C->c=q-o+1;++C;}++c;}else{int n=0;F:sscanf(c
,"%f%n",&C->f,&n);c+=n;C->d=d;++C;}}for(E=N;E-C;++E)x=E->d>x?E->d:x;for(;x>0;--x
)for(E=P=N;E-C;E->d&&!E->c?P=E:0,++E)if(E->d==x&&E->c){switch((E++)->c){
#define Z(x,n)case n:P->f=P->f x E->f;break;
Z(+,1)Z(-,2)Z(*,3)Z(/,4)case 5:P->f=powf(P->f,E->f);}E->d=0;}return N->f;}
Expandido
#include<stdio.h>
#include<string.h>
#include<math.h>
float X(char*c){
struct{
float f;
int d,c;
}N[99],*C,*E,*P;
char*o="+-*/^()",*q,d=1,x=0;
for(C=N;*c;){
C->f=C->c=0;
if(q=strchr(o,*c)){
if(*c<42) // Parentheses.
d+=*c-41?8:-8;
else{ // +-*/^.
if(C==N|C[-1].c)
goto F;
C->d=d+(q-o)/2*2;
C->c=q-o+1;
++C;
}
++c;
}else{
int n=0;
F:
sscanf(c,"%f%n",&C->f,&n);
c+=n;
C->d=d;
++C;
}
}
for(E=N;E-C;++E)
x=E->d>x?E->d:x;
for(;x>0;--x)
for(E=P=N;E-C;E->d&&!E->c?P=E:0,++E)
if(E->d==x&&E->c){
switch((E++)->c){
#define Z(x,n)case n:P->f=P->f x E->f;break;
Z(+,1)
Z(-,2)
Z(*,3)
Z(/,4)
case 5:
P->f=powf(P->f,E->f);
}
E->d=0;
}
return N->f;
}
int main(){
assert(X("2+2")==4);
assert(X("-1^(-3*4/-6)")==1);
assert(X("-2^(2^(4-1))")==256);
assert(X("2*6/4^2*4/3")==1);
puts("success");
}
Explicación
Desarrollé mi propia técnica. Compruébelo usted mismo. =]
C (249 characters)
char*c;double m(char*s,int o){int i;c=s;double x=*s-40?strtod(c,&s):m(c+1,0);double y;for(;*c&&c-41;c++){for(i=0;i<7&&*c-"``-+/*^"[i];i++);if(i<7){if(i/2<=o/2){c-=*c!=41;break;}y=m(c+1,i);x=i-6?i-5?i-4?i-3?i-2?x:x-y:x+y:x/y:x*y:pow(x,y);}}return x;}
This is a somewhat-revamped version of my previous version. By using strtod instead of atof (props to P Daddy) I was able to cut it by ~90 chars!
Caracteristicas
- Supports exponentation, multiplication, division, addition, and subtraction. Note that it DOES NOT support unary minus, since that wasn''t mentioned in the spec, even though it was used in the OP''s test cases. I thought it was ambiguous enough to leave out
- It''s 249 chars long
- Supports double-precision arithmetic
- It''s 249 chars long
- Supports PEMDAS, though exponentation associates as "x^y^z"->"(x^y)^z", not as "x^(y^z)"
- Assumes that input isn''t garbage. Garbage in, garbage out.
- Did I mention it''s 249 chars long? :PAG
Uso
Pass a pointer to a null-terminated array of chars, then 0. Like so:
m(charPtr,0)
You must include math.h and stdlib.h in the source file you call the function from. Also note that char*c is defined globally at the start of the code. So don''t define any variable named c in anything using this. If you must have a way to negate things, "-[insert expression here]" is equivalent to "(0-[insert expression here])" the way the OP has precedence ordered
C#, 1328 bytes
My first try. It''s a full program with console IO.
using System;using System.Collections.Generic;using System.Linq;
using F3 = System.Func<double, double, double>;using C = System.Char;using D = System.Double;
using I = System.Int32;using S = System.String;using W = System.Action;
class F{public static void Main(){Console.WriteLine(new F().EE(Console.ReadLine()));}
D EE(S s){s="("+s.Replace(" ","")+")";
return V(LT(s.Select((c,i)=>c!=''-''||P(s[i-1])<0||s[i-1]=='')''?c:''_'')).GroupBy(t=>t.Item2).Select(g=>new S(g.Select(t=>t.Item1).ToArray())));}
I P(C c){return (" __^^*/+-()".IndexOf(c)-1)/2;}
D V(IEnumerable<S> s){Func<S,C,I>I=(_,c)=>_.IndexOf(c);
I l=0,n=0;var U=new List<S>();var E=new Stack<D>();var O=new Stack<C>();
Func<D>X=E.Pop;Action<D>Y=E.Push;F3 rpow=(x,y)=>Math.Pow(y,x);F3 rdiv=(x,y)=>y/x;
W[]OA={()=>Y(rpow(X(),X())),()=>Y(X()*X()),()=>Y(rdiv(X(),X())),()=>Y(X()+X()),()=>Y(-X()+X()),()=>Y(-X()),};
O.Push('')'');foreach(S k in s.TakeWhile(t=>l>0||n==0)){n++;I a=I("(",k[0])-I(")",k[0]);l+=a;
if(l>1||l==-a)U.Add(k);else{if(U.Count>0)E.Push(V(U));U.Clear();I p = Math.Min(P(k[0]),P(''-''));
if(p<0)E.Push(D.Parse(k));else{while(P(O.Peek())<=p)OA[I("^*/+-_",O.Pop())]();O.Push(k[0]);}}}
return X();}
IEnumerable<Tuple<C,I>> LT(IEnumerable<C> s){I i=-1,l=-2;foreach(C c in s){I p=P(c);if(p>=0||p!=l)i++;l=P(c);yield return Tuple.Create(c,i);}}}
Here it is un-golfified:
using System;
using System.Collections.Generic;
using System.Linq;
class E
{
public static void Main()
{
Console.WriteLine(EvalEntry(Console.ReadLine()));
}
public static double EvalEntry(string s)
{
return Eval(Tokenize("(" + s.Replace(" ", "") + ")"));
}
const char UnaryMinus = ''_'';
static int Precedence(char op)
{
// __ and () have special (illogical at first glance) placement as an "optimization" aka hack
return (" __^^*/+-()".IndexOf(op) - 1) / 2;
}
static double Eval(IEnumerable<string> s)
{
Func<string, char, int> I = (_, c) => _.IndexOf(c);
Func<char, int> L = c => I("(", c) - I(")", c);
// level
int l = 0;
// token count
int n = 0;
// subeval
var U = new List<string>();
// evaluation stack
var E = new Stack<double>();
// operation stack
var O = new Stack<char>();
Func<double> pop = E.Pop;
Action<double> push = E.Push;
Func<double, double, double> rpow = (x, y) => Math.Pow(y, x);
Func<double, double, double> rdiv = (x, y) => y / x;
// ^*/+-_
Action[] operationActions =
{
() => push(rpow(pop(), pop())),
() => push(pop()*pop()),
() => push(rdiv(pop(),pop())),
() => push(pop()+pop()),
() => push(-pop()+pop()),
() => push(-pop()),
};
Func<char, Action> getAction = c => operationActions["^*/+-_".IndexOf(c)];
// ohhhhh here we have another hack!
O.Push('')'');
foreach (var k in s.TakeWhile(t => l > 0 || n == 0))
{
n++;
int adjust = L(k[0]);
l += L(k[0]);
/* major abuse of input conditioning here to catch the '')'' of a subgroup
* (level == 1 && adjust == -1) => (level == -adjust)
*/
if (l > 1 || l == -adjust)
{
U.Add(k);
continue;
}
if (U.Count > 0)
{
E.Push(Eval(U));
U.Clear();
}
int prec = Math.Min(Precedence(k[0]), Precedence(''-''));
// just push the number if it''s a number
if (prec == -1)
{
E.Push(double.Parse(k));
}
else
{
while (Precedence(O.Peek()) <= prec)
{
// apply op
getAction(O.Pop())();
}
O.Push(k[0]);
}
}
return E.Pop();
}
static IEnumerable<string> Tokenize(string s)
{
return
LocateTokens(PreprocessUnary(s))
.GroupBy(t => t.Item2)
.Select(g => new string(g.Select(t => t.Item1).ToArray()));
}
// make sure the string doesn''t start with -
static IEnumerable<char> PreprocessUnary(string s)
{
return s.Select((c, i) => c != ''-'' || Precedence(s[i - 1]) < 0 || s[i - 1] == '')'' ? c : UnaryMinus);
}
static IEnumerable<Tuple<char, int>> LocateTokens(IEnumerable<char> chars)
{
int i = -1;
int lastPrec = -2;
foreach (char c in chars)
{
var prec = Precedence(c);
if (prec >= 0 || prec != lastPrec)
{
i++;
lastPrec = Precedence(c);
}
yield return Tuple.Create(c, i);
}
}
}
Ruby, 61 lines, includes console input
puts class RHEvaluator
def setup e
@x = e
getsym
rhEval
end
def getsym
@c = @x[0]
@x = @x.drop 1
end
def flatEval(op, a, b)
case op
when ?* then a*b
when ?/ then a/b
when ?+ then a+b
when ?- then a-b
when ?^ then a**b
end
end
def factor
t = @c
getsym
t = case t
when ?- then -factor
when ?0..?9 then t.to_f - ?0
when ?(
t = rhEval
getsym # eat )
t
end
t
end
def power
v = factor
while @c == ?^
op = @c
getsym
v = flatEval op, v, factor
end
v
end
def multiplier
v = power
while @c == ?* or @c == ?/
op = @c
getsym
v = flatEval op, v, power
end
v
end
def rhEval
v = multiplier
while @c == ?+ or @c == ?-
op = @c
getsym
v = flatEval op, v, multiplier
end
v
end
RHEvaluator # return an expression from the class def
end.new.setup gets.bytes.to_a
Ruby, now 44 lines
C89, 46 lines
These could be crammed a lot. The C program includes headers that aren''t strictly needed and a main() program that some other entries didn''t include. The Ruby program does I/O to get the strings, which wasn''t technically required...
I realized that the recursive descent parser doesn''t really need separate routines for each priority level, even though that''s how it''s always shown in references. So I revised my previous Ruby entry by collapsing the three binary priority levels into one recursive routine that takes a priority parameter. I added C89 for fun. It''s interesting that the two programs have about the same number of lines.
Ruby
puts class RHEvaluator
def setup e
@opByPri, @x, @TOPPRI = [[?+,0],[?-,0],[?*,1],[?/,1],[?^,2]], e, 3
getsym
rhEval 0
end
def getsym
@c = @x[0]
@x = @x.drop 1
end
def flatEval(op, a, b)
case op
when ?* then a*b
when ?/ then a/b
when ?+ then a+b
when ?- then a-b
when ?^ then a**b
end
end
def factor
t = @c
getsym
t = case t
when ?- then -factor
when ?0..?9 then t.to_f - ?0
when ?(
t = rhEval 0
getsym # eat )
t
end
t
end
def rhEval pri
return factor if pri >= @TOPPRI;
v = rhEval pri + 1
while (q = @opByPri.assoc(@c)) && q[1] == pri
op = @c
getsym
v = flatEval op, v, rhEval(pri + 1)
end
v
end
RHEvaluator # return an expression from the class def
end.new.setup gets.bytes.to_a
C89
#include <stdio.h>
#include <math.h>
#include <strings.h>
#define TOPPRI ''3''
#define getsym() token = *x++;
const char opByPri[] = "+0-0*1/1^2";
char token, *x;
double rhEval(int);
int main(int ac, char **av) {
x = av[1];
getsym();
return printf("%f/n", rhEval(''0'')), 0;
}
double flatEval(char op, double a, double b) {
switch (op) {
case ''*'': return a * b;
case ''/'': return a / b;
case ''+'': return a + b;
case ''-'': return a - b;
case ''^'': return pow(a, b);
} }
double factor(void) {
double d; char t = token;
getsym();
switch (t) {
case ''-'': return -factor();
case ''0'': case ''1'': case ''2'': case ''3'': case ''4'':
case ''5'': case ''6'': case ''7'': case ''8'': case ''9'':
return t - ''0'';
case ''('': d = rhEval(''0'');
getsym();
}
return d;
}
double rhEval(int pri) {
double v; char *q;
if (pri >= TOPPRI)
return factor();
v = rhEval(pri + 1);
while ((q = index(opByPri, token)) && q[1] == pri) {
char op = token;
getsym();
v = flatEval(op, v, rhEval(pri + 1));
}
return v;
}
Analizador de descenso recursivo en PARLANSE, un lenguaje similar a C con sintaxis LISP: [70 líneas, 1376 caracteres sin contar sangría por 4 necesarios para SO] EDITAR: Reglas cambiadas, alguien insistió en números flotantes, fijos. No hay llamadas a la biblioteca, excepto la conversión de flotador, entrada e impresión. [ahora 94 líneas, 1825 caracteres]
(define main (procedure void)
(local
(;; (define f (function float void))
(= [s string] (append (input) "$"))
(= [i natural] 1)
(define S (lambda f
(let (= v (P))
(value (loop
(case s:i)
"+" (;; (+= i) (+= v (P) );;
"-" (;; (+= i) (-= v (P) );;
else (return v)
)case
)loop
v
)value
)define
(define P (lambda f
(let (= v (T))
(value (loop
(case s:i)
"*" (;; (+= i) (= v (* v (T)) );;
"/" (;; (+= i) (= v (/ v (T)) );;
else (return v)
)case
)loop
v
)value
)define
(define T (lambda f
(let (= v (O))
(value (loop
(case s:i)
"^" (;; (+= i) (= v (** v (T)) );;
else (return v)
)case
)loop
v
)value
)define
(define O (lambda f
(let (= v +0)
(value
(case s:i)
"(" (;; (+= i) (= v (E)) (+= i) );;
"-" (;; (+= i) (= v (- 0.0 (O))) );;
else (= v (StringToFloat (F))
)value
v
)let
)define
(define F (lambda f)
(let (= n (N))
(value
(;; (ifthen (== s:i ".")
(;; (+= i)
(= n (append n "."))
(= n (concatenate n (N)))
);;
)ifthen
(ifthen (== s:i "E")
(;; (+= i)
(= n (append n "E"))
(ifthen (== s:i "-")
(;; (+= i)
(= n (append n "-"))
(= n (concatenate n (N)))
);;
);;
)ifthen
);;
n
)let
)define
(define N (lambda (function string string)
(case s:i
(any "0" "1" "2" "3" "4" "5" "6" "7" "8" "9")
(value (+= i)
(append ? s:(-- i))
)value
else ?
)case
)define
);;
(print (S))
)local
)define
Asume una expresión bien formada, números flotantes con al menos un dígito inicial, exponentes opcionales como Enn o E-nnn. No compilado y ejecutado.
Pecularidades: la definición f es esencialmente signature typedef. Las lambdas son las funciones de análisis, una por regla de gramática. Se llama a una función F escribiendo (F args). Las funciones PARLANSE tienen un alcance léxico, por lo que cada función tiene acceso implícito a la expresión s a evaluar y un índice de exploración de cadenas i.
La gramática implementada es:
E = S $ ;
S = P ;
S = S + P ;
P = T ;
P = P * T ;
T = O ;
T = O ^ T ;
O = ( S ) ;
O = - O ;
O = F ;
F = digits {. digits} { E {-} digits} ;
C #, 13 líneas:
static string Calc(string exp)
{
WebRequest request = WebRequest.Create("http://google.com/search?q=" +
HttpUtility.UrlDecode(exp));
using (WebResponse response = request.GetResponse())
using (Stream dataStream = response.GetResponseStream())
using (StreamReader reader = new StreamReader(dataStream))
{
string r = reader.ReadToEnd();
int start = r.IndexOf(" = ") + 3;
int end = r.IndexOf("<", start);
return r.Substring(start, end - start);
}
}
Esto se comprime a unos 317 caracteres:
static string C(string e){var q = WebRequest.Create("http://google.com/search?q="
+HttpUtility.UrlDecode(e));using (var p=q.GetResponse()) using (var s=
p.GetResponseStream()) using (var d = new StreamReader(dataStream)){var
r=d.ReadToEnd();var t=r.IndexOf(" = ") + 3;var e=r.IndexOf("<",t);return
r.Substring(t,e-t);}}
Gracias a Mark y P Daddy en los comentarios, se comprime a 195 caracteres :
string C(string f){using(var c=new WebClient()){var r=c.DownloadString
("http://google.com/search?q="+HttpUtility.UrlDecode(f));int s=r.IndexOf(
" = ")+3;return r.Substring(s,r.IndexOf("<",f)-s);}}
I know, I know..this code-golf seems to be closed. Still, I felt the urge to code this stuff in erlang __ , so here is an erlang version (didn''t found the will to golf-format it, so these are 58 lines, about 1400 chars)
-module (math_eval).
-export ([eval/1]).
eval( Str ) ->
ev(number, Str,[]).
ev( _, [], Stack ) -> [Num] = do(Stack), Num;
ev( State, [$ |Str], Stack ) ->
ev( State,Str,Stack );
ev( number, [$(|Str], Stack ) ->
ev( number,Str,[$(|Stack] );
ev( number, Str, Stack ) ->
{Num,Str1} = r(Str),
ev( operator,Str1,[Num|Stack] );
ev( operator, [$)|Str], Stack) ->
ev( operator, Str, do(Stack) );
ev( operator, [Op2|Str], [N2,Op,N1|T]=Stack ) when is_float(N1) andalso is_float(N2) ->
case p(Op2,Op) of
true -> ev( number, Str, [Op2|Stack]);
false -> ev( operator, [Op2|Str], [c(Op,N1,N2)|T] )
end;
ev( operator, [Op|Str], Stack ) ->
ev( number,Str,[Op|Stack] ).
do(Stack) ->
do(Stack,0).
do([],V) -> [V];
do([$(|Stack],V) -> [V|Stack];
do([N2,Op,N1|Stack],0) ->
do(Stack,c(Op,N1,N2));
do([Op,N1|Stack],V) ->
do(Stack,c(Op,N1,V)).
p(O1,O2) -> op(O1) < op(O2).
op(O) ->
case O of
$) -> 0; $( -> 0;
$^ -> 1;
$* -> 2; $/ -> 2;
$+ -> 3; $- -> 3;
$ -> 4; _ -> -1
end.
r(L) ->
r(L,[]).
r([], Out) ->
{f( lists:reverse(Out) ),[]};
r([$-|R],[]) ->
r(R,[$-]);
r([C|T]=R,O) ->
if (C =< $9 andalso C >= $0) orelse C =:= $. -> r(T,[C|O]);
true -> {f(lists:reverse(O)),R}
end.
f(L) ->
case lists:any(fun(C) -> C =:= $. end,L) of
true -> list_to_float(L);
false -> list_to_float(L++".0")
end.
c($+,A,B) -> A+B;
c($-,A,B) -> A-B;
c($*,A,B) -> A*B;
c($/,A,B) -> A/B;
c($^,A,B) -> math:pow(A,B).
I wrote an attp at http://www.sumtree.com as an educational tool for teachers that does this.
Used bison for the parsing and wxwidgets for the GUI.
This is my "reference implementation" in C# (somewhat unwieldy).
static int RevIndexOf(string S, char Ch, int StartPos)
{
for (int P = StartPos; P >= 0; P--)
if (S[P] == Ch)
return P;
return -1;
}
static bool IsDigit(char Ch)
{
return (((Ch >= ''0'') && (Ch <= ''9'')) || (Ch == ''.''));
}
static int GetNextOperator(List<string> Tokens)
{
int R = Tokens.IndexOf("^");
if (R != -1)
return R;
int P1 = Tokens.IndexOf("*");
int P2 = Tokens.IndexOf("/");
if ((P1 == -1) && (P2 != -1))
return P2;
if ((P1 != -1) && (P2 == -1))
return P1;
if ((P1 != -1) && (P2 != -1))
return Math.Min(P1, P2);
P1 = Tokens.IndexOf("+");
P2 = Tokens.IndexOf("-");
if ((P1 == -1) && (P2 != -1))
return P2;
if ((P1 != -1) && (P2 == -1))
return P1;
if ((P1 != -1) && (P2 != -1))
return Math.Min(P1, P2);
return -1;
}
static string ParseSubExpression(string SubExpression)
{
string[] AA = new string[] { "--", "++", "+-", "-+" };
string[] BB = new string[] { "+", "+", "-", "-" };
for (int I = 0; I < 4; I++)
while (SubExpression.IndexOf(AA[I]) != -1)
SubExpression = SubExpression.Replace(AA[I], BB[I]);
const string Operators = "^*/+-";
List<string> Tokens = new List<string>();
string Token = "";
foreach (char Ch in SubExpression)
if (IsDigit(Ch) || (("+-".IndexOf(Ch) != -1) && (Token == "")))
Token += Ch;
else
if (Operators.IndexOf(Ch) != -1)
{
Tokens.Add(Token);
Tokens.Add(Ch + "");
Token = "";
}
else
throw new Exception("Unhandled error: invalid expression.");
Tokens.Add(Token);
int P1 = GetNextOperator(Tokens);
while (P1 != -1)
{
double A = double.Parse(Tokens[P1 - 1]);
double B = double.Parse(Tokens[P1 + 1]);
double R = 0;
switch (Tokens[P1][0])
{
case ''^'':
R = Math.Pow(A, B);
break;
case ''*'':
R = A * B;
break;
case ''/'':
R = A / B;
break;
case ''+'':
R = A + B;
break;
case ''-'':
R = A - B;
break;
}
Tokens[P1] = R.ToString();
Tokens.RemoveAt(P1 + 1);
Tokens.RemoveAt(P1 - 1);
P1 = GetNextOperator(Tokens);
}
if (Tokens.Count == 1)
return Tokens[0];
else
throw new Exception("Unhandled error.");
}
static bool FindSubExpression(string Expression, out string Left, out string Middle, out string Right)
{
int P2 = Expression.IndexOf('')'');
if (P2 == -1)
{
Left = "";
Middle = "";
Right = "";
return false;
}
else
{
int P1 = RevIndexOf(Expression, ''('', P2);
if (P1 == -1)
throw new Exception("Unhandled error: unbalanced parentheses.");
Left = Expression.Substring(0, P1);
Middle = Expression.Substring(P1 + 1, P2 - P1 - 1);
Right = Expression.Remove(0, P2 + 1);
return true;
}
}
static string ParseExpression(string Expression)
{
Expression = Expression.Replace(" ", "");
string Left, Middle, Right;
while (FindSubExpression(Expression, out Left, out Middle, out Right))
Expression = Left + ParseSubExpression(Middle) + Right;
return ParseSubExpression(Expression);
}