#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 阅读(244)
评论(0) 编辑 收藏 引用 所属分类:
代码库