中缀表达式求值c++栈
时间: 2023-10-31 11:05:11 浏览: 58
中缀表达式求值可以通过栈来实现。具体步骤如下:
1. 定义两个栈,一个用来存储操作数,一个用来存储操作符。
2. 从左到右遍历中缀表达式的每个元素。
3. 如果当前元素是数字,则将其压入操作数栈中。
4. 如果当前元素是操作符,则进行如下操作:
- 如果操作符栈为空或者栈顶元素为左括号,则将当前操作符压入操作符栈中。
- 如果当前操作符的优先级大于栈顶操作符的优先级,则将当前操作符压入操作符栈中。
- 否则,将操作符栈顶元素弹出,直到当前操作符的优先级大于栈顶操作符的优先级,然后将当前操作符压入操作符栈中。
5. 如果当前元素是左括号,则将其压入操作符栈中。
6. 如果当前元素是右括号,则进行如下操作:
- 重复弹出操作符栈顶元素,直到遇到左括号为止。左括号不需要入栈,也不需要输出。
- 将弹出的操作符和操作数进行计算,并将计算结果压入操作数栈中。
7. 遍历完中缀表达式后,如果操作符栈不为空,则重复弹出操作符和操作数进行计算,直到操作符栈为空。
下面是一个示例代码:
```c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int priority(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
} else {
return 0;
}
}
int calculate(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default:
return 0;
}
}
int evaluate(string expr) {
stack<int> operands;
stack<char> operators;
for (int i = 0; i < expr.length(); i++) {
char c = expr[i];
if (isdigit(c)) {
int num = c - '0';
while (i + 1 < expr.length() && isdigit(expr[i + 1])) {
num = num * 10 + (expr[i + 1] - '0');
i++;
}
operands.push(num);
} else if (c == '(') {
operators.push(c);
} else if (c == ')') {
while (!operators.empty() && operators.top() ! '(') {
char op = operators.top();
operators.pop();
int b = operands.top();
operands.pop();
int a = operands.top();
operands.pop();
operands.push(calculate(a, b, op));
}
if (!operators.empty()) {
operators.pop(); // 弹出左括号
}
} else {
while (!operators.empty() && priority(c) <= priority(operators.top())) {
char op = operators.top();
operators.pop();
int b = operands.top();
operands.pop();
int a = operands.top();
operands.pop();
operands.push(calculate(a, b, op));
}
operators.push(c); }
}
while (!operators.empty()) {
char op = operators.top();
operators.pop();
int b = operands.top();
operands.pop();
int a = operands.top();
operands.pop();
operands.push(calculate(a, b, op));
}
return operands.top();
}
int main() {
string expr = "3+4*5-(6+7)";
int result = evaluate(expr);
cout << result << endl; // 输出: 10
return 0;
}
```