利用c++的栈进行表达式求值
时间: 2023-09-09 18:10:36 浏览: 59
可以使用栈来实现表达式求值,具体步骤如下:
1.定义一个操作符栈和一个操作数栈。
2.从左到右扫描表达式,遇到数字就入操作数栈,遇到操作符就与操作符栈栈顶元素比较优先级,如果当前操作符优先级较低,则将操作符栈栈顶元素弹出做运算,同时将结果入操作数栈,直到当前操作符优先级大于栈顶元素或者操作符栈为空,然后将当前操作符入操作符栈。
3.当表达式扫描完成后,依次将操作符栈中的操作符弹出做运算,同时将结果入操作数栈,直到操作符栈为空。
4.最后操作数栈中剩下的唯一元素即为表达式的值。
下面是一个简单的C++代码实现:
```c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int getPriority(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
} else {
return 0;
}
}
int calculate(int a, int b, char op) {
if (op == '+') {
return a + b;
} else if (op == '-') {
return a - b;
} else if (op == '*') {
return a * b;
} else {
return a / b;
}
}
int evaluate(string expression) {
stack<char> opStack;
stack<int> numStack;
for (int i = 0; i < expression.length(); i++) {
char ch = expression[i];
if (isdigit(ch)) {
int num = ch - '0';
while (i + 1 < expression.length() && isdigit(expression[i + 1])) {
num = num * 10 + (expression[i + 1] - '0');
i++;
}
numStack.push(num);
} else if (ch == '(') {
opStack.push(ch);
} else if (ch == ')') {
while (opStack.top() != '(') {
char op = opStack.top();
opStack.pop();
int b = numStack.top();
numStack.pop();
int a = numStack.top();
numStack.pop();
numStack.push(calculate(a, b, op));
}
opStack.pop();
} else {
while (!opStack.empty() && opStack.top() != '(' && getPriority(ch) <= getPriority(opStack.top())) {
char op = opStack.top();
opStack.pop();
int b = numStack.top();
numStack.pop();
int a = numStack.top();
numStack.pop();
numStack.push(calculate(a, b, op));
}
opStack.push(ch);
}
}
while (!opStack.empty()) {
char op = opStack.top();
opStack.pop();
int b = numStack.top();
numStack.pop();
int a = numStack.top();
numStack.pop();
numStack.push(calculate(a, b, op));
}
return numStack.top();
}
int main() {
string expression = "3+4*(6-2)/3";
int result = evaluate(expression);
cout << "表达式 " << expression << " 的计算结果为:" << result << endl;
return 0;
}
```
这里的 evaluate 函数接受一个字符串表达式作为参数,返回表达式的值。在函数中,我们依次扫描表达式中的每个字符,根据字符的类型决定是将数字入操作数栈还是将操作符入操作符栈,同时进行相应的运算。最后操作数栈中的唯一元素即为表达式的值。