当前位置:首页 > 数据结构 > > 正文
SSOJ2460字符串匹配问题
2566+

题目大意:字符串中只含有括号()[]<>{},判断输入的字符串中括号是否匹配。如果括号有相互包含的形式,从内到外必须是<>,(),[],{}。

题目描述

字符串中只含有括号 ()[]   <>  {},判断输入的字符串中括号是否匹配。如果括号有相互包含的形式,从内到外必须是<>,(),[],{},例如,[()],输出:YES,而输入([])、([)]都应该输出NO。

输入

第1行为一个整数n,表示以下有多少个由括号组成的字符串。接下来的n行,每一行都是一个由括号组成的长度不超过255的字符串。

输出

输出n行,每行都是YES或NO

样例输入

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

样例输出

YES
YES
YES
YES
YES

解题思路

遇到左括号,如果符合要求,就加入栈中:<前面可以是<([{,任意左括号都可以;(前面可以是([{,不能是<;[前面可以是[{,不能是<(,即≥[;{前面可以是{,即≥{。

遇到右括号,如果前面有对应的左括号,则匹配后去掉该对括号:若能匹配,左右括号之和除以2再加1即为右括号,详见ASCII编码表。

遇到不符合要求的,退出循环。

最后根据n的值判断是否匹配成功。

程序实现

About

坚决不Copy代码!

本文标签:,,

SSOJ2460字符串匹配问题:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!