CODEVS 3657 括号序列

【问题描述】

我们用以下规则定义一个合法的括号序列:

(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.


上一篇:Python全栈--6.1-match-search-findall-group(s)的区别以及计算器实例


下一篇:软件工程课程作业(二)--四则运算2改进版(c++)