アルゴリズムとデータ構造

対応する括弧を見つける

開き括弧と閉じ括弧で構成された文字列が与えられたとき、それぞれの閉じ括弧に対応する開き括弧を見つける問題です。与えられる括弧列は常に正しい形式であることが保証されています。

入力

入力は単一の行 s で与えられます (1 ≤ |s| ≤ )。

出力

各閉じ括弧に対応する開き括弧のインデックスを、スペース区切りで出力してください。

例

入力
出力
(()())
2 4 1
((()))
3 2 1
()()()
1 3 5

解説

  1. (()())
      2. Bracket
      (
      (
      )
      (
      )
      )
      Index
      1
      2
      3
      4
      5
      6
      Opening index
      -
      -
      2
      -
      4
      1
  1. ((()))
      2. Bracket
      (
      (
      (
      )
      )
      )
      Index
      1
      2
      3
      4
      5
      6
      Opening index
      -
      -
      -
      3
      2
      1
  1. ()()()
      2. Bracket
      (
      )
      (
      )
      (
      )
      Index
      1
      2
      3
      4
      5
      6
      Opening index
      -
      1
      -
      3
      -
      5
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue