栈的经典应用—括号匹配问题

括号匹配问题算是栈应用中比较经典的问题了。

给定一个只包括 (，)，{ ，}，[，] 的字符串，判断字符串是否有效。
有效字符串需满足：
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;
}