436 字
1 分钟
利用栈实现括号检查匹配
利用栈实现括号匹配检查
本文的目的是实现检查括号的匹配性。包含（），【】，{}。
即括号是否正确闭合。🤔
比如{(A+B)+(C+D)}就是闭合的，而{（x+y)*(z)则缺少一个右括号，是不闭合的！
检查括号通常是编译器的工作，所以我们来帮他实现一下吧。
实现要求？
- 首先肯定要满足左边括号的数量等于右括号的数量。但是显然这肯定不够🤔
- 右括号要有左括号对应 比如
)(就是数量满足但是不匹配 - 可以出现右括号的条件是：与其对应的左括号之后出现的所有括号都已经匹配才行！比如
[(])就不行。换句话说就是靠右的左括号要先关闭(即就近关闭，左括号会选择一个最近的右括号来匹配），比如[()()]
解决方案
我们可以从左到右扫描表达式，如果碰到一个开放的左括号，就把他填入栈中。
如果我们碰到一个关闭的括号，它就是列表中最后一个括号所匹配的括号！。如果不一致，或者由于列表是空的但是却有关闭括号！我们就可以说括号不匹配！
否则我们就将被匹配上的括号从栈中弹出。
我们来模拟一下过程吧，样本采用[()()]
当前list：empty开始读取括号··········当前list:[开始读取括号··········当前list:[(开始读取括号··········匹配成功，弹出最近的括号当前括号:[接着就是重复工作，扫到最后列表会变成空。（ps:跟消消乐差不多😎）这里的列表总是满足后进去的先出来，栈正好满足这一特性，所以选他做数据容器相当合适！
完整代码
#include<iostream>#include<stack>#include<cstring>using namespace std;bool Check(const char* exp){ stack<char> S; int n=strlen(exp); for(int i=0;i<n;i++){ char c=exp[i]; if(c=='{'||c=='('||c=='['){ S.push(c); } else if(c=='}'||c==']'||c==')'){ if(S.empty()) return false;//先检查一下是否直接就是右括号！ char d=S.top(); if( (c==')'&&d=='(')|| (c=='}'&&d=='{')|| (c==']'&&d=='[') ){ S.pop(); } else{ //类型不匹配 return false; } } } return S.empty();}int main(){ char exp[1000]; cout<<"please input text： "; cin.getline(exp,1000); if(Check(exp)){ cout<<"success!"; } else{ cout<<"defeat!"; } return 0;}
利用栈实现括号检查匹配
https://fatdog.20060113.xyz/posts/stack-bracket/ 部分信息可能已经过时