本文共 6414 字，大约阅读时间需要 21 分钟。
学习数据结构与算法过程中的心得体会以及知识点的整理，方便我自己查找，也希望可以和大家一起交流。
Candela是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的Candela画了一排括号序列，其中包含小括号()、中括号[]和大括号{}，总长度为N。这排随意绘制的括号序列显得杂乱无章，于是Candela定义了什么样的括号序列是美观的： (1) 空的括号序列是美观的； (2) 若括号序列A是美观的，则括号序列(A)、[A]、{A}也是美观的； (3)若括号序列A、B都是美观的，则括号序列AB也是美观的； 例如 (){[]}() 是美观的括号序列，而 )({)[}]( 则不是。 现在Candela想知道她画出的括号序列是不是美观的。你能帮帮她吗？
一个括号序列，长度不超过10000。
如果它是美观的，输出Yes，否则输出No。
样例输入 { } ( ) { [ ] } ( ) 样例输出 Yes
c
#include#include #include typedef char ElemType;typedef struct{ //存储元素的数组 ElemType *base; //栈顶指针 int top; //当前分配的存储容量( 以sizeof(ElemType)为单位 ) int capacity;}Stack;//初始化一个空栈。空栈拥有10000个元素的空间，栈顶值为 -1void init(Stack *pStack){ pStack->base=(ElemType*)malloc(10*sizeof(ElemType)); pStack->capacity=10; pStack->top=-1;}//把x入栈void push(Stack *pStack,ElemType x){ //如果输入的元素即将超出栈的最大限制，那么进行扩容。 if(pStack->top==pStack->capacity-1) { //以原来容量的两倍进行扩容. pStack->capacity*=2; ElemType*b=(ElemType*)malloc(pStack->capacity*sizeof(ElemType)); //复制数据到新的扩容后的栈中数组 for(int e=0;e<=pStack->top;e++) { b[e]=pStack->base[e]; } free(pStack->base); pStack->base=b; } //如果输入的元素没有超出栈的最大限制，那么将元素压栈 pStack->base[++pStack->top]=x;}//返回当前栈顶元素的值ElemType top(Stack *pStack){ ElemType f=pStack->base[pStack->top]; return f;}//当前栈顶元素出栈void pop(Stack *pStack){ pStack->top--;}//判断是否栈空，若空则返回 true，否则返回 falsebool empty(Stack *pStack){ if(pStack->top==-1) return true; else return false;}//清空分配给栈的存储空间void destroy(Stack *pStack){ free(pStack->base); free(pStack);}int main(void){ char c[10000]; Stack *pStack; pStack=(Stack*)malloc(sizeof(Stack)); init(pStack); bool flag=true; gets(c); for(int i=0;c[i]!='\0';i++) { if(c[i]=='('||c[i]=='['||c[i]=='{') push(pStack,c[i]); if(c[i]==')'||c[i]==']'||c[i]=='}') { if(empty(pStack)) { printf("No\n"); flag = false; break; } else { if((c[i]==')'&&pStack->base[pStack->top]=='(')|| (c[i]==']'&&pStack->base[pStack->top]=='[')|| (c[i]=='}'&&pStack->base[pStack->top]=='{')) { pop(pStack); continue; } else { printf("No\n"); flag=false; break; } } } } if(flag==true) { if(empty(pStack)) printf("Yes\n"); else printf("No\n"); } destroy(pStack); return 0;}
这道题虽然说什么美观的括号，但其实就是利用栈实现括号的匹配，那我们首先就要搞清楚括号匹配和不匹配的类型：
1.匹配的类型就一种，我们利用栈的先进后出的特性，对括号从最内侧进行匹配，如果到最后一个元素输入后，整个栈中没有元素（匹配后元素就直接出栈删除）的话，就是匹配的，输出“Yes”。 2.不匹配的类型有三种 2.1左括号多余，也就是说在输入数据结束后，最后一个元素是括号的左半部分“（”，“{”，“[”。那么这个时候就是输出“No”。 2.2右括号多余，也就是说在输入数据结束后，最后一个元素是括号的右半部分“）”，“}”，“]”。那么这个时候就是输出“No”。 2.3括号不匹配，也就是说在输入数据结束后，栈内元素的括号不能相互匹配，例如：“（}”，“{[”，“[{)”。那么这个时候就是输出“No”。 3.其实大体思路就是每输入一个数据就对前一个数据进行匹配，如果匹配成功就一起出栈，如果到最后栈内没有数据了，那就是yes，反之就是No。 4.具体写第二条是因为，有些题目会要求细分为具体不匹配的原因，例如下面这题：假设表达式中只包含三种括号：圆括号、方括号和花括号，它们可相互嵌套，如([{}])或({[][()]})等均为正确的格式,而{[]})}或{[()]或([]}均为不正确的格式.
输入一串括号 如果输入的右括号多余，输出:Extra right brackets 如果输入的左括号多余,，输出:Extra leftbrackets 如果输入的括号不匹配，输出:Brackets not match 如果输入的括号匹配，输出:Brackets match
{ { { {)))
Brackets not match
样例输入
{([)]}
样例输出
Brackets not match
这个时候我们只需要把上面的代码稍微改一下输出就可以了
c
#include#include #include typedef char ElemType;typedef struct{ ElemType *base; //存储元素的数组 int top;//栈顶指针 int capacity; //当前分配的存储容量( 以sizeof(ElemType)为单位 )}Stack;void init(Stack *pStack) //初始化一个空栈。空栈拥有10个元素的空间，栈顶值为 -1{ pStack->base =(ElemType*)malloc(10*sizeof(ElemType)); pStack->capacity = 10; pStack->top = -1;}void push(Stack *pStack, ElemType x)//把 x 入栈{ if(pStack->top == pStack->capacity - 1) { pStack->capacity*=2; ElemType*b = (ElemType*)malloc(pStack->capacity*sizeof(ElemType)); for(int e=0;e<=pStack->top;e++) { b[e] = pStack->base[e]; } free(pStack->base); pStack->base = b; } pStack->base[++pStack->top] = x;}ElemType top(Stack *pStack)//返回当前栈顶元素的值{ ElemType f = pStack ->base[pStack->top]; return f;}void pop(Stack *pStack)//当前栈顶元素出栈{ pStack->top--;}bool empty(Stack *pStack)//如果栈空，则返回 true，否则返回 false{ if(pStack->top == -1) return true; else return false;}void destroy(Stack *pStack)//清空分配给栈的存储空间{ free(pStack->base); free(pStack);}int main(void){ char c[31]; Stack *pStack; pStack = (Stack*)malloc(sizeof(Stack)); init(pStack); bool flag = true; gets(c); for(int i=0;c[i]!='\0';i++) { if(c[i] == '('||c[i] == '['||c[i] == '{') push(pStack,c[i]); if(c[i] == ')'||c[i] == ']'||c[i] == '}') { if(empty(pStack)) { //改动1 printf("Extra right brackets\n"); flag = false; break; } else { if((c[i] == ')'&&pStack->base[pStack->top] == '(')|| (c[i] == ']'&&pStack->base[pStack->top] == '[')|| (c[i] == '}'&&pStack->base[pStack->top] == '{')) { pop(pStack); continue; } else { //改动2 printf("Brackets not match\n"); flag = false; break; } } } } if(flag == true) { if(empty(pStack)) //改动3 printf("Brackets match\n"); else //改动4 printf("Extra left brackets\n"); } destroy(pStack); return 0;}
转载地址：http://ifazi.baihongyu.com/