数据结构——括号匹配问题

素颜马尾好姑娘i 2022-12-23 06:52 108阅读 0赞

## 括号匹配 ##

给定一个字符串，其中的字符只包含三种括号：花括号\{ \}、中括号\[ \]、圆括号( )，即它仅由 “( ) \[ \] \{ \}” 这六个字符组成。设计算法，判断该字符串是否有效，即字符串中括号是否匹配。括号匹配要求括号必须以正确的顺序配对，如 “\{ \[ \] ( ) \}” 或 “\[ ( \{ \} \[ \] ) \]” 等为正确的格式，而 “\[ ( \] )” 或 “\{ \[ ( ) \}” 或 “( \{ \} \] )” 均为不正确的格式。

#### 所需的知识前提：栈 ####

###### 以下是顺序栈的基本算法 ######

结构表示，初始化，销毁栈，入栈，出栈，得到栈顶元素，判断栈是否为空等算法

解决问题的关键代码  
//思路  
1.如果是左括号\{ ， \[ ， ( ， 就入栈  
2如果是右括号，先判断栈顶元素是否是这个右括号对应的左括号  
若是则出栈  
若不是则返回no  
3待字符串全部读取完，看栈中栈顶指针与栈底指针指向是否唯一（即判断栈是否为空）  
若栈空，即满足括号匹配输出yes  
若栈不空，即不满足括号匹配输入no

void praenthese_match()
    {
         	
    	SqStack S;
        InitStack(S);
    	printf("输入带括号的字符串序列：");
    	char a[100];
    	 scanf("%s",a);
        int l=strlen(a);
        char e;
        for(int i=0;i<l;i++){
        
            if(a[i]=='('||a[i]=='['||a[i]=='{'){
        
                Push(S,a[i]);
            }
            else{
        
                	if(a[i]==')'&&*(S.top-1)=='(')
    					Pop(S,e);
                	
                	else if(a[i]==')'&&*(S.top-1)!='(')
                		{
        
    						printf("No\n");
                			return;
    					}
                	
    			
    			
    				if(a[i]==']'&&*(S.top-1)=='[')
    					Pop(S,e);
               	 	
                	else if(a[i]==']'&&*(S.top-1)!='[')
                		{
        
    						printf("No\n");
                			return;
    					}	
    			
    				if(a[i]=='}'&&*(S.top-1)=='{')
    					Pop(S,e);
    				else if(a[i]=='}'&&*(S.top-1)!='{')
    					{
        
    						printf("No\n");
                			return;
    					}
                	
            }
        }
        if(S.top==S.base) printf("Yes\n");
        else printf("No\n");
    	
     }

下面是这个问题的全部代码（可以直接运行）  
//输入时是英文的括号这个应该不用我提醒吧！

#include<stdio.h>
    #include<bits/stdc++.h>
    using namespace std;
    #include<malloc.h>
    #include<string>
    
    typedef int Status;
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    
    // ------栈的顺序存储结构表示----------
    #define STACK_INIT_SIZE 100 	// 存储空间初始分配量
    #define STACK_INCREMENT 10 	// 存储空间分配增量
    typedef char ElemType;
    typedef struct {
        
      ElemType *base; 	// 栈底指针
      ElemType *top; 	// 栈顶指针
      int stacksize; 	// 栈空间大小
    } SqStack;
    
    
    void InitStack(SqStack &S)
    {
        
        // 构造一个空栈S
        if(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE 
                                      * sizeof(ElemType))))
            exit(OVERFLOW);     // 存储分配失败
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
    }
    
    void DestroyStack(SqStack &S)
    {
        
        // 销毁栈S，S不再存在
        free(S.base);
        S.base = NULL;
        S.top = NULL;
        S.stacksize = 0;
    }
    
    void Push(SqStack &S, ElemType e)
    {
        
        if(S.top - S.base >= S.stacksize) {
         // 栈满，追加存储空间
            S.base = (ElemType *)realloc(S.base, (S.stacksize 
                  + STACK_INCREMENT) * sizeof(ElemType));
            if(!S.base)
                exit(OVERFLOW);           // 存储分配失败
            S.top = S.base + S.stacksize;
            S.stacksize += STACK_INCREMENT;
        }
        *(S.top)++ = e;
    }
    
    Status Pop(SqStack &S, ElemType &e)
    {
        
        // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
        // 否则返回ERROR
        if(S.top == S.base)
            return ERROR;
        e = *--S.top;
        return OK;
    }
    
    Status GetTop(SqStack S, ElemType &e)
    {
        
        // 若栈不空，则用e返回S的栈顶元素，并返回OK；
        // 否则返回ERROR
        if(S.top > S.base) {
        
            e = *(S.top - 1);
            return OK;
        }
        else
            return ERROR;
    }
    
    Status StackEmpty(SqStack S)
    {
        
        // 若栈S为空栈，则返回TRUE，否则返回FALSE
        if(S.top == S.base)
            return TRUE;
        else
            return FALSE;
    }
    
    void praenthese_match()
    {
         	
    	SqStack S;
        InitStack(S);
    	printf("输入带括号的字符串序列：");
    	char a[100];
    	 scanf("%s",a);
        int l=strlen(a);
        char e;
        for(int i=0;i<l;i++){
        
            if(a[i]=='('||a[i]=='['||a[i]=='{'){
        
                Push(S,a[i]);
            }
            else{
        
                	if(a[i]==')'&&*(S.top-1)=='(')
    					Pop(S,e);
                	
                	else if(a[i]==')'&&*(S.top-1)!='(')
                		{
        
    						printf("No\n");
                			return;
    					}
                	
    			
    			
    				if(a[i]==']'&&*(S.top-1)=='[')
    					Pop(S,e);
               	 	
                	else if(a[i]==']'&&*(S.top-1)!='[')
                		{
        
    						printf("No\n");
                			return;
    					}	
    			
    				if(a[i]=='}'&&*(S.top-1)=='{')
    					Pop(S,e);
    				else if(a[i]=='}'&&*(S.top-1)!='{')
    					{
        
    						printf("No\n");
                			return;
    					}
                	
            }
        }
        if(S.top==S.base) printf("Yes\n");
        else printf("No\n");
    	
     } 
    int main(){
        
       
        praenthese_match();
        
       
    }

![在这里插入图片描述][20201123152145716.png_pic_center]  
![在这里插入图片描述][20201123152145672.png_pic_center]  
![在这里插入图片描述][20201123152145669.png_pic_center]

[20201123152145716.png_pic_center]: /images/20221120/72c34630e80d4f58a792e56d88d4493f.png
[20201123152145672.png_pic_center]: /images/20221120/004faf21206b4e5ebb022378af87a780.png
[20201123152145669.png_pic_center]: /images/20221120/b5ae0ae342044d49a5360ba96839ba23.png