sistema - programa gauss jordan c++
Escribir un simple analizador de ecuaciones (10)
¿Qué? Nooooo. A menos que esto sea una tarea, no escriba un analizador. Hay cien analizadores por ahí y todos tienen una ventaja sobre todas las sugerencias aquí: ya están por ahí. No tienes que escribirlos.
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 anidados?
James ha proporcionado una buena respuesta. Wikipedia también tiene un buen artículo sobre esto.
Si (y no lo recomiendo) quisieras analizar esa expresión directamente, dado que parece ordenado en el sentido de que cada conjunto de parens no tiene más de un par de operandos, creo que podrías enfocarlo así:
parse a la primera ")". Luego vuelva a analizar el anterior "(". Evalúe lo que hay dentro y reemplace todo el conjunto con un valor. Luego repita de forma recursiva hasta que haya terminado.
Entonces, en este ejemplo, primero debe analizar "(7 * 2)" y reemplazarlo con 14. Luego, debería obtener (3 + 14) y reemplazarlo con 17. Y así sucesivamente.
Puedes hacerlo con Regex o incluso .IndexOf y .Substring.
Me voy sin el beneficio de revisar mi sintaxis aquí, pero algo como esto:
int y = string.IndexOf(")");
int x = string.Substring(0,y).LastIndexOf("(");
string z = string.Substring(x+1,y-x-1) // This should result in "7 * 2"
Tendrá que evaluar la expresión resultante y hacer un bucle hasta que los parens estén agotados y luego evaluar la última parte de la cadena.
La forma más fácil de resolver esto es implementar el algoritmo de Shunting Yard para convertir la expresión de notación de infijo a notación de postfix.
Es fácil-con-una-capital-E evaluar una expresión postfix.
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 signos de puntuación), pero escribir una máquina de estado simple para hacerlo es sencillo.
O simplemente puede hacer esto en una línea en R:
> eval(parse(text = ''((5 + (3 + (7*2))) - (8 * 9))/72'' ))
[1] -0.6944444
Primero convierta la expresión en forma de prefijo o postfijo. Entonces es muy fácil de evaluar!
Ejemplo:
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 compilar más tarde. O, en una implementación de intérprete inmediata, un analizador de descenso recursivo podría calcular las subexpresiones sobre la marcha cuando regresa de las fichas de hoja, y terminar con el resultado.
Puedes usar el algoritmo Shunting yard o la Notación polaca inversa , ambos usan pilas 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 (e.g., 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.
Sí, el algoritmo es un algoritmo de Shunting yard, pero si quieres implementarlo, te sugiero Python y su paquete de compilació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 eval () incorporado.
print eval("5 + (4./3) * 9") // 17
Si se sabe que las expresiones están entre paréntesis completos (es decir, todos los paréntesis posibles están ahí), entonces esto se puede hacer fácilmente mediante el análisis de descendencia recursiva. 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 es suficiente un simple descenso recursivo. De hecho, he visto este problema exacto dado como una forma de probar el pensamiento recursivo en las clases de programación introductoria.
Si no necesariamente tiene esta garantía, entonces una buena idea podría ser el análisis de precedencia. Muchas de las otras respuestas a esta pregunta discuten varios sabores de algoritmos para hacer esto.
Yo 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 código complejo, vea si hay herramientas que puedan ayudarlo a simplificarlo (problemas como este se han resuelto antes, así que no reinvente la rueda).
Entonces, usando lex (flex) / yacc (bison) haría:
el
%option noyywrap
Number [0-9]+
WhiteSpace [ /t/v/r]+
NewLine /n
%{
#include <stdio.h>
%}
%%
/( return ''('';
/) return '')'';
/+ return ''+'';
/- return ''-'';
/* return ''*'';
// return ''/'';
{Number} return ''N'';
{NewLine} return ''/n'';
{WhiteSpace} /* Ignore */
. fprintf(stdout,"Error/n");exit(1);
%%
ey
%{
#include <stdio.h>
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 l-r;}
extern char* yytext;
extern void yyerror(char const * msg);
%}
%union
{
Operator op;
double value;
}
%type <op> MultOp AddOp
%type <value> 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 e.l
> bison e.y
> 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 mucho tiempo y ahora puede obtener las reglas gramaticales para el análisis de expresiones fácilmente (solo busque en Google C Grammer y extraiga la parte que necesita).
> ./a.out
2 + 3 * 4
Result: 1.400000e+01