数据结构表达式求值c++
时间: 2023-07-25 09:07:44 浏览: 45
可以使用栈来实现表达式求值。具体实现步骤如下:
1. 定义两个栈,一个用于存放操作数,一个用于存放运算符。
2. 遍历表达式中的每个字符,如果是数字则将其转化为整数并入操作数栈中。如果是运算符,则与运算符栈顶元素进行比较,如果当前运算符优先级高于栈顶运算符,则将其入栈,否则弹出栈顶运算符进行计算,直到当前运算符可以入栈。
3. 当遍历完表达式后,如果运算符栈不为空,则依次弹出运算符进行计算,直到运算符栈为空,此时操作数栈中的唯一元素即为表达式的值。
以下是一个简单的C++代码实现:
```c++
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
int priority(char op) {
if (op == '*' || op == '/') return 2;
else if (op == '+' || op == '-') return 1;
else return 0; // 左括号
}
int evaluate(char* expr) {
stack<int> nums;
stack<char> ops;
int len = strlen(expr);
for (int i = 0; i < len; i++) {
if (isdigit(expr[i])) {
int num = 0;
while (i < len && isdigit(expr[i])) {
num = num * 10 + (expr[i] - '0');
i++;
}
nums.push(num);
i--;
} else if (expr[i] == '(') {
ops.push(expr[i]);
} else if (expr[i] == ')') {
while (ops.top() != '(') {
int num2 = nums.top();
nums.pop();
int num1 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
int result;
if (op == '+') result = num1 + num2;
else if (op == '-') result = num1 - num2;
else if (op == '*') result = num1 * num2;
else result = num1 / num2;
nums.push(result);
}
ops.pop(); // 弹出左括号
} else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
while (!ops.empty() && priority(expr[i]) <= priority(ops.top())) {
int num2 = nums.top();
nums.pop();
int num1 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
int result;
if (op == '+') result = num1 + num2;
else if (op == '-') result = num1 - num2;
else if (op == '*') result = num1 * num2;
else result = num1 / num2;
nums.push(result);
}
ops.push(expr[i]);
}
}
while (!ops.empty()) {
int num2 = nums.top();
nums.pop();
int num1 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
int result;
if (op == '+') result = num1 + num2;
else if (op == '-') result = num1 - num2;
else if (op == '*') result = num1 * num2;
else result = num1 / num2;
nums.push(result);
}
return nums.top();
}
int main() {
char expr[100];
cout << "请输入表达式(不含空格):";
cin >> expr;
int result = evaluate(expr);
cout << "计算结果为:" << result << endl;
return 0;
}
```
注意:以上代码只适用于不含空格的表达式。如果需要支持含空格的表达式,则需要对代码进行相应修改。