-3

如何评估仅由+and*运算符组成的中缀字符串表达式。（无括号）。

示例 1：

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

示例 2：

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

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

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();
}

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

4

2 回答 2

4

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

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

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

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

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

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

在您的情况下，您需要匹配功能一个前瞻符号，因此，下一个标记。您将在此处找到这样的示例。在那里你可以找到一个编译器，它有一个前端（扫描器、解析器）和 2 个不同的代码生成器作为后端。您的任务不需要代码生成器，您可以在减少时直接评估。

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

他们基本上为语法中的每个生产/终端/非终端编写一个函数并评估标记并调用其他终端或非终端的函数。有趣的方法，对您的用例来说并不困难。

希望这有所帮助 。. .

于 2020-07-24T05:58:34.267 回答
0 
 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;
    }
于 2020-10-16T19:02:28.000 回答