think：1.空格的输入 2.临界情况的考虑
数据结构实验之栈四：括号匹配 Time Limit: 1000MS Memory Limit: 65536KB
Problem Description 给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。
Input 输入数据有多组，处理到文件结束。
Output 如果匹配就输出“yes”，不匹配输出“no”
Example Input sin(20+10) {[}]
Example Output yes no
Hint
Author ma6174
accepted
#include <stdio.h> #include <string.h> #define MAXN 64 int top1, top2; char stacks1[MAXN], stacks2[MAXN], s[MAXN]; int main() { int i, len; while(gets(s) != NULL) { top1 = top2 = 0; len = strlen(s); for(i = 0; i < len; i++) { if(s[i] == '{' || s[i] == '[' || s[i] == '(') stacks1[top1++] = s[i]; if(s[i] == '}' || s[i] == ']' || s[i] == ')') stacks1[top1++] = s[i]; } stacks1[top1] = '\0'; stacks2[0] = stacks1[0]; for(i = 1; i < top1; ) { if((top2 >= 0) && ((stacks2[top2] == '{' && stacks1[i] == '}') || (stacks2[top2] == '[' && stacks1[i] == ']') || (stacks2[top2] == '(' && stacks1[i] == ')'))) { top2 -= 1; i++; } else { stacks2[++top2] = stacks1[i]; i++; } } if(top2 == -1 || top1 == 0) printf("yes\n"); else printf("no\n"); } return 0; } /*************************************************** User name: jk160630 Result: Accepted Take time: 0ms Take Memory: 112KB Submit time: 2017-02-01 20:21:49 ****************************************************/wrong answer(忽视了字符串中空格的输入)
#include <stdio.h> #include <string.h> #define MAXN 64 int top1, top2; char stacks1[MAXN], stacks2[MAXN], s[MAXN]; int main() { int i, len; while(scanf("%s", s) != EOF) { top1 = top2 = 0; len = strlen(s); for(i = 0; i < len; i++) { if(s[i] == '{' || s[i] == '[' || s[i] == '(') stacks1[top1++] = s[i]; if(s[i] == '}' || s[i] == ']' || s[i] == ')') stacks1[top1++] = s[i]; } stacks1[top1] = '\0'; stacks2[0] = stacks1[0]; for(i = 1; i < top1; ) { if((top2 >= 0) && ((stacks2[top2] == '{' && stacks1[i] == '}') || (stacks2[top2] == '[' && stacks1[i] == ']') || (stacks2[top2] == '(' && stacks1[i] == ')'))) { top2 -= 1; i++; } else { stacks2[++top2] = stacks1[i]; i++; } } if(top2 == -1 || top1 == 0) printf("yes\n"); else printf("no\n"); } return 0; } /*************************************************** User name: jk160630 Result: Wrong Answer Take time: 0ms Take Memory: 108KB Submit time: 2017-02-01 20:18:35 ****************************************************/wrong answer(忽视了空格输入、未考虑临界值得带入、测试数据考虑不全面)
#include <stdio.h> #include <string.h> #define MAXN 64 int top1, top2; char stacks1[MAXN], stacks2[MAXN], s[MAXN]; int main() { int i, len; while(scanf("%s", s) != EOF) { top1 = top2 = 0; len = strlen(s); for(i = 0; i < len; i++) { if(s[i] == '{' || s[i] == '[' || s[i] == '(') stacks1[top1++] = s[i]; if(s[i] == '}' || s[i] == ']' || s[i] == ')') stacks1[top1++] = s[i]; } stacks1[top1] = '\0'; stacks2[0] = stacks1[0]; for(i = 1; i < top1; ) { if((stacks2[top2] == '{' && stacks1[i] == '}') || (stacks2[top2] == '[' && stacks1[i] == ']') || (stacks2[top2] == '(' && stacks1[i] == ')')) { top2 -= 1; i++; } else { stacks2[++top2] = stacks1[i]; i++; } } if(top2 <= 0) printf("yes\n"); else printf("no\n"); } return 0; } /*************************************************** User name: jk160630 Result: Wrong Answer Take time: 0ms Take Memory: 112KB Submit time: 2017-02-01 10:34:22 ****************************************************/