如何计算仅由+和*运算符组成的中缀字符串表达式。(无括号(。
示例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();
}
注意：不希望使用任何非标准库。理想情况下不使用任何库。
是的，您只需要一个堆栈。您可以将标准方法与shift-reduce解析器一起使用。就你的情况和简单的语法而言，这可能已经有点太多了。但我无论如何都会描述它。
秘密是使用"；解析堆栈"；。所以只有一个堆栈。不是运算符和操作数堆栈。在那里，您将使用属性化令牌。令牌有一个类型，如ADD、MULT、NUMBER和一个关联的属性。属性通常是并集或结构。对于ADD和MULT，它将为空，并且将包含NUMBER的值。
通常具有getNextToken功能的扫描仪将生成您的代币。在您的情况下，非常简单，只有这3个令牌。
然后，在循环中，您将始终执行以下操作。
- 始终将新令牌推送到解析堆栈
- 尝试将堆栈的顶部与语法的生成相匹配(以及前瞻性标记(
- 减少堆栈(移除匹配的元素(，计算表达式，并将结果放入解析堆栈
所以，总是：移位、匹配、减少
在您的情况下，匹配函数需要一个先行符号，因此需要下一个标记。你会在这里找到这样一个例子。在那里你可以找到一个编译器，有一个前端(Scanner，Parser(和两个不同的代码生成器作为后端。您的任务不需要代码生成器，您可以在减少的同时直接进行评估。
但是，对于这样一个简单的语法，你根本不需要堆栈。crafting A Compiler with C就是一个很好的例子。我的这本书是1991年的，当然内容仍然有效。
他们基本上为语法中的每个生产/终端/非终端编写一个函数，并评估令牌并调用其他终端或非终端的函数。有趣的方法，对您的用例来说并不困难。
希望这能有所帮助。
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;
}