括号是否匹配问题求解
以下为代码演示:
- /***
- // 括号匹配问题
- 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);
- }