有效的括号

题目描述

给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串 s，请判断该字符串是否有效。

有效字符串需要满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

输入格式

输入一行，包含一个字符串 s。

输出格式

如果字符串有效，输出 true；否则输出 false。

数据范围

1 <= |s| <= 10^4

字符串 s 仅由 (、)、[、]、{、} 组成。

样例 1

输入

()

输出

true

样例 2

输入

()[]{}

输出

true

样例 3

输入

(]

输出

false

样例 4

输入

([])

输出

true