Classic application of stack -- bracket matching problem

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;
}