【问题描述】
我们用以下规则定义一个合法的括号序列:
(1)空序列是合法的
(2)假如S是一个合法的序列,则 (S) 和[S]都是合法的
(3)假如A 和 B 都是合法的,那么AB和BA也是合法的
例如以下是合法的括号序列:
(), [], (()), ([]), ()[], ()[()]
以下是不合法括号序列的:
(, [, ], )(, ([]), ([()
现在给定一些由'(', ')', '[', ,']'构成的序列 ,请添加尽量少的括号,得到一个合法的括号序列。
【输入】
输入包括号序列S。含最多100个字符(四种字符: '(', ')', '[' and ']') ,都放在一行,中间没有其他多余字符。
【输出】
使括号序列S成为合法序列需要添加最少的括号数量。
【样例输入】
([()
【样例输出】
2
【样例说明】
最少添加2个括号可以得到合法的序列:()[()]或([()])
【数据范围】S的长度<=100 (最多100个字符)。 解题思路
program kuohao;
uses math;
const maxn=;
var
f:Array[..maxn,..maxn] of longint;
s:string;
p,i,j,k,min,flag:Longint;
begin
readln(s);
for i:= to length(s) do f[i,i]:=;
for p:= to length(s) do//枚举次数
for i:= to length(s)-p do//枚举起点
begin
min:=maxlongint;
flag:=;
j:=i+p;
if ((s[i]='(') and(s[j]=')')) or((s[i]='[')and (s[j]=']'))
then
begin
f[i,j]:=f[i+,j-];
flag:=;
end;
for k:=i to j- do//枚举决策
begin
if f[i,k]+f[k+,j]<min then min:=f[i,k]+f[k+,j];
end;
if (min<f[i,j]) or (flag=) then f[i,j]:=min;
writeln(f[,length(s)]);
end.