第二回 PAST J - 文字列解析

問題原文

atcoder.jp

問題要旨

英子文字と (, ) からなる「括弧の対応が取れているような」文字列 が与えられる。
また、 を 文字列 を反転した文字列とする。
以下の操作を可能中桐繰り返し行った時の、最終的な を求めよ。

• (, ) を含まない の部分文字列 を、 で置きかえる。

• 

• 最終的な の長さは1000以下。

解法

逆ポーランド記法を勉強したことがあれば、スタックに積んでいくのが思い浮かびます。
あるいは、

atcoder.jp

を解いておくとパッと思い浮かびます。

経験が無い場合には、
1. 内側の括弧から処理が入る。
2. ) がきた時に処理が入る。
3. ) がきた時には、 ( が出るまできたみちを戻りたい。

という気持ちになると解けるのかなぁという感じです。

実装

S = input()
stack = []
 
for s in S:
    if s != ')':
        stack.append(s)
    else:
        r = ''
        while stack[-1] != '(':
            r += stack.pop()
        stack.pop()
        stack.extend(list(r[::-1]))
        stack.extend(list(r))
 
print(''.join(stack))

感想

スタックうまく使えると自尊心が満たされた気がします。