Creando un evaluador de expresiones matemáticas

Question

No puedo usar boost :: spirit en mi entorno. Pero me gustaría utilizar STL y aumentar tanto como sea posible para construir mi propio evaluador de expresiones. ¿Hay alguna alternativa para impulsar :: espíritu?

Answer 1

YACC++ es una muy buena herramienta para el generador de analizadores para aplicaciones C++. ANTLR también es una buena opción si no tiene una buena documentación para su uso en C/C++.

Answer 2

El siguiente código incluye pruebas de unidad y un analizador completo que escribí en una sesión de aproximadamente 90 minutos en ACCU 200x (8 o 9). Si necesita más, puede ser bastante fácil de extender. Puede hacer que se duplique definiendo Parse::value_type, o extrayéndolo en un archivo de encabezado separado y conviértalo en una clase de plantilla.

O puede tomar los casos de prueba y pruébelo usted mismo. (utiliza CUTE desde http://cute-test.com)

#include "cute.h" 
#include "ide_listener.h" 
#include "cute_runner.h" 
#include <cctype> 
#include <map> 

namespace { 

class Parser { 
    typedef int value_type; 
    typedef std::vector<value_type> valuestack; 
    typedef std::vector<char> opstack; 
    typedef std::map<std::string,value_type> memory; 
public: 
    memory variables; 
    private: 
    void evaluateSingleOperator(char op,value_type &result,value_type operand) { 
     switch(op) { 
      case '+': result += operand; break; 
      case '-': result -= operand; break; 
      case '*': result *= operand; break; 
      case '/': result /= operand; break; 
      default: throw("invalid operand"); 
     } 
    } 
    void evaluateStacks(valuestack &values, opstack &ops) { 
     while(ops.size() && values.size()>1) { 
      char op = ops.back(); ops.pop_back(); 
      value_type operand = values.back(); values.pop_back(); 
      evaluateSingleOperator(op,values.back(),operand); 
     } 
    } 
    bool higherPrecedenceOrLeftAssociative(char last, char current) { 
     return (last == current)||(last == '*' || last == '/') ; 
    } 
    bool shouldEvaluate(char op,opstack const &ops) { 
     return ops.size() > 0 && higherPrecedenceOrLeftAssociative(ops.back(),op); 
    } 
    std::string parseVariableName(std::istream &is) { 
     std::string variable; 
     char nextchar=0; 
     while ((is >> nextchar) && isalpha(nextchar)) { 
      variable += nextchar;  
     } 
     if (variable.size() == 0) throw std::string("internal parse error"); 
     is.unget(); 
     return variable;  
    } 
    int peekWithSkipWhiteSpace(std::istream &is) { 
     int nextchar = EOF; 
     while(isspace(nextchar = is.peek())) is.get(); 
     return nextchar; 
    } 
    value_type getOperand(std::istream &is) { 
     int nextchar = peekWithSkipWhiteSpace(is); 
     if (nextchar == EOF) throw std::string("syntax error operand expected"); 
     if (isdigit(nextchar)){ 
      value_type operand=0; 
      if (!(is >> operand)) throw std::string("syntax error getting number") ; 
      return operand; 
     } else if ('(' == nextchar) { 
      is.get(); 
      return parse(is); 
     } else if (isalpha(nextchar)) { 
      std::string variable= parseVariableName(is); 
      if(parseAssignmentOperator(is)) { 
       variables[variable] = parse(is); 
      } else { 
       if (!variables.count(variable)) throw std::string("undefined variable: ")+variable; 
      } 
      return variables[variable]; 
     } 
     throw std::string("syntax error");   
    } 
    bool parseAssignmentOperator(std::istream &is) { 
     int nextchar = peekWithSkipWhiteSpace(is); 
     if ('=' != nextchar) { 
      return false; 
     } 
     is.get(); 
     return true; 
    } 
    public: 
    value_type parse(std::istream &is) { 
     is >> std::skipws; 
     valuestack values; 
     opstack ops; 
     values.push_back(getOperand(is)); 
     char op=')'; 
     while((is >>op) && op != ')') { 
      if (shouldEvaluate(op, ops)) { 
       evaluateStacks(values, ops); 
      } 
      values.push_back(getOperand(is)); 
      ops.push_back(op); 
     } 
     evaluateStacks(values,ops); 
     return values.back(); 
    } 
    value_type eval(std::string s) { 
     std::istringstream is(s); 
     return parse(is); 
    } 
}; 
int eval(std::string s) { 
    return Parser().eval(s); 
} 
void shouldThrowEmptyExpression() { 
    eval(""); 
} 
void shouldThrowSyntaxError() { 
    eval("()"); 
} 
void testSimpleNumber() { 
    ASSERT_EQUAL(5,eval("5")); 
} 
void testSimpleAdd() { 
    ASSERT_EQUAL(10,eval("5 +5")); 
} 
void testMultiAdd() { 
    ASSERT_EQUAL(10,eval("1 + 2 + 3+4")); 
} 
void testSimpleSubtract() { 
    ASSERT_EQUAL(5,eval("6-1")); 
} 
void testTenPlus12Minus100() { 
    ASSERT_EQUAL(-78,eval("10+12-100")); 
} 
void testMultiply() { 
    ASSERT_EQUAL(50,eval("10*5")); 
} 
void testDivision() { 
    ASSERT_EQUAL(7,eval("21/3")); 
} 
void testAddThenMultiply() { 
    ASSERT_EQUAL(21,eval("1+4 *5")); 
} 
void testAddThenMultiplyAdd() { 
    ASSERT_EQUAL(16,eval("1+4*5 -5")); 
} 
void testAddSubSub() { 
    ASSERT_EQUAL(-4,eval("1+2-3-4")); 
} 
void testSimpleParenthesis() { 
    ASSERT_EQUAL(1,eval("(1)")); 
} 
void testSimpleOperandParenthesis() { 
    ASSERT_EQUAL(2,eval("1+(1)")); 
} 
void testParenthesis() { 
    ASSERT_EQUAL(5,eval("2*(1+4)-5")); 
} 
void testNestedParenthesis() { 
    ASSERT_EQUAL(16,eval("2*(1+(4*3)-5)")); 
} 
void testDeeplyNestedParenthesis() { 
    ASSERT_EQUAL(8,eval("((2*((1+(4*3)-5)))/2)")); 
} 
void testSimpleAssignment() { 
    Parser p; 
    ASSERT_EQUAL(1, p.eval("a=1*(2-1)")); 
    ASSERT_EQUAL(8, p.eval("a+7")); 
    ASSERT_EQUAL(1, p.eval("2-a")); 
} 
void testLongerVariables() { 
    Parser p; 
    ASSERT_EQUAL(1, p.eval("aLongVariableName=1*(2-1)")); 
    ASSERT_EQUAL(42, p.eval("AnotherVariable=7*(4+2)")); 
    ASSERT_EQUAL(1, p.eval("2-(aLongVariableName*AnotherVariable)/42")); 
} 
void shouldThrowUndefined() { 
    eval("2 * undefinedVariable"); 
} 
void runSuite(){ 
    cute::suite s; 
    //TODO add your test here 
    s.push_back(CUTE_EXPECT(CUTE(shouldThrowEmptyExpression),std::string)); 
    s.push_back(CUTE_EXPECT(CUTE(shouldThrowSyntaxError),std::string)); 
    s.push_back(CUTE(testSimpleNumber)); 
    s.push_back(CUTE(testSimpleAdd)); 
    s.push_back(CUTE(testMultiAdd)); 
    s.push_back(CUTE(testSimpleSubtract)); 
    s.push_back(CUTE(testTenPlus12Minus100)); 
    s.push_back(CUTE(testMultiply)); 
    s.push_back(CUTE(testDivision)); 
    s.push_back(CUTE(testAddThenMultiply)); 
    s.push_back(CUTE(testAddSubSub)); 
    s.push_back(CUTE(testAddThenMultiplyAdd)); 
    s.push_back(CUTE(testSimpleParenthesis)); 
    s.push_back(CUTE(testSimpleOperandParenthesis)); 
    s.push_back(CUTE(testParenthesis)); 
    s.push_back(CUTE(testNestedParenthesis)); 
    s.push_back(CUTE(testDeeplyNestedParenthesis)); 
    s.push_back(CUTE(testSimpleAssignment)); 
    s.push_back(CUTE(testLongerVariables)); 
    s.push_back(CUTE_EXPECT(CUTE(shouldThrowUndefined),std::string)); 
    cute::ide_listener lis; 
    cute::makeRunner(lis)(s, "The Suite"); 
} 

} 
int main(){ 
runSuite(); 
}