analizar la expresión matemática en c ++

Tengo una pregunta sobre Parsing Trees:

Tengo una cuerda (math expresion estring), por ejemplo: (a+b)*c-(de)*f/g . Tengo que analizar esa expresión en un árbol:

 class Exp{}; class Term: public Exp{ int n_; } class Node: Public Exp{ Exp* loperator_; Exp* roperator_; char operation; // +, -, *, / } 

¿Qué algoritmo puedo usar para construir un árbol que represente la cadena de expresión anterior?

Use el algoritmo de yarda de derivación . La descripción de la wikipedia es bastante completa, espero que sea suficiente.

También puede intentar escribir una gramática formal, por ejemplo, una gramática de expresión sintáctica , y usar una herramienta para generar un analizador sintáctico. Este sitio sobre PEG enumera 3 bibliotecas C / C ++ para analizar PEG.

(a+b)*c-(de)*f/g es una expresión in-fix.

Para hacer fácilmente un árbol , primero conviértalo en una expresión de prefijo.

Del ejemplo, el prefijo de (A * B) + (C / D) es + (* AB) (/ CD)

  (+) / \ / \ (*) (/) / \ / \ ABCD ((A*B)+(C/D)) 

Su árbol se ve como + como su nodo raíz. Puede continuar rellenando el subárbol izquierdo y derecho, sobre cada operador.

Además, este enlace explica el análisis de descenso recursivo en detalle y puede implementarse.

El primer paso es escribir una gramática para tus expresiones. El segundo paso para un caso tan simple es escribir un analizador de descenso recursivo, ese es el algoritmo que recomendaría. Aquí está la página wiki sobre analizadores de descenso recursivo que tiene una buena implementación de C en busca.

http://en.wikipedia.org/wiki/Recursive_descent_parser

 #include  #include  #include  #include  #include  using namespace std; class Exp{ public: // Exp(){} virtual void print(){} virtual void release(){} }; class Term: public Exp { string val; public: Term(string v):val(v){} void print(){ cout << ' ' << val << ' '; } void release(){} }; class Node: public Exp{ Exp *l_exp; Exp *r_exp; char op; // +, -, *, / public: Node(char op, Exp* left, Exp* right):op(op),l_exp(left), r_exp(right){} ~Node(){ } void print(){ cout << '(' << op << ' '; l_exp->print(); r_exp->print(); cout << ')'; } void release(){ l_exp->release(); r_exp->release(); delete l_exp; delete r_exp; } }; Exp* strToExp(string &str){ int level = 0;//inside parentheses check //case + or - //most right '+' or '-' (but not inside '()') search and split for(int i=str.size()-1;i>=0;--i){ char c = str[i]; if(c == ')'){ ++level; continue; } if(c == '('){ --level; continue; } if(level>0) continue; if((c == '+' || c == '-') && i!=0 ){//if i==0 then s[0] is sign string left(str.substr(0,i)); string right(str.substr(i+1)); return new Node(c, strToExp(left), strToExp(right)); } } //case * or / //most right '*' or '/' (but not inside '()') search and split for(int i=str.size()-1;i>=0;--i){ char c = str[i]; if(c == ')'){ ++level; continue; } if(c == '('){ --level; continue; } if(level>0) continue; if(c == '*' || c == '/'){ string left(str.substr(0,i)); string right(str.substr(i+1)); return new Node(c, strToExp(left), strToExp(right)); } } if(str[0]=='('){ //case () //pull out inside and to strToExp for(int i=0;iprint(); tree->release(); delete tree; } //output:(- (* (+ ab ) c )(/ (* (- de ) f ) g )) 

Puedes usar esta gramática para crear tu expresión.

 exp: /* empty */ | non_empty_exp { print_exp(); } ; non_empty_exp: mult_div_exp | add_sub_exp ; mult_div_exp: primary_exp | mult_div_exp '*' primary_exp { push_node('*'); } | mult_div_exp '/' primary_exp { push_node('/'); } ; add_sub_exp: non_empty_exp '+' mult_div_exp { push_node('+'); } | non_empty_exp '-' mult_div_exp { push_node('-'); } ; primary_exp: | '(' non_empty_exp ')' | NUMBER { push_term($1); } ; 

Y lo siguiente para tu Lexer.

 [ \t]+ {} [0-9]+ { yylval.number = atoi(yytext); return NUMBER; } [()] { return *yytext; } [*/+-] { return *yytext; } 

La expresión se construye sobre la marcha, utilizando estas rutinas:

 std::list exps; /* push a term onto expression stack */ void push_term (int n) { Term *t = new Term; t->n_ = n; exps.push_front(t); } /* push a node onto expression stack, top two in stack are its children */ void push_node (char op) { Node *n = new Node; n->operation_ = op; n->roperator_ = exps.front(); exps.pop_front(); n->loperator_ = exps.front(); exps.pop_front(); exps.push_front(n); } /* * there is only one expression left on the stack, the one that was parsed */ void print_exp () { Exp *e = exps.front(); exps.pop_front(); print_exp(e); delete e; } 

La siguiente rutina puede imprimir bastante su árbol de expresiones:

 static void print_exp (Exp *e, std::string ws = "", std::string prefix = "") { Term *t = dynamic_cast(e); if (t) { std::cout << ws << prefix << t->n_ << std::endl; } else { Node *n = dynamic_cast(e); std::cout << ws << prefix << "'" << n->operation_ << "'" << std::endl; if (prefix.size()) { ws += (prefix[1] == '|' ? " |" : " "); ws += " "; } print_exp(n->loperator_, ws, " |- "); print_exp(n->roperator_, ws, " `- "); } } 

Escribí una clase para manejar esto en el día. Es un poco detallado y tal vez no es la cosa más eficiente en el planeta, pero maneja enteros con signo / sin signo, dobles, float, operaciones lógicas y bit a bit.

Detecta desbordamiento y subdesbordamiento numérico, devuelve texto descriptivo y códigos de error sobre syntax, puede forzarse a manejar dobles como enteros o ignorar señalización, admite precisión definible por el usuario y redondeo inteligente e incluso mostrará su trabajo si establece DebugMode (verdadero).

Por último …… no depende de ninguna biblioteca externa, por lo que puede simplemente incluirla.

Uso de muestra:

 CMathParser parser; double dResult = 0; int iResult = 0; //Double math: if (parser.Calculate("10 * 10 + (6 ^ 7) * (3.14)", &dResult) != CMathParser::ResultOk) { printf("Error in Formula: [%s].\n", parser.LastError()->Text); } printf("Double: %.4f\n", dResult); //Logical math: if (parser.Calculate("10 * 10 > 10 * 11", &iResult) != CMathParser::ResultOk) { printf("Error in Formula: [%s].\n", parser.LastError()->Text); } printf("Logical: %d\n", iResult); 

La última versión está siempre disponible a través del Repositorio CMathParser GitHub .