C语言数据结构--栈括号匹配算法

雨点打透心脏的1/2处 2024-03-22 10:44 64阅读 0赞

今天这一期使用栈来完成括号匹配算法

① 栈结构

typedef struct
    {
        char elem[Stack_Size];
        int  top;
    }SeqStack;

② 初始化栈

void InitStack(SeqStack* S)  //初始化栈
    {
        S->top = -1;
    }

③ 入栈

int Push(SeqStack* S, char x)  //入栈
    {
        if (S->top == Stack_Size - 1) return False;    //如果栈顶指针等于栈的最大容量减一，说明栈已满，返回False
        S->top++;                                      //否则，将栈顶指针加一
        S->elem[S->top] = x;                           //将x赋值给栈顶元素
        return True;
    }

④ 出栈

int Pop(SeqStack* S, char* x)  //出栈
    {
        if (S->top == -1) return False;     //如果栈顶指针为-1，说明栈为空，返回False
        else
        {
            *x = S->elem[S->top];          //否则，将栈顶元素赋值给x指向的变量
            S->top--;                     //将栈顶指针减一
            return True;
        }
    }

⑤ 判断栈是否为空

int IsEmpty(SeqStack* S)   //判断栈是否为空
    {
        if (S->top == -1)     //如果栈顶指针为-1，说明栈为空
        {
            return True;    //返回True
        }
        else                 //否则，栈不为空
        {
            return False;   //返回False
        }
    }

⑤ 括号匹配

int BracketMatch(char *x)   //括号匹配
    {
        SeqStack S;                      //定义一个顺序栈S
        InitStack(&S);                   //初始化栈S
        int len = strlen(x);        //获取字符串x的长度
        for(int i = 0;i < len;i++)       //遍历字符串x中的每个字符
        {
            if(x[i]=='['||x[i]=='{'||x[i]=='(')           //如果字符是左括号
            {
                Push(&S,x[i]);                   //将左括号入栈
            }
            else                              //如果字符是右括号
            {
                if(IsEmpty(&S))              //如果栈为空，说明没有匹配的左括号，返回False
                    return False;
    
                char ch;                     //定义一个字符变量ch
                Pop(&S,&ch);                 //将栈顶元素出栈，并赋值给ch
                if(x[i]==')' && ch!='(')     //如果右括号是')'，但栈顶元素不是'('，说明不匹配，返回False
                    return False;
                if(x[i]==']' && ch!='[')     //如果右括号是']'，但栈顶元素不是'['，说明不匹配，返回False
                    return False;
                if(x[i]=='}' && ch!='{')    //如果右括号是'}'，但栈顶元素不是'{'，说明不匹配，返回False
                    return False;
    
            }
        }
        return IsEmpty(&S);       //遍历完字符串后，如果栈为空，说明所有括号都匹配，返回True；否则，返回False
    }

完整代码：

#include "stdio.h"
    #include <string.h>
    #define False 0
    #define True 1
    #define Stack_Size 50
    
    typedef struct
    {
        char elem[Stack_Size];
        int  top;
    }SeqStack;
    
    void InitStack(SeqStack* S)  //初始化栈
    {
        S->top = -1;
    }
    
    int Push(SeqStack* S, char x)  //入栈
    {
        if (S->top == Stack_Size - 1) return False;    //如果栈顶指针等于栈的最大容量减一，说明栈已满，返回False
        S->top++;                                      //否则，将栈顶指针加一
        S->elem[S->top] = x;                           //将x赋值给栈顶元素
        return True;
    }
    
    int Pop(SeqStack* S, char* x)  //出栈
    {
        if (S->top == -1) return False;     //如果栈顶指针为-1，说明栈为空，返回False
        else
        {
            *x = S->elem[S->top];          //否则，将栈顶元素赋值给x指向的变量
            S->top--;                     //将栈顶指针减一
            return True;
        }
    }
    
    int IsEmpty(SeqStack* S)   //判断栈是否为空
    {
        if (S->top == -1)     //如果栈顶指针为-1，说明栈为空
        {
            return True;    //返回True
        }
        else                 //否则，栈不为空
        {
            return False;   //返回False
        }
    }
    
    int GetPop(SeqStack* S, char* x)       //获取栈顶元素
    {
        if (S->top == -1) return False;   //如果栈顶指针为-1，说明栈为空，返回False
        else
        {
            *x = S->elem[S->top];        //否则，将栈顶元素赋值给x指向的变量
            return (True);               //返回True
        }
    }
    void Stack_display(SeqStack *S) //显示栈元素
    {
        if (S->top == -1)                       //如果栈顶指针为-1，说明栈为空
        {
            printf("栈为空\n");          //打印提示信息
            return; //结束函数
        }
    
        printf("栈中的元素: ");                //打印提示信息
        for (int i = S->top; i >= 0; i--)           //从栈顶到栈底遍历栈中的元素
        {
            printf("%c ", S->elem[i]);       //打印每个元素，用空格隔开
        }
        printf("\n");
    }
    
    int BracketMatch(char *x)   //括号匹配
    {
        SeqStack S;                      //定义一个顺序栈S
        InitStack(&S);                   //初始化栈S
        int len = strlen(x);        //获取字符串x的长度
        for(int i = 0;i < len;i++)       //遍历字符串x中的每个字符
        {
            if(x[i]=='['||x[i]=='{'||x[i]=='(')                //如果字符是左括号
            {
                Push(&S,x[i]);                              //将左括号入栈
            }
            else                             //如果字符是右括号
            {
                if(IsEmpty(&S))             //如果栈为空，说明没有匹配的左括号，返回False
                    return False;
    
                char ch;                    //定义一个字符变量ch
                Pop(&S,&ch);             //将栈顶元素出栈，并赋值给ch
                if(x[i]==')' && ch!='(')    //如果右括号是')'，但栈顶元素不是'('，说明不匹配，返回False
                    return False;
                if(x[i]==']' && ch!='[')    //如果右括号是']'，但栈顶元素不是'['，说明不匹配，返回False
                    return False;
                if(x[i]=='}' && ch!='{')   //如果右括号是'}'，但栈顶元素不是'{'，说明不匹配，返回False
                    return False;
    
            }
        }
        return IsEmpty(&S);       //遍历完字符串后，如果栈为空，说明所有括号都匹配，返回True；否则，返回False
    }
    
    int main()
    {
        SeqStack S;
        char str[]={'(','{','[',']','}',')'};   //可以更换成其他括号序列
        char str1[]={'(','}'};                  //可以更换成其他括号序列
        InitStack(&S);
        if(BracketMatch(&str))
        {
            printf("匹配成功！");
        }
        else
        {
            printf("匹配失败！");
        }
        return 0;
    }

结果：

（1）括号序列为char str\[\]=\{'(','\{','\[','\]','\}',')'\};

![c2afc196b7b44e199431882cd4cc11c5.png][]

![477b595483004d89b2c42bb17d80dd91.png][]

（2）括号序列为char str1\[\]=\{'\{','(','\}','\]'\};

![3065e72f446e44e8a3114db76038206f.png][]

![eab2f423621647208017a26c74f61490.png][]

[c2afc196b7b44e199431882cd4cc11c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d30ac518fdc84621a1dcd610f64f0b06.png
[477b595483004d89b2c42bb17d80dd91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/7b86baea4447429fa80eb48fcf2d9b2c.png
[3065e72f446e44e8a3114db76038206f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/dfea89ab4467479f8a85dc7ac6be40f0.png
[eab2f423621647208017a26c74f61490.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/275e0dfa3757467a9e9cca58585323a9.png