括号婚配

括号匹配

一，题目

       四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

二，解答

        解法一：左右括号成一对则抵消

                        可以将左括号看成1右括号看成 -1，然后对8个数进行全排列

                        对每个排列判断，是否符合条件，逐个相加，sum>=0直到遍历完该序列，符合条件则count++

                         如果出现sum<0则失败

       解法二：采用八位bit，从0000 0000 到 1111 1111遍历，遇到0加 -1遇到1加 1

                        如果加完该序列所有位等于0,且递加过程中sum始终大于零则符合条件

三，源码

// MatchNums.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include<iostream>
#include <vector>
using namespace std ;
void Print(vector<char> v)
{
 for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg)
  cout<<*beg<<" ";
 cout<<endl;
}
void MatchNums(int nSize,int nLen,vector<char> &v)
{
 int nLeftBrackets=0;
 int nRightBrackets=0;
 for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg)
 {
  if(*beg=='(')
   nLeftBrackets++;
  else
   nRightBrackets++;

  if(nLeftBrackets==3)
   nLeftBrackets=3;
  if(nRightBrackets>nLeftBrackets)
   return;
  if(nLeftBrackets+nRightBrackets==nSize&&nLeftBrackets==nRightBrackets)
   Print(v);
 }

 if (nLen>0)
 {
  v.push_back('(');
  MatchNums(nSize,nLen-1,v);
  v.pop_back();
  v.push_back(')');
  MatchNums(nSize,nLen-1,v);
  v.pop_back();
 }
}
int main()
{
 vector <char> v;
 int n=4;
 MatchNums(n,n,v);

 system("pause");
 return 0;
}

// MatchNums.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include<iostream>#include <vector>using namespace std ;void Print(vector<char> v){for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg)cout<<*beg<<" ";cout<<endl;}void MatchNums(int nSize,int nLen,vector<char> &v){int nLeftBrackets=0;int nRightBrackets=0;for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg){if(*beg=='(')nLeftBrackets++;elsenRightBrackets++;if(nLeftBrackets==3)nLeftBrackets=3;if(nRightBrackets>nLeftBrackets)return;if(nLeftBrackets+nRightBrackets==nSize&&nLeftBrackets==nRightBrackets)Print(v);}if (nLen>0){v.push_back('(');MatchNums(nSize,nLen-1,v);v.pop_back();v.push_back(')');MatchNums(nSize,nLen-1,v);v.pop_back();}}int main(){vector <char> v;int n=4;MatchNums(n,n,v);system("pause");return 0;}