Escribir un analizador de ecuaciones simple

Qué tipo de algoritmos se usarían para hacer esto (como en, esto es una cadena, y quiero encontrar la respuesta):

((5 + (3 + (7 * 2))) - (8 * 9)) / 72 

Digamos que alguien escribió eso, ¿cómo podría lidiar con tantos paréntesis nesteds?

Puede usar el algoritmo de yarda de desvío o la notación polaca inversa , ambos usan stacks para manejar esto, wiki lo dijo mejor que yo.

De wiki,

 While there are tokens to be read: Read a token. If the token is a number, then add it to the output queue. If the token is a function token, then push it onto the stack. If the token is a function argument separator (eg, a comma): Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched. If the token is an operator, o1, then: while there is an operator token, o2, at the top of the stack, and either o1 is left-associative and its precedence is less than or equal to that of o2, or o1 is right-associative and its precedence is less than that of o2, pop o2 off the stack, onto the output queue; push o1 onto the stack. If the token is a left parenthesis, then push it onto the stack. If the token is a right parenthesis: Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. Pop the left parenthesis from the stack, but not onto the output queue. If the token at the top of the stack is a function token, pop it onto the output queue. If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. When there are no more tokens to read: While there are still operator tokens in the stack: If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. Pop the operator onto the output queue. Exit. 

La forma más fácil de resolver esto es implementar el algoritmo de yarda de derivación para convertir la expresión de la notación infija a la notación postfija.

Es Easy-with-a-capital-E para evaluar una expresión postfija.

El algoritmo de Shunting Yard se puede implementar en menos de 30 líneas de código. También deberá tokenizar la entrada (convertir la cadena de caracteres en una secuencia de operandos, operadores y puntuadores), pero escribir una máquina de estados simple para hacer eso es sencillo.

James ha proporcionado una buena respuesta. Wikipedia tiene un buen artículo sobre esto también.

Si (y no lo recomiendo) quisiste analizar esa expresión directamente, dado que parece ordenada en el sentido de que cada conjunto de parens no tiene más de un par de operandos, creo que podrías abordarlo así:

parse al primero “)”. Luego, vuelva a analizar el anterior “(“. Evalúe qué hay dentro y reemplace todo el conjunto con un valor. Luego repítalo recursivamente hasta que termine.

Entonces, en este ejemplo, primero analizaría “(7 * 2)” y lo reemplazaría con 14. Entonces obtendría (3 + 14) y lo reemplazaría con 17. Y así sucesivamente.

Puede hacerlo con Regex o incluso .IndexOf y .Substring.

Me voy sin beneficio de comprobar mi syntax aquí, pero algo como esto:

 int y = string.IndexOf(")"); int x = string.Substring(0,y).LastIndexOf("("); string z = string.Substring(x+1,yx-1) // This should result in "7 * 2" 

Tendrá que evaluar la expresión resultante y repetir esto hasta que los parens estén agotados y luego evaluar esa última parte de la cadena.

Puede usar un analizador de máquina de estado (yacc LALR, etc.) o un analizador de descenso recursivo.

El analizador podría emitir tokens RPN para evaluar o comstackr más tarde. O bien, en una implementación de intérprete inmediata, un analizador de descenso recursivo podría calcular subexpresiones sobre la marcha a medida que regresa de los tokens de hoja, y terminar con el resultado.

Usaría las herramientas que están disponibles en casi todas partes.
Me gusta Lex / Yacc porque los conozco, pero hay equivalentes en todas partes. Entonces, antes de escribir un código complejo, vea si hay herramientas que lo ayuden a simplificarlo (problemas como este han sido resueltos antes, así que no vuelva a inventar la rueda).

Entonces, usando lex (flex) / yacc (bison) haría:

el

 %option noyywrap Number [0-9]+ WhiteSpace [ \t\v\r]+ NewLine \n %{ #include  %} %% \( return '('; \) return ')'; \+ return '+'; \- return '-'; \* return '*'; \/ return '/'; {Number} return 'N'; {NewLine} return '\n'; {WhiteSpace} /* Ignore */ . fprintf(stdout,"Error\n");exit(1); %% 

ey

 %{ #include  typedef double (*Operator)(double,double); double mulOp(double l,double r) {return l*r;} double divOp(double l,double r) {return l/r;} double addOp(double l,double r) {return l+r;} double subOp(double l,double r) {return lr;} extern char* yytext; extern void yyerror(char const * msg); %} %union { Operator op; double value; } %type  MultOp AddOp %type  Expression MultExpr AddExpr BraceExpr %% Value: Expression '\n' { fprintf(stdout, "Result: %le\n", $1);return 0; } Expression: AddExpr { $$ = $1;} AddExpr: MultExpr { $$ = $1;} | AddExpr AddOp MultExpr { $$ = ($2)($1, $3);} MultExpr: BraceExpr { $$ = $1;} | MultExpr MultOp BraceExpr { $$ = ($2)($1, $3);} BraceExpr: '(' Expression ')' { $$ = $2;} | 'N' { sscanf(yytext,"%le", &$$);} MultOp: '*' { $$ = &mulOp;} | '/' { $$ = &divOp;} AddOp: '+' { $$ = &addOp;} | '-' { $$ = &subOp;} %% void yyerror(char const * msg) { fprintf(stdout,"Error: %s", msg); } int main() { yyparse(); } 

Construir

 > flex el > bison ey > gcc *.c > ./a.out ((5 + (3 + (7 * 2))) - (8 * 9)) / 72 Result: -6.944444e-01 > 

Lo anterior también maneja las reglas normales de precedencia del operador:
No por nada de lo que hice, pero alguien inteligente resolvió esto hace años y ahora puedes obtener las reglas gtwigticales para el análisis de expresiones fácilmente (Just google C Grammer y copia el bit que necesitas).

 > ./a.out 2 + 3 * 4 Result: 1.400000e+01 

Primero convierta la expresión en formulario de prefijo o postfijo. ¡Entonces es muy fácil de evaluar!

Ejemplo:

Evaluación de la expresión Postfix.

Si se sabe que las expresiones están completamente entre paréntesis (es decir, todos los paréntesis posibles están allí), entonces esto se puede hacer fácilmente mediante el análisis recursivo-descendente. Esencialmente, cada expresión es cualquiera de la forma

  number 

o de la forma

  (expression operator expression) 

Estos dos casos se pueden distinguir por su primer token, por lo que un simple descenso recursivo es suficiente. De hecho, he visto este problema exacto como una forma de probar el pensamiento recursivo en las clases introductorias de progtwigción.

Si no tiene necesariamente esta garantía, entonces puede ser una buena idea algún tipo de análisis de precedencia. Muchas de las otras respuestas a esta pregunta discuten varios sabores de algoritmos para hacer esto.

¿Qué? Nooooo. A menos que sea una tarea para hacer, no escriba un analizador. Hay un centenar de analizadores y todos tienen una ventaja sobre todas las sugerencias aquí: ya están ahí. No tienes que escribirlos.

Sí, el algoritmo es Algoritmo de yarda de desvío, pero si desea implementarlo, le sugiero que Python y su paquete de comstackción

 import compiler equation = "((5 + (3 + (7 * 2))) - (8 * 9)) / 72" parsed = compiler.parse( equation ) print parsed 

También puede evaluar esta expresión con el método incorporado de eval ()

 print eval("5 + (4./3) * 9") // 17 

O puede hacer esto en una línea en R:

 > eval(parse(text = '((5 + (3 + (7*2))) - (8 * 9))/72' )) [1] -0.6944444