【uva-673】 Parentheses Balance（括号匹配问题）

题干：

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

<dl compact="" style="border-width:0px;list-style:none;color:rgb(51,51,51);font-family:Simsun;font-size:14px;background-color:rgb(249,249,249);"> <dd style="border-width:0px;margin-left:0px;list-style:none;"> (a)if it is the empty string(b)if A and B are correct, AB is correct,(c)if A is correct, <tt>(</tt>A <tt>)</tt> and <tt>[</tt>A <tt>]</tt> 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 <tt>()</tt> and <tt>[]</tt>, one string a line.

Output

A sequence of <tt>Yes</tt> or <tt>No</tt> on the output file.

Sample Input

3

           ([])          
           (([()])))          
           ([()[]()])()          

Sample Output

           Yes          
           No          
           Yes          

</dd> </dl>

解题报告：

注意运用栈的知识，再一点就是注意空串！所以这里不能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中！理清楚！