某東機試第二題

題目描述

合法的括号比對序列被定義為

1 空串“”是合法的括号序列

2如果“X”和“Y”是合法的序列，那麼“XY”也是一個合法的括号序列

3如果“X”是一個合法的序列，那麼“（X)”也是一個合法的括号序列

4每個合法的括号序列都可以由上面的規則生成

例如“”，“（）”，“（）（）（）”，“（（）（））”，“（（（（））））”都是合法的。東東現在有一個合法的括号序列s，一次移除操作分為兩步

1移除序列s中第一個左括号

2移除序列s中任意一個右括号，保證操作之後s還是一個合法的括号序列

東東現在想知道使用上述的移除操作有多少種方案可以把序列s變為空

如果兩個方案中有一次移除操作移除的是不同的右括号就認為是不同的方案

例如 s="(((())))"輸出24，第一次有4種情況，第二次有三種情況，依次類推有4*3*3*1=24

輸入描述

輸入包括一行，一行合法的括号序列s,序列長度length(2<=length<=20)

輸出一個整數表示方案數

示例1

輸入

（（（（））））

輸出

24

#include<stdio.h>
#include<string.h> 
using namespace std;
 bool judge( char str2[]){
 	char hel[20];
 	int coul=0; ///當作左邊棧 
 	char her[20];
	int length2=strlen(str2); 
	int i=0;
	while(i<length2){
		if(str2[i]=='('){
			hel[coul++]='('; 
		}else if(str2[i]==')'){
			if(coul==0)
			return false;
			else coul--;
		}
		i++;
	} 
	if(coul!=0)  return false;
	
	return true;
 }
int main(){
	char str[20];
	while(scanf("%s",str)!=EOF){
		if(judge(str)==false)
		printf("0\n");
		else{
			int length=strlen(str);
			int ans=1;
			int poi=-1;
		for(int i=0;i<length;i++){
			   int count=0;
			   str[i]='a'; 
			for(int j=i+1;j<length;j++){
				if(str[j]==')'){
					str[j]='a';
					if(judge(str)==true){
						count++;
						poi=j;
					}
					str[j]=')';
				}
			}  
			   str[poi]='a';
			   if(count!=0)
			   ans=ans*count;
		}
		  printf("%d\n",ans);
		}
		
	}
	return 0;
}