括号匹配

我就是我 2023-06-08 09:24 6阅读 0赞

## c语言数据结构栈-1931扩号匹配 ##

描述  
判断一组匹配的左右扩号序列中，每一个右扩号与之相匹配成对的左扩号是整个扩号序列的第几个扩号。输出所有判断结果。  
输入  
输入有两行。  
第一行输入一个整数（该整数必定是偶数），该整数表示扩号序列中一共有多少个扩号。  
第二行输入用1和2分别代表左右扩号的扩号序列。例如输入序列11211222，表示扩号序列(()(()))。  
输出  
输出为一行。即挨个输出每个2（右扩号‘）’）与之相匹配的1（左扩号‘（’）在扩号序列中是第几个，用空格格开。  
样例输入  
4  
1212  
4  
1122  
6  
112122  
8  
11211222  
20  
11211122122121122212  
样例输出  
1 3  
2 1  
2 4 1  
2 5 4 1  
2 6 5 9 4 12 15 14 1 19  
提示  
输入的扩号总数一定为偶数。输入的12序列必定是匹配的，1和2的个数相等，必为扩号总数的一半。  
测试数据有多组，采用while()循环输入。

#include<stdio.h>
    #include<stdlib.h>
    #define N 100
    #define SIZE 20
    
    
    typedef struct stack{ 
    	char *base,*top;
    }stack;
    
    //将栈初始化，申请内存空间 
    int initSatck(stack &s){ 
    	s.base=(char*)malloc(sizeof(char)*(SIZE+N));
    	if(!s.base)//若内存空间申请失败，直接返回 
    		return 0;
    	
    	s.top=s.base;//让栈顶指针指向栈底 
    	return 1;
    }
    
    //入栈函数，将元素压入栈内 
    int push(stack &s,char e){ 
    	char *p;
    	if(!s.base){ //若无内存空间，则返回 
    		return 0;
    	}
    	*s.top=e;//赋值 
    	s.top++;//将栈顶指针向上移动 
    	return 1;
    }
    
    
    //出栈函数，将栈顶元素挤出栈 
    int pop(stack &s){ 
    	if(!s.base||s.base==s.top){ //若无内存空间或栈为空，直接返回 
    		return 0;
    	}
    	s.top--;//栈顶指针向下移动 
    	return 1;
    }
    
    int main(){ 
    	stack s;//定义栈 
    	int i,n,index[N],m=0,t=0;//n为每次要匹配的括号总数，index[]数组记录存储进栈的左括号（即输入的1）在括号序列中的对应序号 
    	char flag[N];//t为标记变量，负责标记若为最后一个输出元素，则不输出元素后多余的空格 
    	initSatck(s);
    	while(scanf("%d",&n)!=-1){ 
    		scanf("%s",&flag);
    		
    		for(i=0;i<n;i++){ //进入for循环，开始处理这一轮的括号匹配 
    			if(flag[i]=='1'){ //若为左括号，则压入栈内 
    				push(s,flag[i]);
    				index[m]=i+1;//同时记录下对应的左括号在括号序列中的下标，方便匹配到右括号时输出 
    				m++;
    			}
    			if(*(s.top-1)=='1'&&flag[i+1]=='2'){ //若匹配成功 
    					t++;//标记变量自增 
    				if(t==n/2)//若为最后一个元素，输出无多余的空格 
    					printf("%d",index[m-1]);
    				else
    					printf("%d ",index[m-1]);//不是最后一个元素，则应该输出空格，
    											//此处若不进行处理，则会导致编译不通过，发生“output limit exceeded”错误 
    				pop(s);//将左括号挤出栈 
    				if(*(s.top-1)=='1')//若挤出栈后，栈内还有左括号， 
    					m--;//此时栈内的元素为刚匹配完的左括号的前一个括号，m--以后， 
    						//index数组中存储的最后一个值与栈顶元素在括号序列的序列号（下标）保持一致 
    			}	
    		}
    		m=0;//完成一轮数据的处理后，将m和t初始化为0 
    		t=0;
    		printf("\n");
    	}
    	return 0;
    }

注意：由于以上代码中使用了引用，所有保存文件时需要将格式保存为.cpp，提交时语言需选择c++