XDOJ 括号匹配 C

前言

日做日新。

题干

问题描述    
表达式中的合法括号为“(”、“)”、“[”、“]”、“{”、“}”，这三种括号可以按照任意的次序嵌套使用。
请写一个程序，判断给定表达式中的括号是否匹配，既左右括号顺序和数量都匹配。

输入说明    
输入为一个表达式字符串，长度不超过50。

输出说明    
对输入的表达式，若其中的括号是匹配的，则输出“yes”，否则输出“no”。

输入样例    
样例1输入
[(d+f)*{}2]
样例2输入
[(2+3))

输出样例    
样例1输出
yes
样例2输出
no
 

解析

难点 

1. 判断括号匹配的方式？——> 函数，使程序模块化
2. 判断括号匹配的思想？——> 栈（只有左括号入栈）
3. 起始位置的选取？——> 第一个右括号出现，开始与栈顶的左括号匹配

解答

1.0（虽然AC，但我发现OJ的数据 漏情况）比如：输入[[2+3]*3]，输出结果错误

#include<stdio.h>
#include<string.h>
int dy(char x,char y);
int main(){int i,j=0,len;char a[55],b[55];gets(a);len=strlen(a);for(i=0;i<len;i++){if(a[i]=='('||a[i]=='['||a[i]=='{'||a[i]==')'||a[i]==']'||a[i]=='}'){b[j]=a[i];j++;}}if(j%2!=0){printf("no");return 0;}else{len=j;for(i=0;i<len;i++){for(j=i+1;j<len;j++){if(dy(b[i],b[j])==1){if((i+j)%2==0){printf("no");return 0;}}}}if(i==len){printf("yes");}	}return 0;
}
int dy(char x,char y){if(x=='{'&&y!='}') return 0;if(x=='['&&y!=']') return 0;if(x=='('&&y!=')') return 0;if(x=='}'&&y!='{') return 0;if(x==']'&&y!='[') return 0;if(x==')'&&y!='(') return 0;return 1;
}

2.0 利用栈

#include<stdio.h>
#include<string.h>int left(char c){if(c=='('||c=='{'||c=='[') return 1;return 0;
}int right(char c){if(c==')'||c=='}'||c==']') return 1;return 0;
}int check(char left,char right){if(left=='('&&right==')') return 1;if(left=='{'&&right=='}') return 1;if(left=='['&&right==']') return 1;return 0;
}int main(){int i=0,l;char stack[30];int top=0;		// initial stack top=0char s[60];gets(s);l=strlen(s);for(i=0;i<l;i++){if(left(s[i])==1){stack[top]=s[i];top++;}else if(right(s[i])==1){if(check(stack[top-1],s[i])){top--;continue;}else{printf("no");return 0;}}}if(top==0) printf("yes");	// is stack empty?else printf("no");return 0;
}

拓展

栈

数据结构-栈（Stack） - 知乎 (zhihu.com)

本人2.0代码参考

C语言括号匹配_故园归梦的博客-CSDN博客_c语言括号匹配