当前位置:网站首页>栈的经典应用—括号匹配问题
栈的经典应用—括号匹配问题
2022-07-06 09:27:00 【帅帅气气的黑猫警长】
括号匹配问题算是栈应用中比较经典的问题了。
给定一个只包括 (
,)
,{
,}
,[
,]
的字符串,判断字符串是否有效。
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
顺序栈核心代码和算法
typedef struct { //顺序栈结构体
char data[MAXSIZE];
int top;
}sqstack;
void initstack(sqstack &s) //初始化顺序栈
bool push(sqstack &s,char e) //push操作
bool pop(sqstack &s,char &e) //pop操作
bool stackempty(sqstack s) //判空
bool chack(char str[],int length) //匹配代码
{
sqstack s;
initstack(s);
cout<<"initstack"<<endl;
for(int i=0;i<length;i++)
{
//cout<<str[i]<<endl;
if(str[i]=='(' ||str[i]=='[' ||str[i]=='{') //把(,[,{左半部分push到栈
{
push(s,str[i]);
}
else {
if(stackempty(s)) //先判断栈中还有没有待配对元素
return 0;
char topelem;
pop(s,topelem); //pop出栈顶元素与之配对
//cout<<topelem<<" "<<str[i]<<endl;
if(str[i]==')'&&topelem!='(')
return 0;
if(str[i]==']'&&topelem!='[')
return 0;
if(str[i]=='}'&&topelem!='{')
return 0;
}
}
return stackempty(s); //最后匹配完看栈中有无剩余
}
顺序栈实现完整代码
#include <iostream>
#define MAXSIZE 20
using namespace std;
typedef struct {
char data[MAXSIZE];
int top;
}sqstack;
void initstack(sqstack &s) //初始化
{
s.top=-1;
}
bool push(sqstack &s,char e) //push操作
{
if(s.top==MAXSIZE-1)
return 0;
s.top=s.top+1;
s.data[s.top]=e;
return 1;
}
bool pop(sqstack &s,char &e) //pop操作
{
if(s.top==-1)
return 0;
e=s.data[s.top];
s.top=s.top-1;
return 1;
}
bool stackempty(sqstack s) //判空操作
{
if(s.top==-1)
return 1;
else return 0;
}
bool chack(char str[],int length) //匹配操作
{
sqstack s;
initstack(s);
cout<<"initstack"<<endl;
for(int i=0;i<length;i++)
{
//cout<<str[i]<<endl;
if(str[i]=='(' ||str[i]=='[' ||str[i]=='{')
{
push(s,str[i]);
}
else {
if(stackempty(s))
return 0;
char topelem;
pop(s,topelem);
//cout<<topelem<<" "<<str[i]<<endl;
if(str[i]==')'&&topelem!='(')
return 0;
if(str[i]==']'&&topelem!='[')
return 0;
if(str[i]=='}'&&topelem!='{')
return 0;
}
}
return stackempty(s);
}
int main() {
char str[]={'{','[','(',')','(',')',']','}'};
int length=sizeof(str)/sizeof(str[0]); //此处为判断str数组长度
cout<<length<<endl;
if(chack(str,length))
cout<<"yes"<<endl;
else cout<<"no"<<endl;
cout <<"over\n";
return 0;
}
链栈实现完整代码
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct lnode{ //链栈结构体
char data;
struct lnode *next;
}lnode,*linkstack;
bool initstack(linkstack &s) //初始化链栈(表)
{
s=(lnode*)malloc(sizeof(lnode));
if(s==NULL)
return 0;
s->next=NULL;
return 1;
}
bool push(linkstack &s,char e) //push(类似链表头插)
{
lnode *p;
p=(lnode*)malloc(sizeof(lnode));
if(p==NULL)
return 0;
p->data=e;
p->next=s->next;
s->next=p;
return 1;
}
bool pop(linkstack &s,char &e) //pop(类似链表删除)
{
if(s->next==NULL)
return 0;
lnode *p;
p=s->next;
e=s->next->data;
s->next=p->next;
free(p);
return 1;
}
bool stackempty(linkstack s) //判空
{
if(s->next==NULL)
return 1;
else return 0;
}
bool chack(char str[],int length) //匹配算法
{
linkstack s;
initstack(s);
cout<<"initstack"<<endl;
for(int i=0;i<length;i++)
{
//cout<<str[i]<<endl;
if(str[i]=='(' ||str[i]=='[' ||str[i]=='{')
{
push(s,str[i]);
}
else {
if(stackempty(s))
return 0;
char topelem;
pop(s,topelem);
cout<<topelem<<" "<<str[i]<<endl;
if(str[i]==')'&&topelem!='(')
return 0;
if(str[i]==']'&&topelem!='[')
return 0;
if(str[i]=='}'&&topelem!='{')
return 0;
}
}
return stackempty(s);
}
int main() {
char str[]={'{','[','(',')','(',')',']','}'};
int length=sizeof(str)/sizeof(str[0]);
cout<<length<<endl;
if(chack(str,length))
cout<<"yes"<<endl;
else cout<<"no"<<endl;
cout <<"over\n";
return 0;
}
边栏推荐
- Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
- MySQL grants the user the operation permission of the specified content
- Matlab comprehensive exercise: application in signal and system
- Gartner: five suggestions on best practices for zero trust network access
- [exercise-1] (UVA 673) parentheses balance/ balanced brackets (stack)
- Interval sum ----- discretization
- Research Report of peripheral venous catheter (pivc) industry - market status analysis and development prospect prediction
- Frida hook so layer, protobuf data analysis
- [exercise-7] crossover answers
- [exercise-5] (UVA 839) not so mobile (balance)
猜你喜欢
程序员的你,有哪些炫技的代码写法?
Optimization method of path problem before dynamic planning
信息安全-威胁检测引擎-常见规则引擎底座性能比较
Frida hook so layer, protobuf data analysis
Matlab comprehensive exercise: application in signal and system
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
7-1 懂的都懂 (20 分)
差分(一维,二维,三维) 蓝桥杯三体攻击
Borg Maze (BFS+最小生成树)(解题报告)
C语言数组的概念
随机推荐
滲透測試 ( 1 ) --- 必備 工具、導航
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
MySQL授予用户指定内容的操作权限
【高老师软件需求分析】20级云班课习题答案合集
【练习-7】Crossword Answers
Research Report on market supply and demand and strategy of China's earth drilling industry
用C语言写网页游戏
Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
1010 things that college students majoring in it must do before graduation
Ball Dropping
【练习-11】4 Values whose Sum is 0(和为0的4个值)
Research Report on surgical fluid treatment industry - market status analysis and development prospect prediction
差分(一维,二维,三维) 蓝桥杯三体攻击
Common configuration files of SSM framework
HDU-6025-Coprime Sequence(女生赛)
Auto.js入门
Penetration test (1) -- necessary tools, navigation
Nodejs+vue网上鲜花店销售信息系统express+mysql
【练习-7】(Uva 10976)Fractions Again?!(分数拆分)
Research Report on market supply and demand and strategy of geosynthetics industry in China