数据结构总结分享02——栈的相关例题与应用【简单】-程序员充电站

前情提要

栈的应用非常广泛，下面列举出几个最为经典的题目，分别用了上篇文章中自己的类来实现以及 STL 中的std::stack来实现~

使用自己的类的应用

题目：括号匹配
说明：这是一个非常经典的栈新手村入门第一题，题目要求我们判断一个表达式的括号是否匹配成功。那不匹配的场景有哪些呢？包括一下几种场景：
- 左 / 右括号多了，即最后会剩下未匹配的括号
- 匹配不对：显然括号得跟自己一类的进行判断，比如([)]这种虽然满足了一个左括号匹配一个右括号，但是类型不对，依然错误。
  - 拓展：其实这道题还可以简化为表达式满足左右类型一定相同或只用一类括号时，那此时不匹配的清空就只会是左 / 右括号多了这种场景，那么此时就只需记录左右括号的个数，遍历完后再看个数是否想等即可
拓展：一般来说编写这个程序都是来判断一个表达式的括号是否匹配，但我们还可以应用到对常规代码的括号匹配的正确性判断的应用中。因为据我们都所知的，代码语句除了应用之外，括号也都是满足表达式一样的配对原则因此代码功能可以直接复用~
程序示例：

#include<iostream>#include<string>usingnamespacestd;// 定义泛型链式栈 (LStack)template<typenameT>classLStack{private:structNode{T data;Node*next;};Node*topPtr;// 栈顶指针public:// 构造函数LStack(){topPtr=nullptr;}// 析构函数：释放所有节点内存~LStack(){while(!isEmpty()){pop();}}// 入栈voidpush(T value){Node*newNode=newNode;newNode->data=value;newNode->next=topPtr;topPtr=newNode;}// 出栈Tpop(){if(isEmpty()){throwout_of_range("栈空，无法出栈");}Node*temp=topPtr;T poppedValue=temp->data;// 暂存要返回的数据topPtr=topPtr->next;deletetemp;// 释放内存returnpoppedValue;// 返回出栈的数据}// 判断栈是否为空boolisEmpty(){returntopPtr==nullptr;}};// 第二部分：括号匹配逻辑函数boolMatchBrackets(string str){LStack<char>lStack;for(inti=0;i<str.length();i++){// 遇到左括号：压入栈if(str[i]=='{'||str[i]=='['||str[i]=='('){lStack.push(str[i]);}// 遇到右括号：进行匹配检测elseif(str[i]=='}'||str[i]==']'||str[i]==')'){// 栈为空，说明右括号多出来了if(lStack.isEmpty()){cout<<"无匹配左括号 (位置 "<<i<<" 出现多余的 '"<<str[i]<<"')\n";// 【修复4】补充缺失的分号returnfalse;}// 取出栈顶最近的一个左括号charb=lStack.pop();// 判断是否配对if(!((b=='('&&str[i]==')')||(b=='['&&str[i]==']')||(b=='{'&&str[i]=='}'))){cout<<"匹配不对 (期待与 '"<<b<<"' 匹配，但遇到了 '"<<str[i]<<"')\n";returnfalse;}}}// 字符串遍历完了，如果栈里还有东西，则说明左括号多出来了if(!lStack.isEmpty()){cout<<"有未匹配的左括号\n";returnfalse;}else{cout<<"匹配成功\n";returntrue;}}// 测试intmain(){cout<<"--- 括号匹配测试程序 ---\n\n";// 完全匹配string test1="{[()]}";cout<<"测试 1: "<<test1<<endl;MatchBrackets(test1);cout<<endl;// 代码中常见的匹配string test2="int main() { int a = (1 + 2) * [3]; }";cout<<"测试 2: "<<test2<<endl;MatchBrackets(test2);cout<<endl;// 右括号多余string test3="{[()]} )";cout<<"测试 3: "<<test3<<endl;MatchBrackets(test3);cout<<endl;// 左右括号不匹配 (交叉情况)string test4="{ [(]) }";cout<<"测试 4: "<<test4<<endl;MatchBrackets(test4);cout<<endl;// 左括号多余string test5="((( [{}]";cout<<"测试 5: "<<test5<<endl;MatchBrackets(test5);cout<<endl;return0;}

使用STL 中的`std::stack`来解题

本文给出两道题目来进行应用：

后缀表达式的计算：

题目说明：计算后缀表达式的值
ps:该题目在算法分享02——调度场算法一文中有所提及，但只给出核心思路，并未给出示例代码，下面本文仔细说明：
核心思路：过程非常简单直接，按部就班地做就可实现
1.左起依次读取表达式的一个符号
2.若读入的是操作数，则将其压入栈中
3.若读入的是运算符，则从栈中连续弹出两个元素，进行相应的运算，并将结果压入栈中
4.若读入的是结束符，则栈顶元素是计算结果
题目来源：洛谷 P1449 后缀表达式
- 特别说明：@为表达式的结束符号；.为操作数的结束符号。
示例代码（这两种方法实在代码书写的思路过程上有所不同，但在进行的核心操作上面依旧一样）
1. 方法一：一层for循环，内嵌判断来实现

#include<iostream>#include<string>#include<stack>#include<cctype>usingnamespacestd;intmain(){string hz;cin>>hz;stack<int>ret;for(inti=0,num=0;hz[i]!='@';i++){if(isdigit(hz[i])){num=num*10+(hz[i]-'0');if(!isdigit(hz[i+1])){ret.push(num);num=0;}}elseif(hz[i]!='.'){inta=ret.top();ret.pop();intb=ret.top();ret.pop();if(hz[i]=='+')ret.push(a+b);elseif(hz[i]=='-')ret.push(b-a);elseif(hz[i]=='*')ret.push(a*b);elseif(hz[i]=='/')ret.push(b/a);}}cout<<ret.top()<<endl;return0;}

方法二：两层for循环，第一层for循环负责处理每个操作数和运算符，第二层的while循环负责处理连续的数字字符来构成一个完整的操作数，并处理连续的运算符来进行计算

#include<iostream>#include<string>#include<stack>#include<cctype>usingnamespacestd;intmain(){string hz;cin>>hz;stack<int>ret;for(inti=0;hz[i]!='@';i++){intnum=0;while(isdigit(hz[i])){num=num*10+(hz[i]-'0');i++;}ret.push(num);while(!isdigit(hz[i+1])&&hz[i+1]!='@'){i++;inta=ret.top();ret.pop();intb=ret.top();ret.pop();if(hz[i]=='+')ret.push(a+b);elseif(hz[i]=='-')ret.push(b-a);elseif(hz[i]=='*')ret.push(a*b);elseif(hz[i]=='/')ret.push(b/a);}}cout<<ret.top()<<endl;return0;}

中缀表达式的计算：

题目说明：计算中缀表达式的值
核心思路：（使用两个栈来实现）：
1. 遇到数字，直接入运算数栈
2. 遇到运算符，比较优先级：
  1. 如果当前运算符优先级高于栈顶运算符，直接入运算符栈
  2. 否则，循环弹出运算符栈顶的运算符，并从运算数栈弹出两个数进行计算，直到当前运算符优先级高于栈顶运算符或栈空，然后将当前运算符入栈
3. 遇到左括号，直接入运算符栈
4. 遇到右括号，循环弹出运算符栈顶的运算符，并从运算数栈弹出两个数进行计算，直到遇到左括号为止，此时将左括号弹出但不参与计算
参考题目：洛谷 P10079 EX 中缀表达式
- 说明：此题更加难，还涉及到幂运算以及表达式合法的判断，目前就用更为简单的实现来说明栈的应用，因此下面只给出含加减乘除的中缀表达式的计算，且默认表达式合法。在后续讲述栈的的进阶等内容时再仔细分析~
示例代码：

#include<iostream>#include<stack>#include<string>usingnamespacestd;// 两个栈直接设置为全局的stack<int>n;// 运算数栈stack<char>op;// 运算符栈// 判断符号优先级的函数intpriority(charc){if(c=='*'||c=='/')return2;if(c=='+'||c=='-')return1;return0;}// 进行具体运算的函数voidcal(){intb=n.top();n.pop();inta=n.top();n.pop();chars=op.top();op.pop();if(s=='+')n.push(a+b);elseif(s=='-')n.push(a-b);elseif(s=='*')n.push(a*b);elseif(s=='/')n.push(a/b);}intmain(){string mz;cin>>mz;for(inti=0;i<mz.length();i++){if(isdigit(mz[i])){n.push(mz[i]-'0');}else{if(op.empty()){op.push(mz[i]);}elseif(mz[i]=='('||priority(mz[i])>priority(op.top())){op.push(mz[i]);}elseif(mz[i]==')'){while(op.top()!='('){cal();}op.pop();}else{while(!op.empty()&&priority(op.top())>=priority(mz[i])){cal();}op.push(mz[i]);}}}while(!op.empty()){cal();}cout<<n.top()<<endl;return0;}