程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 1141 括號匹配

poj 1141 括號匹配

編輯:關於C++


根據“黑書”的思路,定義:

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("");
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved