栈的应用：括号匹配检验

短命女 2022-05-26 01:56 223阅读 0赞

> 输入包含括号的表达式，包含3中括号：圆括号()，方括号\[\],大括号\{\}；其嵌套顺序随意，即（）或\{ \{（）\[\]\}\}等均为正确的输入格式，检验输入表达式中的括号是否匹配。

--------------------

源代码：

**BracketMatch.h**

#ifndef __BRACKETMATCH_H__
    #define __BRACKETMATCH_H__
    
    #define MAXSIZE 100
    
    typedef char DataType;
    typedef struct
    {
        DataType stack[MAXSIZE];
        int top;
    }SeqStack;
    
    void InitStack(SeqStack* s);   //初始化顺序栈
    int StackEmpty(SeqStack* s);   //判断栈是否为空
    int StackPush(SeqStack* s, DataType data);   //入栈操作
    void StackPop(SeqStack* s, DataType* data);   //出栈操作
    int GetTop(SeqStack* s, DataType* data);      //取栈顶元素
    int Match(char ch, char c);    //判断左右两个括号是否是相同类型的括号
    void CheckMatch(DataType* ch, SeqStack s);  //括号匹配检测
    
    #endif

--------------------

**BracketMatch.c**

#include <stdio.h>
    #include <stdlib.h>
    #include "BracketMatch.h"
    
    int top = -1;
    
    //初始化栈
    
    void InitStack(SeqStack* s)
    {
        s->top = -1;
    }
    
    //判断栈是否为空
    int StackEmpty(SeqStack* s)
    {
        if (s->top == -1)
        {
            return 1;
        }
        return 0;
    }
    
    //入栈操作
    
    int StackPush(SeqStack* s, DataType data)
    {
        if (s->top == MAXSIZE)
        {
            printf("栈已满，不能入栈！\n");
        }
        s->top++;
        s->stack[s->top] = data;
        return 1;
    }
    
    //出栈
    void StackPop(SeqStack* s, DataType* data)
    {
        if (StackEmpty(s))
        {
            printf("栈为空！\n");
        }
        *data = s->stack[top];
        s->top--;
    }
    
    //取栈顶元素
    
    int GetTop(SeqStack* s, DataType* data)
    {
        if (StackEmpty(s))
        {
            printf("栈为空");
        }
        *data = s->stack[s->top];
        return *data;
    }
    
    //判断左右两个括号是否是同类型的括号
    
    int Match(char ch, char c)
    {
        if (ch == '('&&c == ')')
        {
            return 1;
        }
        if (ch == '['&&c == ']')
        {
            return 1;
        }
        if (ch == '{'&&c == '}')
        {
            return 1;
        }
        return 0;
    }
    
    //检测括号是否匹配
    
    void CheckMatch(DataType* p, SeqStack s)
    {
        DataType c; 
        while (*p)
        {
            switch (*p)
            {
                /*如果是左括号，将其入栈*/
            case '(':
            case '[':
            case '{':
                StackPush(&s, *p++);  
                break;
            case ')':
            case ']':
            case '}':
                /*栈为空 ，说明没有左括号入栈*/
                if (StackEmpty(&s))
                {
                    printf("缺少左括号！\n");
                    return;
                }
                else
                {
                    /*取出栈顶元素，将栈顶元素与读入的右括号比较，如果栈顶括号与 右括号匹配，则将栈顶括号出栈*/
                    GetTop(&s, &c);
                    if (Match(c, *p))
                    {
                        StackPop(&s, &c);
                    }
                    /*栈顶括号与读入的括号不匹配*/
                    else
                    {
                        printf("左右括号不匹配！\n");
                        return;
                    }
                }
                /*如果读入的不是括号，指针后移一位*/
            default:
                p++;
            }
        }
        /*栈为空，所有的字符序列读入完毕，说明括号序列匹配*/
        if (StackEmpty(&s))
        {
            printf("括号匹配！\n");
        }
        else
        {
            printf("缺少右括号！\n");
        }
    }

**main.c**

#include <stdio.h>
    #include <stdlib.h>
    #include "BracketMatch.h"
    #include <stdio.h>
    
    int main()
    {
        DataType ch[MAXSIZE];
        char*p;
        p = ch;
        memset(ch, 0x00, sizeof(ch));
        SeqStack  s;
        InitStack(&s);
        printf("请输如一个带括号的表达式：\n");
        gets(ch);
        CheckMatch(p,s);
        return 0;
    }