c语言：括号匹配检测（栈的应用）

深藏阁楼爱情的钟 2022-08-03 11:55 166阅读 0赞

/*
    	括号匹配检测，对于一串带括号的字符
    	1.如果是左括号，入栈
    	2.如果是右括号，与栈顶元素比较，
    			若形成括号对，则栈顶左括号出栈；
    			若不能形成括号对，则括号不能匹配
    */
    # include <stdio.h>
    # include <stdlib.h>
    
    # define INIT_SIZE 6   //初始栈空间
    # define INCRE_SIZE 2  //占空间增量
    
    //栈结构
    typedef struct
    {
    	char * base;  //指向栈空间基址
    	char * top;  //指向栈顶元素的下一个位置
    	int initsize;  //栈空间大小
    }Stack;
    
    Stack inital();  //初始化栈
    void push(Stack &s, char ch);  //元素入栈
    void pop(Stack &s, char &e);  //元素出栈
    bool stack_empty(Stack s);  //判断栈是否为空
    
    int main(void)
    {
    	Stack s = inital();
    	char ch[20];
    	char * p;
    	char e;
    
    	printf("请输入带括号的字符串:");
    	gets(ch);	//输入字符
    	p = ch;   //指向首字符
    
    	while(*p)  //没有到串尾
    	{
    		switch(*p)
    		{
    			case '(':       
    			case '[':
    			case '{':
    				push(s, *p); //左括号入栈
    				p ++;      //读下一个字符
    				break;
    
    			case ')':
    			case ']':
    			case '}':
    				pop(s, e);  //读入右括号，与栈顶的左括号e匹配
    				if( !((e == '(' && *p == ')') || (e == '['  && *p == ']') || (e == '{' && *p == '}')))
    				{
    					printf("左右括号不能匹配\n");
    					exit(0);
    				}
    				p ++;
    				break;
    			
    			default:
    				p ++;
    		}
    	}
    	
    	if(stack_empty(s))  //栈是否为空，为空，则匹配成功
    	{
    		printf("括号匹配成功\n");
    	}
    	else
    	{
    		printf("括号匹配失败\n");
    	}
    
    	return 0;
    }
    
    //初始化栈
    Stack inital()
    {
    	Stack s;
    	s.base = (char *)malloc(sizeof(char) * INIT_SIZE);
    	s.initsize = INIT_SIZE;
    	s.top = s.base;
    	return s;
    }
    
    //入栈
    void push(Stack &s, char ch)
    {
    	if(s.top - s.base >= s.initsize) //栈满，增加栈空间
    	{
    		s.base = (char *)realloc(s.base, sizeof(char) * (s.initsize + INCRE_SIZE));
    		s.initsize = s.initsize + INCRE_SIZE;
    	}
    
    	*(s.top) = ch;
    	s.top ++;
    }
    
    //出栈
    void pop(Stack &s, char &e)
    {
    	if(stack_empty(s))
    		return;
    	else
    	{
    		e = *(s.top - 1);
    		s.top --;
    	}
    }
    
    //判断栈是否为空
    bool stack_empty(Stack s)
    {
    	if(s.base == s.top)
    		return true;
    	else
    		return false;
    }

![Center][]

![Center 1][]

[Center]: /images/20220731/f8fdc7d282cf42e99d608f9f9eb2476d.png
[Center 1]: /images/20220731/511905c2ccbd48319a3528a6caf4fdae.png