评估仅由加法和乘法组成的中缀字符串表达式

Question

如何计算仅由 + 和 * 运算符组成的中缀字符串表达式。（没有括号）。

示例 1：

输入："1+2*3"
输出：7

示例 2：

输入："1+2*3+4"
输出：11

这是我目前的代码（没有给出正确的结果），我想知道我是否可以用一个堆栈（或 none）

int evaluateExpression(string s) {
    stack<int> operandStack;
    stack<char> operatorStack;
    string token = "";
    for(char &c : s) {
        if(c == '*' || c == '+') {
            operandStack.push(stoi(token));
            operatorStack.push(c);
            token = "";
        }
        else {
            token += c;
        }
        if(operandStack.size() > 1 
            && operandStack.size() == operatorStack.size() + 1
            && operatorStack.top() == '*') {
                int a = operandStack.top(); operandStack.pop();
                int b = operandStack.top(); operandStack.pop();
                operandStack.push(a * b);
            }
    }
    
    while(operandStack.size() > 1) {
        int a = operandStack.top(); operandStack.pop();
        int b = operandStack.top(); operandStack.pop();
        operandStack.push(a + b);
    }
    
    return operandStack.top();
}

注意：不想使用任何非标准库。理想情况下不使用任何库。

Answer 1

是的，您只需要一堆。您可以将标准方法与 shift-reduce 解析器一起使用。对于您的情况和简单的语法，这可能已经有点太多了。但无论如何我都会描述它。

秘诀是使用“解析堆栈”。所以只有一堆。不是运算符 and 操作数堆栈。在那里您将使用属性标记。令牌具有类型，如 ADD、MULT、NUMBER 和关联属性。属性通常是联合或结构。 ADD 和 MULT 将为空，NUMBER 将包含一个值。

通常具有getNextToken功能的扫描仪将生成您的令牌。在你的情况下，非常简单，只有那 3 个标记。

然后，在一个循环中，您将始终执行以下操作。

始终将新令牌压入解析堆栈
尝试将堆栈顶部与语法的产生式（和前瞻标记）相匹配
减少堆栈（删除匹配的元素），计算表达式，并将结果放入解析堆栈

所以，总是：移动、匹配、减少

在您的情况下，匹配函数需要一个先行符号，因此，下一个标记。你会发现正是这样一个例子here。在那里你可以找到一个编译器，它有一个前端（扫描器、解析器）和 2 个不同的代码生成器作为后端。您的任务不需要代码生成器，您可以在减少的同时直接评估。

但是，对于如此简单的语法，您根本不需要堆栈。书中crafting A Compiler with C就是一个很好的例子。我的这本书是1991年的，当然内容仍然有效。

他们基本上在语法中为每个 production/terminal/non-terminal 编写一个函数并对标记求值并调用其他终端或非终端的函数。有趣的方法，对您的用例来说并不困难。

希望对您有所帮助。 . .

Answer 2

 int evaluateExpression(string s) {
        string token = "";
        char currOperator = '+';
        stack<int> st;
        string temp = s + '.';
        for(const char &c : temp) {
            if(isdigit(c)) {
                token += c;                    
            }
            else if(c != ' ') {
                if(currOperator == '*') {
                    int stackTop = st.top();
                    st.pop();
                    st.push(stackTop * stoi(token));
                }
              
                else if(currOperator == '+') {
                    st.push(stoi(token));
                }
                
                token = "";
                currOperator = c;
            }
        }
        
        int result = 0;
        while(!st.empty()) {
            result += st.top();
            st.pop();            
        }
        return result;
    }

评估仅由加法和乘法组成的中缀字符串表达式

Evaluate infix string expression consisting of only addition and multiplication

c++

algorithm

expression

infix-notation

infix-operator