Evaluación de expresiones aritméticas de cadena en C++

Question

Estoy buscando una forma sencilla de evaluar una expresión matemática sencilla a partir de una cadena, así:

3 * 2 + 4 * 1 + (4 + 9) * 6

sólo quiero + y * operaciones más ( y ) signos. Y * tiene más prioridad que +.

Answer 1

Creo que usted está buscando un simple recursive descent parser.

Aquí hay un ejemplo muy sencillo:

const char * expressionToParse = "3*2+4*1+(4+9)*6"; 

char peek() 
{ 
    return *expressionToParse; 
} 

char get() 
{ 
    return *expressionToParse++; 
} 

int expression(); 

int number() 
{ 
    int result = get() - '0'; 
    while (peek() >= '0' && peek() <= '9') 
    { 
     result = 10*result + get() - '0'; 
    } 
    return result; 
} 

int factor() 
{ 
    if (peek() >= '0' && peek() <= '9') 
     return number(); 
    else if (peek() == '(') 
    { 
     get(); // '(' 
     int result = expression(); 
     get(); // ')' 
     return result; 
    } 
    else if (peek() == '-') 
    { 
     get(); 
     return -factor(); 
    } 
    return 0; // error 
} 

int term() 
{ 
    int result = factor(); 
    while (peek() == '*' || peek() == '/') 
     if (get() == '*') 
      result *= factor(); 
     else 
      result /= factor(); 
    return result; 
} 

int expression() 
{ 
    int result = term(); 
    while (peek() == '+' || peek() == '-') 
     if (get() == '+') 
      result += term(); 
     else 
      result -= term(); 
    return result; 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 

    int result = expression(); 

    return 0; 
} 

Answer 2

creo que se puede encontrar la respuesta en este post: Evaluating string "3*(4+2)" yield int 18

o se puede dar una oportunidad a esta biblioteca: http://weblogs.asp.net/pwelter34/archive/2007/05/05/calculator-net-calculator-that-evaluates-math-expressions.aspx

Answer 3

considerar el uso de espíritu impulso:

http://www.boost.org/doc/libs/1_35_0/libs/spirit/example/fundamental/ast_calc.cpp

Answer 4

Aquí hay una pequeña presentación sobre los árboles de evaluación de complejo (no realmente: p) expresiones matemáticas:

http://courses.cs.vt.edu/~cs1044/spring01/cstruble/notes/6.complexexpr.pdf

Te guiará por él con estilo;)

Answer 5

He escrito un evaluador de expresiones muy simple en C# (se requieren cambios mínimos para que sea compatible con C++). Se basa en el método de creación del árbol de expresiones, solo que el árbol no está realmente construido, pero todos los nodos se evalúan in situ.

Se puede encontrar en esta dirección: Simple Arithmetic Expression Evaluator

Answer 6

Si bien la búsqueda de una biblioteca para una tarea similar encontré libmatheval. Parece ser una cosa adecuada. Lamentablemente, GPL, que es inaceptable para mí.

Answer 7

import java.util.Deque; 
import java.util.LinkedList; 


public class EvaluateArithmeticExpression { 
    public static void main(String[] args) { 
     System.out.println(evaluate("-4*2/2^3+3")==-4*2/Math.pow(2, 3)+3); 
     System.out.println(evaluate("12*1314/(1*4)+300")==12*1314/(1*4)+300); 
     System.out.println(evaluate("123-(14*4)/4+300")==123-(14*4)/4+300); 
     System.out.println(evaluate("12*4+300")==12*4+300); 
    } 
    public static int evaluate(String s){ 
     Deque<Integer> vStack= new LinkedList<>(); 
     Deque<Character> opStack= new LinkedList<>(); 
     int i=0; 
     while(i<s.length()){ 
      if(isNum(s,i)) 
       i=getNum(s,vStack,i); 
      else if(isOp(s,i)) 
       i=doOp(s,opStack,vStack,i); 
     } 
     doOp(opStack,vStack); 
     return vStack.pop(); 
    } 
    private static int getNum(String s, Deque<Integer> vStack,int i){ 
     int sign=1; 
     if(s.charAt(i)=='-' || s.charAt(i)=='+') 
      sign=s.charAt(i++)=='-'?-1:1; 
     int val=0; 
     while(i<s.length() && isNum(s,i)) 
      val=val*10+s.charAt(i++)-'0'; 
     vStack.push(sign*val); 
     return i; 
    } 
    private static int doOp(String s, Deque<Character> opStack,Deque<Integer> vStack,int i){ 
     char op=s.charAt(i); 
     if(op=='(') 
      opStack.push(op); 
     else{ 
      if(op==')'){ 
       while(!opStack.isEmpty() && opStack.peekFirst()!='(') 
        doOp(opStack,vStack); 
       opStack.pop(); 
      } 
      else{ 
       while(!opStack.isEmpty() && prior(op)<=prior(opStack.peekFirst())) 
        doOp(opStack,vStack); 
       opStack.push(op); 
      } 
     } 
     return i+1; 
    } 
    private static int prior(char op){ 
     switch(op){ 
      case '+': 
      case '-': return 1; 
      case '*': 
      case '/': return 2; 
      case '^': return 4; 
     } 
     return 0; 
    } 
    private static void doOp(Deque<Character> opStack,Deque<Integer> vStack){ 
     int b=vStack.isEmpty()?0:vStack.pop(); 
     int a=vStack.isEmpty()?0:vStack.pop(); 
     char op=opStack.pop(); 
     int res=evaluate(a,b,op); 
     vStack.push(res); 
    } 
    private static int evaluate(int a, int b, char op){ 
     switch(op){ 
      case '+': return a+b; 
      case '-': return a-b; 
      case '/': return a/b; 
      case '*': return a*b; 
      case '^': return (int)Math.pow(a,b); 
     } 
     return 0; 
    } 
    private static boolean isNum(String s, int i){ 
     return '0'<=s.charAt(i) && s.charAt(i)<='9'; 
    } 
    private static boolean isOp(String s, int i){ 
     return "()+-*/^".contains(String.valueOf(s.charAt(i))); 
    } 
} 

Answer 8

Uno puede tratar: http://partow.net/programming/exprtk/index.html

1. muy simple
2. sólo tiene que incluir "exprtk.hpp" a su código fuente.
3. puede cambiar dinámicamente el valor de las variables de la expresión.
4. buen punto de partida: http://partow.net/programming/exprtk/code/exprtk_simple_example_01.cpp

Answer 9

sólo para añadir otra alternativa, considere probar TinyExpr para este problema. Es de código abierto y autónomo en un archivo de código fuente. En realidad está escrito en C, pero se compilará limpiamente como C++ en mi experiencia.

la solución de su expresión ejemplo de arriba es tan simple como:

#include "tinyexpr.h" 
#include <stdio.h> 

int main() 
{ 
    double answer = te_interp("3*2+4*1+(4+9)*6", 0); 
    printf("Answer is %f\n", answer); 
    return 0; 
}