TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1507
  • 题目
  • P1507【NK月赛 JUNE2012 E】做错的作业
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    小影(人名) 的数学作业错误百出.
    老师:“你作业的表达式里面只有n个括号,怎么就写错了这么多?”
    “n那么大,都到300了。”
    老师:“那第一个小题只有一个括号你都写错了,这怎么解释?你看,你就写了一个‘(’,明显漏掉了一个‘)’吧?”
    “这……”小影似乎很清楚的记得自己是写的“()”,可是现在怎么只剩下“(”了呢?
    老师:“你看别人某某,写的多好?十道题都做对了。这样吧,我不看你的计算结果了,只看你的括号匹配得正不正确,你今天之内把你的括号修改正确就可以了……”
    “嘿嘿……我把括号全部划掉不就全对了?”小影阴险地想。
    老师:“……不过有一个条件:你只能添加括号而不能把括号划掉,并且你只能添加最少数量的括号。”
    “天呐!”小影瘫倒了,要知道十个题目里面只有第一题很简单,其他的题目括号数目是巨多的。
    看来,只能请善良的你帮帮小影了。

    输入格式

    只有一行,为一个长度为n的字符串,代表小影作业中写的括号。其中有4类括号“()”“[]”“<>”“{}”,“(”和“)”匹配,“[”和“]”匹配,“<”和“>”匹配,“{”和“}”匹配,左括号必须在左,右括号必须在右,其他组合是不匹配的。两个匹配的括号中间可以夹有其他已经匹配的括号。如“([<{}>])(){}”就是匹配的。

    输出格式

    一个整数,为小影最少需要添加的括号数目。

    样例输入 1

    ([(]{})(<>))

    样例输出 1

    2

    样例输入 2

    []>][>]<({[]]{<){{{(})

    样例输出 2

    12

    样例输入 3

    []>][>]<({[]]

    样例输出 3

    7

    提示

    对于30%的数据,n<=50;
    对于100%的数据,n<=300


    来源  命题:Chyy(08级24班);审题:Cauchy(08级5班);数据:Chyy。