数据结构总结分享02——栈的相关例题与应用【简单】

前情提要栈的应用非常广泛下面列举出几个最为经典的题目分别用了上篇文章中自己的类来实现以及 STL 中的std::stack来实现~使用自己的类的应用题目括号匹配说明这是一个非常经典的栈新手村入门第一题题目要求我们判断一个表达式的括号是否匹配成功。那不匹配的场景有哪些呢包括一下几种场景左 / 右括号多了即最后会剩下未匹配的括号匹配不对显然括号得跟自己一类的进行判断比如([)]这种虽然满足了一个左括号匹配一个右括号但是类型不对依然错误。拓展其实这道题还可以简化为表达式满足左右类型一定相同或只用一类括号时那此时不匹配的清空就只会是左 / 右括号多了这种场景那么此时就只需记录左右括号的个数遍历完后再看个数是否想等即可拓展一般来说编写这个程序都是来判断一个表达式的括号是否匹配但我们还可以应用到对常规代码的括号匹配的正确性判断的应用中。因为据我们都所知的代码语句除了应用之外括号也都是满足表达式一样的配对原则因此代码功能可以直接复用~程序示例#includeiostream#includestringusingnamespacestd;// 定义泛型链式栈 (LStack)templatetypenameTclassLStack{private:structNode{T data;Node*next;};Node*topPtr;// 栈顶指针public:// 构造函数LStack(){topPtrnullptr;}// 析构函数释放所有节点内存~LStack(){while(!isEmpty()){pop();}}// 入栈voidpush(T value){Node*newNodenewNode;newNode-datavalue;newNode-nexttopPtr;topPtrnewNode;}// 出栈Tpop(){if(isEmpty()){throwout_of_range(栈空无法出栈);}Node*temptopPtr;T poppedValuetemp-data;// 暂存要返回的数据topPtrtopPtr-next;deletetemp;// 释放内存returnpoppedValue;// 返回出栈的数据}// 判断栈是否为空boolisEmpty(){returntopPtrnullptr;}};// 第二部分括号匹配逻辑函数boolMatchBrackets(string str){LStackcharlStack;for(inti0;istr.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;}// 取出栈顶最近的一个左括号charblStack.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: test1endl;MatchBrackets(test1);coutendl;// 代码中常见的匹配string test2int main() { int a (1 2) * [3]; };cout测试 2: test2endl;MatchBrackets(test2);coutendl;// 右括号多余string test3{[()]} );cout测试 3: test3endl;MatchBrackets(test3);coutendl;// 左右括号不匹配 (交叉情况)string test4{ [(]) };cout测试 4: test4endl;MatchBrackets(test4);coutendl;// 左括号多余string test5((( [{}];cout测试 5: test5endl;MatchBrackets(test5);coutendl;return0;}使用STL 中的std::stack来解题本文给出两道题目来进行应用后缀表达式的计算题目说明计算后缀表达式的值ps:该题目在算法分享02——调度场算法一文中有所提及但只给出核心思路并未给出示例代码下面本文仔细说明核心思路过程非常简单直接按部就班地做就可实现1.左起依次读取表达式的一个符号2.若读入的是操作数则将其压入栈中3.若读入的是运算符则从栈中连续弹出两个元素进行相应的运算并将结果压入栈中4.若读入的是结束符则栈顶元素是计算结果题目来源洛谷 P1449 后缀表达式特别说明为表达式的结束符号.为操作数的结束符号。示例代码这两种方法实在代码书写的思路过程上有所不同但在进行的核心操作上面依旧一样方法一一层for循环内嵌判断来实现#includeiostream#includestring#includestack#includecctypeusingnamespacestd;intmain(){string hz;cinhz;stackintret;for(inti0,num0;hz[i]!;i){if(isdigit(hz[i])){numnum*10(hz[i]-0);if(!isdigit(hz[i1])){ret.push(num);num0;}}elseif(hz[i]!.){intaret.top();ret.pop();intbret.top();ret.pop();if(hz[i])ret.push(ab);elseif(hz[i]-)ret.push(b-a);elseif(hz[i]*)ret.push(a*b);elseif(hz[i]/)ret.push(b/a);}}coutret.top()endl;return0;}方法二两层for循环第一层for循环负责处理每个操作数和运算符第二层的while循环负责处理连续的数字字符来构成一个完整的操作数并处理连续的运算符来进行计算#includeiostream#includestring#includestack#includecctypeusingnamespacestd;intmain(){string hz;cinhz;stackintret;for(inti0;hz[i]!;i){intnum0;while(isdigit(hz[i])){numnum*10(hz[i]-0);i;}ret.push(num);while(!isdigit(hz[i1])hz[i1]!){i;intaret.top();ret.pop();intbret.top();ret.pop();if(hz[i])ret.push(ab);elseif(hz[i]-)ret.push(b-a);elseif(hz[i]*)ret.push(a*b);elseif(hz[i]/)ret.push(b/a);}}coutret.top()endl;return0;}中缀表达式的计算题目说明计算中缀表达式的值核心思路使用两个栈来实现遇到数字直接入运算数栈遇到运算符比较优先级如果当前运算符优先级高于栈顶运算符直接入运算符栈否则循环弹出运算符栈顶的运算符并从运算数栈弹出两个数进行计算直到当前运算符优先级高于栈顶运算符或栈空然后将当前运算符入栈遇到左括号直接入运算符栈遇到右括号循环弹出运算符栈顶的运算符并从运算数栈弹出两个数进行计算直到遇到左括号为止此时将左括号弹出但不参与计算参考题目洛谷 P10079 EX 中缀表达式说明此题更加难还涉及到幂运算以及表达式合法的判断目前就用更为简单的实现来说明栈的应用因此下面只给出含加减乘除的中缀表达式的计算且默认表达式合法。在后续讲述栈的的进阶等内容时再仔细分析~示例代码#includeiostream#includestack#includestringusingnamespacestd;// 两个栈直接设置为全局的stackintn;// 运算数栈stackcharop;// 运算符栈// 判断符号优先级的函数intpriority(charc){if(c*||c/)return2;if(c||c-)return1;return0;}// 进行具体运算的函数voidcal(){intbn.top();n.pop();intan.top();n.pop();charsop.top();op.pop();if(s)n.push(ab);elseif(s-)n.push(a-b);elseif(s*)n.push(a*b);elseif(s/)n.push(a/b);}intmain(){string mz;cinmz;for(inti0;imz.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();}coutn.top()endl;return0;}总结以上就介绍了栈应用的三个例题基本全面地熟悉了栈的特性与操作在对这些例题的熟悉掌握之后还可对列出的参考题目与题目来源中的题再进行深入思考加油数据结构的实战我们已经迈上了脚踏实地的第一步~