poj 1141 括號匹配

poj 1141 括號匹配

根據“黑書”的思路，定義：

d[i][j]為輸入序列從下標i到下標j最少需要加多少括號才能成為合法序列。0<=i<=j

c[i][j]為輸入序列從下標i到下標j的斷開位置，如果沒有斷開則為-1。

當i==j時，d[i][j]為1

當s[i]=='(' && s[j]==')' 或者 s[i]=='[' && s[j]==']'時，d[i][j]=d[i+1][j-1]

否則d[i][j]=min{d[i][k]+d[k+1][j]} i<=k

采用遞推方式計算d[i][j]

輸出結果時采用遞歸方式輸出print(0, len-1)

輸出函數定義為print(int i, int j)，表示輸出從下標i到下標j的合法序列

當i>j時，直接返回，不需要輸出

當i==j時，d[i][j]為1，至少要加一個括號，如果s[i]為'(' 或者')'，輸出"()"，否則輸出"[]"

當i>j時，如果c[i][j]>=0，說明從i到j斷開了，則遞歸調用print(i, c[i][j]);和print(c[i][j]+1, j);

如果c[i][j]<0，說明沒有斷開，如果s[i]=='(' 則輸出'('、 print(i+1, j-1); 和")"

否則輸出"[" print(i+1, j-1);和"]"

#include 
#include 
#include 
#include 

using namespace std;
int dp[100][100];
int c[100][100]={-1};
int len;
char s[1000];

void cal(){
	for(int i=0;ij)return ;
	if(i==j){
		if(s[i]=='('||s[j]==')')
		cout<<"()";
		else
		cout<<"[]";
	}
	if(i=0){
			print(i,c[i][j]);
			print(c[i][j]+1,j);
		}
		else {
			if(s[i]=='('){
				cout<<"(";
				print(i+1,j-1);
				cout<<")";
			}
			else if(s[i]=='['){
				cout<<"[";
				print(i+1,j-1);
				cout<<"]";
			}
		}
	}
}

int main(){
	cin>>s;
	len=strlen(s);
	cal();
	print(0,len-1);
	puts("");
}