首页 > 试题广场 >

括号配对问题

[编程题]括号配对问题
  • 热度指数:8159 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个字符串 S,请检查字符串中仅由括号字符 `[`、`]`、`(`、`)` 组成的子序列是否构成合法括号序列。合法括号序列的定义如下:

\hspace{23pt}\bullet\,空序列是合法括号序列;

\hspace{23pt}\bullet\,如果 A 是合法括号序列,则 `(A)` 和 `[A]` 都是合法括号序列;

\hspace{23pt}\bullet\,如果 AB 都是合法括号序列,则它们的拼接 AB 也是合法括号序列。

\hspace{15pt}字符串 S 可能包含其他字符,但只需考虑括号部分,忽略其他字符。

输入描述:
\hspace{15pt}在一行中输入一个字符串 S,长度 1 \leqq |S| \leqq 10^4,由可见字符组成。


输出描述:
\hspace{15pt}如果字符串 S 中的括号部分能构成合法括号序列,则输出 `true`;否则输出 `false`。
示例1

输入

abcd(])[efg

输出

false

说明

提取括号 `(`、`)`、`[`、`]` 后为 `(])[`,不是合法括号序列。
示例2

输入

a[x(y)z]

输出

true

说明

提取括号后为 `[()]`,是合法括号序列。

这道题你会答吗?花几分钟告诉大家答案吧!