数据结构表达式求值c++完整代码
时间: 2023-07-25 20:45:03 浏览: 52
下面是一个基于栈的表达式求值的完整C++代码:
```c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// 判断是否为操作符
bool isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}
// 计算两个数字的结果
int compute(int num1, int num2, char op) {
switch(op) {
case '+': return num1 + num2;
case '-': return num1 - num2;
case '*': return num1 * num2;
case '/': return num1 / num2;
}
return 0;
}
// 表达式求值函数
int evaluate(string expr) {
stack<int> nums; // 存储数字
stack<char> ops; // 存储操作符
for (int i = 0; i < expr.length(); i++) {
char ch = expr[i];
if (ch == ' ') continue; // 忽略空格
// 如果是数字
if (isdigit(ch)) {
int num = 0;
while (i < expr.length() && isdigit(expr[i])) {
num = num * 10 + (expr[i] - '0');
i++;
}
i--;
nums.push(num);
}
// 如果是操作符
else if (isOperator(ch)) {
// 如果当前操作符优先级小于等于栈顶操作符优先级,先计算栈顶的操作
while (!ops.empty() && ops.top() != '(' && ((ch != '*' && ch != '/') || (ops.top() == '+' || ops.top() == '-'))) {
int num2 = nums.top();
nums.pop();
int num1 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
int result = compute(num1, num2, op);
nums.push(result);
}
ops.push(ch);
}
// 如果是左括号
else if (ch == '(') {
ops.push(ch);
}
// 如果是右括号,计算括号内的表达式
else if (ch == ')') {
while (ops.top() != '(') {
int num2 = nums.top();
nums.pop();
int num1 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
int result = compute(num1, num2, op);
nums.push(result);
}
ops.pop();
}
}
// 计算剩余的表达式
while (!ops.empty()) {
int num2 = nums.top();
nums.pop();
int num1 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
int result = compute(num1, num2, op);
nums.push(result);
}
return nums.top();
}
int main() {
string expr = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
int result = evaluate(expr);
cout << "Result: " << result << endl;
return 0;
}
```
在这个代码中,我们使用了两个栈来分别存储数字和操作符,逐个扫描表达式,根据不同的情况进行处理。当遇到数字时,我们将其转换为整数并存入数字栈中;当遇到操作符时,我们需要根据其优先级和栈顶操作符的优先级来确定是否需要先计算栈顶操作符,然后将其存入操作符栈中;当遇到左括号时,我们将其存入操作符栈中;当遇到右括号时,我们需要先计算括号内的表达式,然后将左括号从操作符栈中弹出。最后,我们需要计算剩余的表达式,直到数字栈中只剩下一个数字,即为表达式的结果。