当前位置:网站首页>Classic application of stack -- bracket matching problem
Classic application of stack -- bracket matching problem
2022-07-06 16:13:00 【Handsome black cat Sheriff】
Bracket matching is a classic problem in stack applications .
Given one only includes (
,)
,{
,}
,[
,]
String , Determines whether the string is valid .
Valid string needs to meet :
1、 Opening parentheses must be closed with closing parentheses of the same type .
2、 The left parenthesis must be closed in the correct order .
Note that an empty string can be considered a valid string .
Sequence stack core code and algorithm
typedef struct { // Sequential stack structure
char data[MAXSIZE];
int top;
}sqstack;
void initstack(sqstack &s) // Initialization sequence stack
bool push(sqstack &s,char e) //push operation
bool pop(sqstack &s,char &e) //pop operation
bool stackempty(sqstack s) // Sentenced to empty
bool chack(char str[],int length) // Match code
{
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]=='{') // hold (,[,{ The left half push To the stack
{
push(s,str[i]);
}
else {
if(stackempty(s)) // First determine whether there are elements to be paired in the stack
return 0;
char topelem;
pop(s,topelem); //pop The element at the top of the stack is paired with it
//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); // Finally, after matching, check whether there is any remaining in the stack
}
Sequence stack to achieve complete code
#include <iostream>
#define MAXSIZE 20
using namespace std;
typedef struct {
char data[MAXSIZE];
int top;
}sqstack;
void initstack(sqstack &s) // initialization
{
s.top=-1;
}
bool push(sqstack &s,char e) //push operation
{
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 operation
{
if(s.top==-1)
return 0;
e=s.data[s.top];
s.top=s.top-1;
return 1;
}
bool stackempty(sqstack s) // Empty operation
{
if(s.top==-1)
return 1;
else return 0;
}
bool chack(char str[],int length) // Match operation
{
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]); // Here is judgment str The length of the array
cout<<length<<endl;
if(chack(str,length))
cout<<"yes"<<endl;
else cout<<"no"<<endl;
cout <<"over\n";
return 0;
}
Chain stack to achieve complete code
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct lnode{ // Chain stack structure
char data;
struct lnode *next;
}lnode,*linkstack;
bool initstack(linkstack &s) // Initializing the chain stack ( surface )
{
s=(lnode*)malloc(sizeof(lnode));
if(s==NULL)
return 0;
s->next=NULL;
return 1;
}
bool push(linkstack &s,char e) //push( Similar to chain meter insertion )
{
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( Similar to list deletion )
{
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) // Sentenced to empty
{
if(s->next==NULL)
return 1;
else return 0;
}
bool chack(char str[],int length) // matching algorithm
{
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;
}
边栏推荐
- b站 实时弹幕和历史弹幕 Protobuf 格式解析
- Interesting drink
- Truck History
- 409. Longest palindrome
- Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
- 1323. Maximum number of 6 and 9
- frida hook so层、protobuf 数据解析
- [teacher Gao UML software modeling foundation] collection of exercises and answers for level 20 cloud class
- 【练习-2】(Uva 712) S-Trees (S树)
- Understand what is a programming language in a popular way
猜你喜欢
window11 conda安装pytorch过程中遇到的一些问题
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
C language is the watershed between low-level and high-level
Borg maze (bfs+ minimum spanning tree) (problem solving report)
渗透测试 ( 4 ) --- Meterpreter 命令详解
(POJ - 3579) median (two points)
Pytorch extract skeleton (differentiable)
2027. Minimum number of operations to convert strings
409. Longest palindrome
Candy delivery (Mathematics)
随机推荐
Pyside6 signal, slot
Opencv learning log 27 -- chip positioning
Programmers, what are your skills in code writing?
[teacher Gao UML software modeling foundation] collection of exercises and answers for level 20 cloud class
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
Truck History
Radar equipment (greedy)
QNetworkAccessManager实现ftp功能总结
力扣——第298场周赛
C language learning notes
Information security - Analysis of security orchestration automation and response (soar) technology
[exercise-9] Zombie's Treasury test
滲透測試 ( 1 ) --- 必備 工具、導航
2027. Minimum number of operations to convert strings
Openwrt build Hello ipk
PySide6 信号、槽
Auto.js入门
Suffix expression (greed + thinking)
Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures
Socket communication