【面试题】括号婚配

使用STL中的stack

#include <iostream>
#include <stack>
#include <assert.h>
using namespace std;

bool isValidSeq(char *s)
{
	assert(s != NULL);
	stack<char> st;
	char *p = s;
	while(*p != '\0')
	{
		if(!st.empty())
		{
			if(st.top() == '(' && *p == ')' || st.top() == '[' && *p == ']' || st.top() == '{' && *p == '}')
			{
				cout << st.top() <<" "<<*p<<" ";
				st.pop();
			}
			else
			{
				st.push(*p);
			}			
		}
		else
		{
			st.push(*p);
		}
		p++;
	}
	return st.empty();
}

void main()
{
	char *s = "(){{}[}]";
	if(isValidSeq(s))
	{
		cout <<"合法的"<<endl;
	}
	else
	{
		cout << "非法的" <<endl;
	}
}

 这是其他人的方法，也不错，转来学习。

#include <iostream>
using namespace std;

char a[50],b[50];
bool check(char a[])
{
	int i,j,flag;  
    flag=i=j=0;
    for(i=0;a[i]!='\0';i++)  
    {         
        if(a[i]=='(')  
		{
			b[j++] = 1;				
		}
        if(a[i]==')')		
		{
			if(b[--j] != 1)
			{
				flag=1;
				break;
			}		
		}
        if(a[i]=='[')  
		{
			b[j++]=2;
		}
        if(a[i]==']')  
		{
			if(b[--j]!=2)
			{
				flag=1;
				break;
			}
		}
        if(a[i]=='{') 
		{
			b[j++]=3;
		}
        if(a[i]=='}')
		{
			if(b[--j]!=3)
			{
				flag=1;
				break;
			}
		}
    }  
    if(flag==0)  
	{
		return true;        
	}
    if(flag==1)  
	{
		return false;     
	}
}
 void main()  
 {  
	 char a[] = "(({[]})[]{})" ;
	 if( check(a) )
	 {
		 cout << "yes" <<endl;
	 }
	 else
	 {
		 cout << "No" <<endl;
	 }

 }