数据结构 -- # 栈的应用 表达式求值 括号匹配,波兰表达式和逆波兰表达式的详解(C++)
若没有相关知识基础，可以先看看下面文章哦🤗👇
栈和队列基本概念
括号匹配
给定若干个括号，如
(((())))
发现最后出现的左括号最先被右括号匹配
那么我们可以利用栈的特性，如果遇到左括号我们就压入栈中，
如果遇到右括号，那么我们就将当前栈顶元素弹出，看是否可以匹配
匹配流程
① : 出栈匹配的过程中，如果此时栈空那么匹配失败
② : 出栈匹配的过程中，如果不相匹配那么匹配失败
③ : 如果序列扫描完毕，最后栈不为空,说明还有剩余的左括号，匹配失败
表达式求值
中缀表达式 : 运算符在中间，是我们平常使用的类型=> a + b
(逆波兰表达式)后缀表达式 : 运算符在后面 a b +
(波兰表达式)前缀表达式 : 运算符在前面 +a b
中缀转后缀手算
- 确定中缀表达式中各个运算符的运算顺序
- 以[左操作数 右操作数 运算符]的方式组合成一个新的操作数
如 a+b 变为 ab+ ，我们要将ab+作为一个新的操作数去用
需要知道的是，如果存在a+b+c+d这种样子的中缀表达式，
我们的运算可以先a+b，也可以是b+c，这样会产生不同的后缀表达式
即 中缀表达式的运算顺序不唯一，会产生不同的后缀表达式
为了方便机器的运算，我们采用**左优先**原则
只要左边的运算符能先计算，就优先计算左边的数据
后缀表达式的机算
从左往右扫描元素,扫描到操作数则压入栈
扫描到运算符则弹出两个栈顶元素,执行运算后再压入栈顶
若表达式合法，则最后栈中只会留下一个元素(最终结果)
中缀转前缀手算
使用右优先原则
按照[运算符 左操作数 右操作数]的方式组合新的操作数
前缀表达式的机算
从右往左扫描元素，其它操作仿照后缀表达式的计算即可
中缀转后缀的机算
栈的作用是保存不能确定运算顺序的运算符
- 遇到操作数，直接加入后缀表达式
- 遇到界限符，如果是左括号那么入栈，如果是右括号则依次弹出栈内运算符并加入到后缀表达式，直到碰到右括号为止
因为括号内的运算符一定是先生效的 - 遇到运算符，依次弹出栈中优先级高于等于当前运算符的所有运算符
等于也要弹出是因为要遵守左优先原则
优先级高的要弹出是因为其要先生效
中缀表达式的代码实现
如何编程计算一个中缀表达式?
需要实现中缀转为后缀，然后机算后缀表达式两个算法
- 初始化操作数栈，用来存放操作数
- 初始化运算符栈，用来存储运算符
- 扫描序列
- 如果扫描到操作数，则压入操作数栈
- 如果扫描到运算符或者界限符，则压入运算符栈
- 按照中缀转后缀的逻辑，每弹出一个运算符，就要弹出两个操作数进行相应的运算，然后再把运算结果压入操作数栈
- 最后操作数栈中留下的元素就为答案
完整代码
//这里是引入了一些常用的头文件,和一些常规操作
//第一行是因为该死的编译器不让直接用scanf
#define _CRT_SECURE_NO_WARNINGS 1
#define _USE_MATH_DEFINES //启用M_PI的定义
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
stack<int> num;//操作数栈
stack<char> op;//运算符栈
//定义符号的优先级
map<char, int> m{ {'+',1},{'-',1},{'*',2},{'/',2} };
//计算后缀表达式
void eval() {
//注意栈顶元素是第二个操作数
int x2 = num.top(); num.pop();
int x1 = num.top(); num.pop();
char p = op.top(); op.pop();
int res = 0;
if (p == '+')res = x1 + x2;
else if (p == '-')res = x1 - x2;
else if (p == '*')res = x1 * x2;
else res = x1 / x2;
num.push(res);
}
int main() {
string s;
cin >> s;
//中缀转后缀
for (int i = 0; i < s.size(); i++) {
//如果当前是数字直接加入操作数栈
//当然我们得先把它变成数字
if (isdigit(s[i])) {
int x = 0, j = i;
while (j < s.size() && isdigit(s[j])) {
x = x * 10 + s[j] - '0';
j++;
}
num.push(x);
//回退i到j-1的位置,i然后自增
i = j - 1;
}
//左括号直接入运算符栈
else if (s[i] == '(')op.push(s[i]);
//如果是右括号，那么我们就可以依次弹出碰到左括号
//内的所有运算符,弹出一个运算符就需要弹出两个操作数
//进行运算
else if (s[i] == ')') {
while (op.top() != '(')eval();
op.pop();//弹出左括号
}
//如果是运算符,那么考虑优先级
//如果栈顶的运算符优先级大于等于当前运算符的优先级
//那么弹出进行运算
else {
while (op.size() > 0 && m[op.top()] >= m[s[i]])eval();
op.push(s[i]);
}
}
//最后计算剩下的数据
while (op.size())eval();
cout << num.top() << endl;
return 0;
}
总结
根据栈的先进后出的特性，我们可以利用栈来进行括号匹配和表达式求值的问题
🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻
🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹
😇 本篇文章存在多处不足，如有修改意见，可以私信或者评论哦，还望海涵 😇
🙇本篇文章参考于Acwing,王道数据结构
原文地址：https://blog.csdn.net/mzh1213/article/details/144323799
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！