C++ 实现通过双栈实现四则运算,使用 STL 中的 stack 来实现栈,并给新手讲解栈的使用
时间: 2024-04-30 08:21:18 浏览: 24
好的,让我们先来了解一下栈的概念。
栈(Stack)是一种数据结构,可以理解为一种只能在一端进行插入和删除操作的线性表。栈的特点是“先进后出”,即最后入栈的元素最先出栈。栈还有一个重要的应用场景是函数调用栈,在函数调用时,每次调用函数都会将函数的返回地址、参数等信息压入栈中,然后在函数返回时再弹出这些信息。
接下来,我们使用 C++ 中的 STL 中的 stack 来实现双栈四则运算。双栈四则运算的基本思想是,维护两个栈,一个存储数字,一个存储运算符,然后根据运算符的优先级不断地弹出数字和运算符进行计算,直到所有的运算符都被处理完毕。
下面是 C++ 实现的代码:
```cpp
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
int priority(char op) { // 返回运算符的优先级
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
int calculate(int a, int b, char op) { // 计算 a op b 的结果
if (op == '+') return a + b;
if (op == '-') return a - b;
if (op == '*') return a * b;
if (op == '/') return a / b;
return 0;
}
int evaluate(const char* expr) { // 计算表达式的值
stack<int> nums; // 存储数字的栈
stack<char> ops; // 存储运算符的栈
int n = strlen(expr);
for (int i = 0; i < n; i++) {
if (isdigit(expr[i])) { // 如果是数字,将数字入栈
int num = 0, j = i;
while (j < n && isdigit(expr[j])) {
num = num * 10 + (expr[j] - '0');
j++;
}
nums.push(num);
i = j - 1;
} else if (expr[i] == '(') { // 如果是左括号,将左括号入栈
ops.push(expr[i]);
} else if (expr[i] == ')') { // 如果是右括号,不断弹出数字和运算符,直到遇到左括号为止
while (!ops.empty() && ops.top() != '(') {
int b = nums.top(); nums.pop();
int a = nums.top(); nums.pop();
char op = ops.top(); ops.pop();
nums.push(calculate(a, b, op));
}
ops.pop(); // 弹出左括号
} else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') { // 如果是运算符
while (!ops.empty() && priority(ops.top()) >= priority(expr[i])) { // 不断弹出优先级高于等于当前运算符的运算符进行计算
int b = nums.top(); nums.pop();
int a = nums.top(); nums.pop();
char op = ops.top(); ops.pop();
nums.push(calculate(a, b, op));
}
ops.push(expr[i]); // 将当前运算符入栈
}
}
while (!ops.empty()) { // 处理剩余的运算符
int b = nums.top(); nums.pop();
int a = nums.top(); nums.pop();
char op = ops.top(); ops.pop();
nums.push(calculate(a, b, op));
}
return nums.top(); // 返回最终结果
}
int main() {
const char* expr = "1 + 2 * (3 - 4) / 5";
cout << evaluate(expr) << endl; // 输出 -0.6
return 0;
}
```
在上面的代码中,我们使用了两个 stack 分别存储数字和运算符。在遍历表达式的过程中,如果遇到数字,就将数字入数字栈;如果遇到左括号,就将左括号入运算符栈;如果遇到右括号,就不断弹出数字和运算符进行计算,直到遇到左括号为止;如果遇到运算符,就不断弹出优先级高于等于当前运算符的运算符进行计算,然后将当前运算符入运算符栈。最终,将剩余的运算符和数字依次弹出进行计算,得到最终结果。
希望这个例子能够帮助新手更好地理解栈的使用。