导言

假设表达式中允许包含两种括号:圆括号和方括号，其嵌套的顺序随意，即【{}】或【([][])】等为正确的格式【[(])】或【[())】等均为不正确的格式。

括号匹配

思路:

左括号入栈，在未遇到右括号前，一直入栈，一旦遇到匹配的右括号，就一直弹出栈顶元素，直到栈空，若栈空，左括号与右括号已匹配完全，则完全匹配，反之则反。

实现

/* 函数结果状态代码 */
#define     TRUE                1
#define     FALSE               0
#define     OK                  1
#define     ERROR               0
#define   OVERFLOW             -2
typedef char SElemType; // 定义栈元素类型为整型
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
//相关头文件包含
#include <iostream>
using namespace std;/*栈的顺序存储表示 */
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef struct SqStack
{SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */SElemType *top; /* 栈顶指针 */int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
/* --------    顺序栈基本函数实现    -------------------*/
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if (!(*S).base)exit(OVERFLOW); /* 存储分配失败 */(*S).top = (*S).base;(*S).stacksize = STACK_INIT_SIZE;return OK;
}
Status DestroyStack(SqStack *S)
{ /* 销毁栈S，S不再存在 */free((*S).base);(*S).base = NULL;(*S).top = NULL;(*S).stacksize = 0;return OK;
}Status ClearStack(SqStack *S)
{ /* 把S置为空栈 */(*S).top = (*S).base;return OK;
}Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */if (S.top == S.base)return TRUE;elsereturn FALSE;
}int StackLength(SqStack S)
{ /* 返回S的元素个数，即栈的长度 */return S.top - S.base;
}Status GetTop(SqStack S, SElemType &e)
{if (S.top == S.base)return ERROR;e = *(S.top - 1);return OK;
}//GetTopStatus Push(SqStack &S, SElemType e)
{//插入元素e为新的栈顶元素if (S.top - S.base >= S.stacksize){//栈满，追加存储空间S.base = (SElemType *)realloc(S.base, (S.stacksize, STACKINCREMENT)*sizeof(SElemType));if (!S.base)exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;
}//pushStatus Pop(SqStack &S, SElemType &e)
{//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif (S.top == S.base)return ERROR;e = *--S.top;return OK;
}//popStatus StackTraverse(SqStack S, Status(*visit)(SElemType))
{ /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 *//* 一旦visit()失败，则操作失败 */while (S.top>S.base)visit(*S.base++);cout << "\n";return OK;
}void visit(SElemType e)
{cout << e;
}void check()
{// 对于输入的任意一个字符串，检验括号是否配对SqStack sq;SElemType ch[100], *p, e;InitStack(&sq); // 初始化栈成功cout << "请输入带括号（()、[]和{}）的表达式:\n";cin.getline(ch, 101, '\n');p = ch;//p指向第一个while (*p != '\0')//没到表尾{switch (*p){case '(':case '[':case '{':Push(sq, *p++); // 左括号入栈，且p++,p指向下一个元素break;case ')':case ']':case '}':if (!StackEmpty(sq))//如果栈不为空{Pop(sq, e); // 弹出栈顶元素if (!(e == '('&&*p == ')' || e == '['&&*p == ']' || e == '{ '&&*p == ' }')){ // 出现3种匹配情况之外的情况cout << "左右括号不匹配" << endl;system("pause");exit(ERROR);}}else // 栈空{cout << "缺乏匹配的左括号" << endl;system("pause");exit(ERROR);}default:p++;//只把括号字符压栈，其他字符不压栈break;}}if (StackEmpty(sq)) // 字符串结束时栈空cout << "括号完全匹配" << endl;elsecout << "缺乏右括号" << endl;}int main()
{//本程序说明，是在VS2013中运行的，若是其他地方无法运行，建议修改代码//程序声明cout << "***************************************************************************" << endl;cout << "                   《数据结构》<C语言版本>严蔚敏 吴伟名 编著              " << endl;cout << "                                编写年月2016年3月                         " << endl;cout << "                                 编写者:YuYunTan                          " << endl;cout << "                                      括号匹配                             " << endl;cout << "***************************************************************************" << endl;check();system("pause");return 0;
}

运行结果