数据结构-栈应用括号匹配

1、顺序栈的定义

2、顺序栈的入栈，出栈，取出栈顶元素，匹配判断函数

3、顺序栈的运行测试

4、实现代码

#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSIZE 100
typedef struct
{char *top;char *base;int stacksize;
}SqStack;Status InitStack(SqStack &S)
{S.base = new char[MAXSIZE]; //为顺序栈动态分配一个最大容量if (!S.base)            //分配空间失败exit(OVERFLOW);S.top = S.base;            //top起始指向base，表示空栈S.stacksize = MAXSIZE;return OK;
}Status Push(SqStack &S,char e)   //元素e压入栈
{if (S.top - S.base == MAXSIZE)return ERROR;*S.top++ = e;   //top当前指向的内存存储e，之后top++return OK;
}
Status Pop(SqStack &S, char &e) //取出元素e
{if (S.base == S.top)return ERROR;e = *--S.top;  //先让top--指向栈顶元素，然后取出return OK;
}char GetTop(SqStack S)
{if (S.top != S.base)return *(S.top-1); ///取出栈顶元素，top指向保持不变	
}Status CheckStack(SqStack &S,char str[])
{for (int i = 0; i < strlen(str); i++){if (str[i] == '(' || str[i] == '[' || str[i] == '{')Push(S, str[i]);else{if (S.top==S.base)//匹配到右括号，但是栈为空结束匹配{cout << "匹配失败";return ERROR;}if (str[i] == ')'&&GetTop(S) == '(' || str[i] == ']'&&GetTop(S) == '[' || str[i] == '}'&&GetTop(S) == '{'){char temp;Pop(S, temp);  //匹配到右括号，与栈顶元素匹配，如果匹配弹出栈顶元素，继续进行匹配}else{cout << "匹配不成功";return ERROR;}}}if (S.top == S.base){cout << "匹配成功";return OK;}else{cout << "左括号多于右括号,匹配失败";return ERROR;}}
int main()
{SqStack S;InitStack(S);char s[20];cout << "请输入待匹配的括号:";cin >> s;CheckStack(S, s);getchar();getchar();return 0;
}