构建一个数学表达式求值器

Question

我无法在我的环境中使用boost::spirit。但我想尽可能地使用STL和boost来构建我的表达式求值器。是否有类似于boost::spirit的替代品？

- Tae-Sung Shin

---

自己编写？CoCo/R？flex/bison？lex/yacc？ANTLR？当然，评估器不包括在内，但是如果有一个坚实的语法，应该很容易。 - sehe

@sehe 谢谢。我认为我知道你提到的一些解析器生成器，但我认为它们生成的是C或类似C的代码。有没有使用至少STL的东西？ - Tae-Sung Shin

Boost.Proto是Boost的表达式求值库；Boost.Spirit是一个解析库（建立在Boost.Proto之上）。 - ildjarn

@ildjarn 谢谢。我会尝试一下，但我怀疑它可能不适用于我的平台。 - Tae-Sung Shin

如果你在一个没有常用库Boost.Spirit的平台上工作，能否告诉我们你正在使用哪个平台（或者有什么额外的约束限制了你对库的使用）？这样可以更容易地建议适用于你平台的库。另外，告诉我们更多关于你尝试达成什么目标的信息也是一个好主意（例如你期望表达式变得多么复杂）。 - Grizzly

@Grizzly和Jared Krumsie，抱歉回复晚了，但由于某些原因，我没有收到你们的评论通知。基本上，我想在数学表达式求值器的基础上构建一个小型矩阵表达式求值器。理论上来说，这应该很容易，但实际上并非如此。我会看一下ExprTk，它看起来不错。谢谢。 - Tae-Sung Shin

Answer 1

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

或者您可以使用 CUTE（来自 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();
}

- PeterSom

Answer 2

YACC ++是C ++应用程序的解析器生成器非常好的工具。ANTLR也是一个不错的选择，但是其在C / C ++中的使用文档不够完善。

- Shivkumar