Code Golf: evaluador de expresiones matemáticas (que respeta PEMDAS)

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, sum, 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 ( aquí ), 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 progtwigdores más inteligentes en sus idiomas de elección.

Relacionado:

Code Golf: Evaluación de expresiones matemáticas

Aclaraciones:

  1. Hagamos de esto una función que acepte un argumento de cadena y devuelva un resultado de cadena.

  2. 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”.

  3. Usar StrToFloat () es aceptable. Al “analizar la biblioteca” quise excluir elementos como los analizadores gtwigticales de propósito general, también para nivelar el campo de juego.

  4. Flotadores de soporte.

  5. Soporta paretheses, exponenciación y los cuatro operadores aritméticos.

  6. Proporcione la multiplicación y la división con la misma precedencia.

  7. Dar sum y resta igual precedencia.

  8. Para simplificar, puede suponer que todas las entradas están bien formadas.

  9. 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. 😉

  10. Para casos divididos por cero, quizás podría devolver “NaN” (suponiendo que desea implementar el manejo de errores).

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,ib),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; FL=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=es&&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 rest 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 . , y (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,ib),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; FL=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=es&&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 sum 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 sum 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 sum, 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 rest 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 rest 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 progtwig 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:

 DE(char*s){ D t[99]; char*e,i=2,z=0; for(;*s;i+=2) V]=strtod(s,&e),P=z=es&&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=es&&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.

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,et);}} 

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);}} 

J

 :[[/%^(:[[+-/^,&i|:[$[' ']^j+0__:k<3:]] 

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 mi with | Some(x,i2) -> fx 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 (fxy) } <|> 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 fxy } <|> parse { return x } } // Expression grammar of this code-golf question let AddOp = Lit '+' (fun xy -> 0. + x + y) <|> Lit '-' (fun xy -> 0. + x - y) let MulOp = Lit '*' (fun xy -> 0. + x * y) <|> Lit '/' (fun xy -> 0. + x / y) let ExpOp = Lit '^' (fun xy -> 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.

Analizador de descenso recursivo en PARLANSE, un lenguaje similar a C con syntax 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 comstackdo 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 scope 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} ; 

F #, 589 caracteres

He comprimido golf mi solución anterior en esta gem:

 let rec D a=function|c::s when System.Char.IsDigit c->D(c::a)s|s->a,s and L pos= let rec K(a,s)=match os with|None->a,s|Some(o,t)->let q,t=pt in K(oaq,t) K(ps) and E=L(LF (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 

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 { public T Value { get; set; } public Option(T x) { Value = x; } } delegate Option>> P(List input); static class Program { static List Cons(T x, List xs) { var r = new List(xs); r.Insert(0, x); return r; } static Option Some(T x) { return new Option(x); } static KeyValuePair> KVP(T x, List y) { return new KeyValuePair>(x,y); } // Core Parser Library static P Fail() { return i => null; } static P Select(this P p, Func 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 SelectMany(this P p, Func> sel, Func 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 Or(this P p1, P p2) { return i => { var r = p1(i); if (r == null) return p2(i); return r; }; } static P Sat(Func pred) { return i => { if (i.Count == 0 || !pred(i[0])) return null; var rest = new List(i); rest.RemoveAt(0); return Some(KVP(i[0], rest)); }; } static P Return(T x) { return i => Some(KVP(x,i)); } // Auxiliary Parser Library static P Digit = Sat(Char.IsDigit); static P Lit(char c, T r) { return from dummy in Sat(x => x == c) select r; } static P> Opt(P> p) { return p.Or(Return(new List())); } static P> Many(P p) { return Many1(p).Or(Return(new List())); } static P> Many1(P p) { return from x in p from xs in Many(p) select Cons(x, xs); } static P Chainl1(this P p, P> op) { return from x in p from r in Chainl1Helper(x, p, op) select r; } static P Chainl1Helper(T x, P p, P> 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 Chainr1(this P p, P> 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 TryParse(string s) { double d; if (Double.TryParse(s, out d)) return Return(d); return Fail(); } static void Main(string[] args) { var Num = from sign in Opt(Lit('-', new List(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((x,y) => x + y)) .Or(Lit('-', new Func((x, y) => x - y))); var MulOp = Lit('*', new Func((x, y) => x * y)) .Or(Lit('/', new Func((x, y) => x / y))); var ExpOp = Lit('^', new Func((x, y) => Math.Pow(x, y))); P Expr = null; P Term = null; P Factor = null; P Part = null; P 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 CodeGolf = s => Expr(new List(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 } } 

C99 (565 caracteres)

Minificado

 #include #include #include 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+(qo)/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;EC;++E)x=E->d>x?E->d:x;for(;x>0;--x )for(E=P=N;EC;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->fx 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 #include #include 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+(qo)/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;EC;++E) x=E->d>x?E->d:x; for(;x>0;--x) for(E=P=N;EC;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->fx 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 (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 

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 stack 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)); } 

Dado que la " implementación de referencia " del OP está en C #, también escribí una versión C-C semi-comprimida:

 DP(D o){ return o!=6?o!=7&&o!=2?o<2?0:1:2:3; } DT(ref S s){ int i; if(s[i=0]<48) i++; while(i47&s[i]<58|s[i]==46) i++; S t=s; s=s.Substring(i); return D.Parse(t.Substring(0,i)); } DV(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)[]{()=>u*r,()=>u+r,()=>0,()=>ur,()=>Math.Pow(u,r),()=>u/r}[(int)o-2](); o=p; } DM(ref S s){ for(D o,r=V(ref s,out o);o>1) L(ref r,ref o,ref s); return r; } 

F #, 52 líneas

Esto en su mayoría evita la generalidad, y solo se enfoca en escribir un analizador de descenso recursivo para resolver este problema exacto.

 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 fxy, cs let AddOp = function | '+'::cs -> Some((fun xy -> 0. + x + y), cs) | '-'::cs -> Some((fun xy -> 0. + x - y), cs) | _ -> None let MulOp = function | '*'::cs -> Some((fun xy -> 0. + x * y), cs) | '/'::cs -> Some((fun xy -> 0. + x / y), cs) | _ -> None let ExpOp = function | '^'::cs -> Some((fun xy -> 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, 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);} 

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.

Rubí

 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 ab 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  #include  #include  #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; } 

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:xy: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

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) -> AB; c($*,A,B) -> A*B; c($/,A,B) -> A/B; c($^,A,B) -> math:pow(A,B). 

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 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 Tokens = new List(); 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); } 

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 ab 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 

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;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())));} IP(C c){return (" __^^*/+-()".IndexOf(c)-1)/2;} DV(IEnumerable s){FuncI=(_,c)=>_.IndexOf(c); I l=0,n=0;var U=new List();var E=new Stack();var O=new Stack(); FuncX=E.Pop;ActionY=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> LT(IEnumerable 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 s) { Func I = (_, c) => _.IndexOf(c); Func L = c => I("(", c) - I(")", c); // level int l = 0; // token count int n = 0; // subeval var U = new List(); // evaluation stack var E = new Stack(); // operation stack var O = new Stack(); Func pop = E.Pop; Action push = E.Push; Func rpow = (x, y) => Math.Pow(y, x); Func 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 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 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 PreprocessUnary(string s) { return s.Select((c, i) => c != '-' || Precedence(s[i - 1]) < 0 || s[i - 1] == ')' ? c : UnaryMinus); } static IEnumerable> LocateTokens(IEnumerable 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); } } } 

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.