带星号的双类型括号匹配

解题思路

• 我们要判断只包含 (、)、<、>、* 的字符串是否为有效括号串。不同于常见题目，本题中 * 只能充当右括号（可在自身位置变成 ) 或 >），不能当左括号或空字符。

• 关键约束

  1. 右括号必须与同类型左括号匹配；
  2. 匹配顺序必须满足栈的后进先出；
  3. * 必须全部被使用，并且只能匹配它左侧的某个尚未匹配的左括号。

题目内容

给定一个字符串 $s$，包含以下字符：$(,), <, >$ 和 $*$。其中字符 $*$ 可以变换成 ), $>$ 中的任意一个右括号。判断字符串是否有效，有效字符串需要满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。
4. 字符 $*$ 只能作为右括号使用，通过变换成合适的类型来匹配左括号。

输入描述

$1≤s.length≤10^4$

$s$ 仅由括号 $'()<> '$ 和 $'*'$ 组成

输出描述

字符串 $s$ 是有效字符串输出 $true$，否则输出 $false$ 。

样例1

输入

()

输出

true

样例2

输入

*)

输出

false