xfstart07
Get busy living or get busy dying
#include < iostream >
using   namespace  std;

#define  INF 0xFFFFFFF
int  N;
char  s[ 110 ];
int  f[ 110 ][ 110 ] = { 0 },p[ 110 ][ 110 ] = { 0 };
void   out ( int  x, int  y){
    
if (x > y)  return ;
    
if (x == y){
        
if (s[x] == ' ( ' || s[x] == ' ) ' )
            printf(
" () " );
        
else  printf( " [] " );
        
return ;
    }
    
if (p[x][y] > 0 ){
        
out (x,p[x][y]);
        
out (p[x][y] + 1 ,y);
    }
    
else   if (p[x][y] ==- 1 ){
        printf(
" %c " ,s[x]);
        
out (x + 1 ,y - 1 );
        printf(
" %c " ,s[y]);
    }
    
else   if (p[x][y] ==- 2 ){
        
if (s[x] == ' ( ' ){
            printf(
" ( " );
            
out (x + 1 ,y);
            printf(
" ) " );
        }
        
else {
            printf(
" [ " );
            
out (x + 1 ,y);
            printf(
" ] " );
        }
    }
    
else   if (p[x][y] ==- 3 ){
        
if (s[x] == ' ( ' ){
            printf(
" ( " );
            
out (x,y - 1 );
            printf(
" ) " );
        }
        
else {
            printf(
" [ " );
            
out (x,y - 1 );
            printf(
" ] " );
        }
    }
}
int  main()
{
    scanf(
" %s " ,s + 1 );
    N
= strlen(s + 1 );
    
for ( int  i = 1 ;i <= N; ++ i)
        f[i][i]
= 1 ;
    
for ( int  k = 1 ;k < N; ++ k)
        
for ( int  i = 1 ;i <= N - k; ++ i){
            
int  j = i + k;
            f[i][j]
= INF;
            
for ( int  t = i;t < j; ++ t)
                
if (f[i][j] > f[i][t] + f[t + 1 ][j]){
                    f[i][j]
= f[i][t] + f[t + 1 ][j];
                    p[i][j]
= t;
                }
            
if (s[i] == ' ( ' && s[j] == ' ) ' || s[i] == ' [ ' && s[j] == ' ] ' )
                
if (f[i][j] > f[i + 1 ][j - 1 ]){
                    f[i][j]
= f[i + 1 ][j - 1 ];
                    p[i][j]
=- 1 ;
                }
            
if (s[i] == ' ( ' || s[i] == ' [ ' )
                
if (f[i][j] > f[i + 1 ][j] + 1 ){
                    f[i][j]
= f[i + 1 ][j] + 1 ;
                    p[i][j]
=- 2 ;
                }
            
if (s[j] == ' ) ' || s[j] == ' ] ' )
                
if (f[i][j] > f[i][j - 1 ] + 1 ){
                    f[i][j]
= f[i][j - 1 ] + 1 ;
                    p[i][j]
=- 3 ;
                }
        }
    
// printf("%d\n",f[1][N]);
     out ( 1 ,N);
    printf(
" \n " );
    
return   0 ;
}





posted on 2009-06-18 10:40 xfstart07 阅读(254) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理