c++ - 通过 std::regex 从数学表达式制作树

Question

程序获取如下字符串:VARIABLE=EXPRESSION。

其中VARIABLE是一些字母和数字，首字母 EXPRESSION 是数学表达式，可以包括:

1) + or *
2) ( or )
3) numbers (for example, 5; 3.8; 1e+18, 8.41E-10)
4) another names of variables.

我需要使用 one 正则表达式将它变成树(仅在内存中)。 我怎样才能做到这一点？ 提出方法:

1. 从 () 中搜索 =
2. 从 () 中搜索 +
3. 从 () 中搜索 *
4. 如果找到某些东西 - 将表达式分成两部分，否则我们得到数字或变量。

看起来很简单，但我无法创建此表达式。 我还发现了如何将条件运算符放入正则表达式中。 大多数情况下，我只需要 3 个正则表达式来表示 =、+ 和 *。 例子: http://i.stack.imgur.com/I8R12.png

Answer 1

如 n.m. 所述，正则表达式无法处理嵌套的括号。然而，有一些简单的替代方法可以解析嵌套的括号，例如 recursive descent parsers .

例子:

enum TokenType
{
    TTId,
    TTNumber,
    TTPlus,
    TTMinus,
    TTTimes,
    TTDivide,
    TTLParen,
    TTRParen,
    TTEndOfInput
};

TokenType token = TTEndOfInput;
string tokenValue;
int peekChar();
void nextChar();
void error(string msg); // doesn't return
Value *createConstant(string value);
Value *createReadVariable(string name);
Value *createAdd(Value *l, Value *r);
Value *createSubtract(Value *l, Value *r);
Value *createMultiply(Value *l, Value *r);
Value *createDivide(Value *l, Value *r);
Value *createNegate(Value *l, Value *r);

Value *expression();

void getToken()
{
    token = TTEndOfInput;
    tokenValue = "";
    if(peekChar() == EOF)
        return;
    if(isalpha(peekChar()))
    {
        while(isalnum(peekChar()))
        {
            tokenValue += (char)peekChar();
            nextChar();
        }
        token = TTId;
        return;
    }
    if(isdigit(peekChar()) || peekChar() == '.')
    {
        while(isdigit(peekChar()))
        {
            tokenValue += (char)peekChar();
            nextChar();
        }
        if(peekChar() == '.')
        {
            tokenValue += (char)peekChar();
            nextChar();
            while(isdigit(peekChar()))
            {
                tokenValue += (char)peekChar();
                nextChar();
            }
            if(tokenValue == ".")
                error("missing digit");
        }
        if(peekChar() == 'e')
        {
            tokenValue += (char)peekChar();
            nextChar();
            if(peekChar() == '+' || peekChar() == '-')
            {
                tokenValue += (char)peekChar();
                nextChar();
            }
            if(!isdigit(peekChar()))
                error("missing digit");
            while(isdigit(peekChar()))
            {
                tokenValue += (char)peekChar();
                nextChar();
            }
        }
        token = TTNumber;
        return;
    }
    switch(peekChar())
    {
    case '+':
        token = TTPlus;
        nextChar();
        return;
    case '-':
        token = TTMinus;
        nextChar();
        return;
    case '*':
        token = TTTimes;
        nextChar();
        return;
    case '/':
        token = TTDivide;
        nextChar();
        return;
    case '(':
        token = TTLParen;
        nextChar();
        return;
    case ')':
        token = TTRParen;
        nextChar();
        return;
    default:
        error("invalid charater");
    }
}

Value *topLevel()
{
    Value *retval;
    switch(token)
    {
    case TTId:
        retval = createReadVariable(tokenValue);
        getToken();
        return retval;
    case TTNumber:
        retval = createConstant(tokenValue);
        getToken();
        return retval;
    case TTLParen:
        getToken();
        retval = expression();
        if(token != TTRParen)
            error("expected )");
        getToken();
        return retval;
    case TTMinus:
        getToken();
        return createNegate(topLevel());
    default:
        error("unexpected token");
    }
}

Value *mulDiv()
{
    Value *retval = topLevel();
    while(token == TTTimes || token == TTDivide)
    {
        TokenType operation = token;
        getToken();
        Value *rhs = topLevel();
        if(operation == TTTimes)
        {
            retval = createMultiply(retval, rhs);
        }
        else // operation == TTDivide
        {
            retval = createDivide(retval, rhs);
        }
    }
    return retval;
}

Value *addSub()
{
    Value *retval = mulDiv();
    while(token == TTPlus || token == TTMinus)
    {
        TokenType operation = token;
        getToken();
        Value *rhs = mulDiv();
        if(operation == TTPlus)
        {
            retval = createAdd(retval, rhs);
        }
        else // operation == TTMinus
        {
            retval = createSubtract(retval, rhs);
        }
    }
    return retval;
}

Value *expression()
{
    return addSub();
}

void error(string msg)
{
    cerr << "error : " << msg << endl;
    exit(1);
}

int main()
{
    getToken();
    Value *expressionTree = expression();
    // ...
    return 0;
}