【数据结构】利用栈求解括号匹配问题

朴灿烈づ我的快乐病毒、 2022-08-25 08:39 137阅读 0赞

括号是否匹配问题求解

以下为代码演示：![吐舌头][tongue.gif]

/***
    // 括号匹配问题
    InitStack ( &S)  :  栈的初始化
    Push ( &S, e) :进栈
    Pop (&S ) : 出栈
    GetTop (S ): 取栈顶元素
    IsEmpty (S): 判栈空否
    ***/
    #include <stdio.h>
    #include <stdlib.h>
    
    #define STACK_MAX 1000
    typedef char ElemType;
    
    typedef struct Stack
    {
    	int top;
    	ElemType elem[STACK_MAX];
    }Stack,*Pstack;
    
    void InitStack (Pstack S) ;           // 栈的初始化
    void Push (Pstack S, ElemType elem) ;  // 进栈
    void Pop (Pstack S ) ;                // 出栈
    ElemType GetTop (Pstack S );          // 取栈顶元素
    bool IsEmpty (Pstack S);              // 判栈空否
    bool match(char a,char b);
    
    void main()
    {
    	int i = 0;
    	bool bMatch = true;
    	char s[100] = "";
    	scanf("%s",s);
    
    	Stack data;
    	Pstack S = &data;
    
    	InitStack(S);
    
    	while (s[i] != '\0')
    	{
    		char elem = s[i];
    
    		if (elem == '{' || elem == '[' || elem == '(')
    			Push(S,elem);
    		else
    		{
    			if (IsEmpty(S))
    			{
    				bMatch = false;
    				break;
    			}
    
    			if (match(elem,GetTop(S)))
    			{
    				Pop(S);
    			}
    			else
    			{
    				bMatch = false;
    				break;
    			}
    		}
    		i++;
    	}
    
    	if (bMatch && IsEmpty(S))
    	{
    		printf("括号匹配\n");
    	}
    	else
    	{
    		printf("括号不匹配\n");
    	}
    }
    
    
    bool match(char a,char b)
    {
    	switch(a)
    	{
    	case '}':
    		if (b == '{')
    			return true;
    	case ']':
    		if (b == '[')
    			return true;
    	case ')':
    		if (b == '(')
    			return true;
    		break;
    	default :
    		exit(-1);
    	}
    }
    void InitStack (Pstack S)   // 栈的初始化
    {
    	S->top = 0;
    
    	for (int i = 0; i < STACK_MAX; i++)
    		S->elem[i] = 0;
    }
    
    void Push (Pstack S, ElemType elem) // 进栈
    {
    	if (S->top != STACK_MAX)    // 判断是否栈满
    		S->elem[(S->top)++] = elem;
    }
    
    void Pop (Pstack S ) // 栈顶元素出栈
    {
    	S->elem[-- (S->top)] = 0;
    }
    
    ElemType GetTop (Pstack S ) // 取栈顶元素
    {
    	if (!IsEmpty(S))
    		return S->elem[S->top-1];
    	else
    		printf("栈空~~\n");
    }
    
    bool IsEmpty (Pstack S) // 判栈空否
    {
    	return (S->top == 0);
    }

[tongue.gif]: /images/20220824/2dbeff9a78a2442abb7e16ad71e5e91f.png