构建数学表达式求值程序 [英] Building a math expression evaluator

问题描述

我无法在我的环境中使用boost :: spirit。但我想使用STL和尽可能多的建立自己的表达式求值程序。有没有这样的替代boost :: spirit？

I can't use boost::spirit in my environment. But I would like to use STL and boost as much as possible to build my own expression evaluator. Is there such an alternative to boost::spirit?

推荐答案

以下代码包括单元测试和一个完整的解析器我写在在ACCU 200x（8或9）约90分钟。如果你需要更多，它可能很容易扩展。您可以通过定义 Parse :: value_type ，或者将其提取到单独的头文件中并将其作为模板类来使其重复。

The following code includes unit tests and a complete parser I wrote in an about 90 minute session at ACCU 200x (8 or 9). If you need more, it might be easy enough to extend. You can make it do doubles by defining Parse::value_type, or extracting it into a separate header file and make it a template class.

或者你可以参加测试用例并尝试自己。 （它使用来自 http://cute-test.com 的CUTE）

Or you can take the test cases and try yourself. (it uses CUTE from 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();
}

这篇关于构建数学表达式求值程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！