対応のとれた括弧列
「正規括弧列」「正しい括弧列」「平衡括弧列」「バランスの取れた括弧列」などと呼ばれることもある。
形式的な定義
ここで、文字列$ s, tに対して、$ s + tを「$ sおよび$ tをこの順番で連結したもの」とする。
$ S_0 = \{""$ \}
すべての非負整数$ iに対して、$ S_{i + 1} = \{"("$ + s +")"$ , s + t | s, t \in S_i\}
ある文字列$ sが正規括弧列であるとは、ある整数$ iが存在し、$ s \in S_iであることと同値。
定義が壊れがち
判定
どの部分においても、そこまでに現れた(の数が)の数以上かつ、最後は同じになる
参考