【uva-673】 Parentheses Balance（括号匹配问题）,摩托罗拉e8论坛

文件名：【uva-673】 Parentheses Balance（括号匹配问题）,摩托罗拉e8论坛 【uva-673】 Parentheses Balance（括号匹配问题）

题干：

You are given a string consisting of parentheses () and []. A string of this type is said to be correct:

(a)if it is the empty string(b)if A and B are correct, AB is correct,(c)if A is correct, (A) and [A] is correct.

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

Input

The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.

Output

A sequence of Yes or No on the output file.

Sample Input?13?123([])(([()])))([()[]()])()

Sample Output

?123YesNoYes

解题报告：

    注意运用栈的知识，再一点就是注意空串！所以这里不能scanf("%s",a);，只能gets(a)或者cin.getline(a , 200 + 5);，因为gets有的地方不让用了！这里编译器选择的是 C++11 5.3.0 还可以用。

ac代码：

#include<iostream>#include<stack>#include<cstdio>#include<cstring>using namespace std;char a[200+5];int main(){int n,len;int flag=0;cin>>n;getchar();while(n--) {flag=0;stack<char > sk;gets(a);len=strlen(a);for(int i = 0; i<len; i++) {if(a[i]=='['||a[i]=='(') {sk.push(a[i]);continue;}if(a[i]==']'&&sk.empty()) {flag=1;break;}if(a[i]==')'&&sk.empty()) {flag=1;break;}if(a[i]==']' && sk.top()!='[') {flag=1;break;}else if(a[i]==']' && sk.top()=='['){//不能直接else 需else if sk.pop();//错误示范在下面↓↓ }if(a[i]==')' && sk.top()!='(') {flag=1;break;}else if(a[i]==')' && sk.top()=='('){sk.pop();}}if(len==0) {printf("Yes\n");continue;}if(flag||!sk.empty()) {printf("No\n");}else {printf("Yes\n");}}return 0 ;}//if(a[i]==']' && sk.top()!='[') {//flag=1;//break;//}//else {//sk.pop();//}//if(a[i]==')' && sk.top()!='(') {//flag=1;//break;//}//else {//sk.pop();//}

法2：（wjh写）

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring> using namespace std;//D 奇数× ][ [(]) [[((]])) int cmp(int a,int b){return a>b;}int main(){int n;char a[140];cin>>n;getchar(); while(n--){int l1=0,r1=0,l2=0,r2=0;gets(a);int fl1=0,fl2=0,flag=0;int l=strlen(a);for(int i=0;i<l;i++){if(a[i]=='('){l1++;fl1++;}else if(a[i]==')'){r1++;fl1--;}else if(a[i]=='['){l2++;fl2++;}else if(a[i]==']'){r2++;fl2--;}if(fl1<0||fl2<0||a[i]=='('&&a[i+1]==']'||a[i]=='['&&a[i+1]==')')flag=-1;}if(l%2==1)//l&1{printf("No\n");}else if(l1!=r1||l2!=r2){printf("No\n");}else if(flag==-1){printf("No\n");}else printf("Yes\n");}return 0;}

做题总结：1.看到最近问题，相邻问题 想到栈。 

        2.正着想不成立时倒着想即可，比如此题：正着想'('不一定和相邻的')'匹配，但是倒着想')'一定和相邻的'('是一对儿。 

                3.if判断分支的时候，一定弄清楚逻辑结构！那种if里面一个条件的还好，就三种 > 、= 、<，但是这种两个的或者多个的一定分清楚包含关系，对立关系！严格的说两个条件的就有3×3=9 种 可能的情况了！if中！理清楚！