スタック

問題

対応の取れているカッコ列 $ S $ があります。

$ S $ の何文字目と何文字目が対応しているかを、すべて出力して下さい。

解き方・ソースコード

この問題はスタックを使って簡単に解くことができます。

スタックとは、次の３種類のクエリを処理することができるデータ構造です。

🔹クエリ１：スタックの一番上に要素 $ x $ を追加する。
🔹クエリ２：スタックの一番上の要素を取得する。
🔹クエリ３：スタックの一番上の要素を削除する。

与えられたカッコ列 $ S $ を左から順番に見ていき開きカッコが何文字目にあるかをスタックに記録していきます。

閉じカッコが見つかった場合、スタックの一番上の開きかっこが対応するものとなります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
#--------- 入力例1 ---------
S = '(())()'
#--------- 入力例2 ---------
# S = 'list(map(int, input().split()))'
#---------------------------
# 左から順番に見ていく
# 文字列は 0 文字目から始まることに注意
Stack = []
for i in range(len(S)):
    if S[i] == '(':
        Stack.append(i + 1)
    if S[i] == ')':
        print('{}文字目と{}文字目'.format(Stack.pop(), i + 1))

[実行結果（入力例１）]

2文字目と3文字目
1文字目と4文字目
5文字目と6文字目

[実行結果（入力例２）]

20文字目と21文字目
28文字目と29文字目
9文字目と30文字目
5文字目と31文字目

開きカッコと閉じカッコの対応関係を確認することができました。