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

忘是亡心i 2024-03-30 09:08 81阅读 0赞

#include<stdio.h>//用栈实现括号匹配：
    
    #define maxize 10//定义了maxize的值是10；
    
    typedef int ;
    
    typedef struct
    
        char data[maxize]; //静态数组存放栈中元素
    
        int top;  //当前栈顶元素
    
    } SqStack;
    
    int b1(char str[],int length);//匹配括号
    
    void initStack(SqStack *s);//构造一个空栈s
    
    int stackEmpty(SqStack s);//判断栈是否为空
    
    int push(SqStack *s,char e);//插入元素e为新的栈顶元素
    
    int pop(SqStack *s,char *e);//删除栈顶元素返回e值
    
    int getTop(SqStack s,char *e);//返回栈顶元素
    
    void print(SqStack s);//出栈
    
    int b1(char str[],int length)
    
    {
    
        SqStack s;
    
       initStack(&s);
    
        int i;
    
        for(i=0; i<length; i++)//扫描左括号，入栈
    
        {
    
            if(str[i]=='('||str[i]=='{'||str[i]=='[')
    
            {
    
                push(&s,str[i]);
    
            }
    
            else//扫描遇到右括号，且当前栈空，则匹配失败
    
            {
    
                if(stackEmpty(s))
    
                {
    
                    return 0;
    
                }
    
                char e;
    
                pop(&s,&e);//左右括号不匹配，则匹配失败
    
                if(str[i]==')'&&e!='(')
    
                {
    
                    return 0;
    
                }
    
                if(str[i]=='}'&&e!='{')
    
                {
    
                    return 0;
    
                }
    
                if(str[i]==']'&&e!='[')
    
                {
    
                    return 0;
    
                }
    
            }
    
        } //考虑左括号是不是为0
    
        return stackEmpty(s);
    
    }
    
    void initStack(SqStack *s)
    
    {
    
        s->top=-1;//构造空栈
    
    }
    
    
    
    int stackEmpty(SqStack s)
    
    {
    
        if(s.top>=0)//判断栈是否为空
    
        {
    
            return 0;
    
        }
    
        return 1;
    
    }
    
    int push(SqStack *s,char e)
    
    {
    
        if(s->top==maxize-1)
    
        {
    
            return 0;
    
        }
    
        s->top=s->top+1;
    
        s->data[s->top]=e;//插入元素
    
        return 1;
    
    }
    
    
    
    int pop(SqStack *s,char *e)
    
    {
    
        if(s->top==-1)
    
        {
    
            return 0;
    
        }
    
        *e=s->data[s->top];
    
        s->top=s->top-1;
    
        return 1;
    
    }
    
    int getTop(SqStack s,char *e)
    
    {
    
        if(s.top==-1)//判断栈是否存在且非空
    
        {
    
            return 0;
    
        }
    
        *e=s.data[s.top];
    
        return 1;
    
    }
    
    void print(SqStack s)
    
    {
    
        int i;
    
        for(i=s.top; i>=0; i--)//全部出栈
    
        {
    
            printf("%c ",s.data[i]);
    
        }
    
        printf(" ");
    
    }
    
    int main()
    
    {
    
        char str[]= {'[','{','(',')','}',']'};//输入所需匹配的符号
    
        int lenth=sizeof(str)/sizeof(char);
    
        if(b1(str,lenth))
    
        {
    
            printf("括号匹配 ");//匹配失败
    
        }
    
        else
    
        {
    
            printf("括号不匹配 ");//匹配成功
    
        }
    
        return 0;
    
    }