かっこの変換(Programmers 60058)

🧑‍💻 这个变换

新開発者として

KACAに入社した「Con」は、先輩の開発者から作業任務を受け、他の開発者が作成したソースコードを分析し、問題を発見し修正するように要求された.ソースコードをコンパイルしてログを表示すると、ほとんどのソースコードのカッコがペアではない形式で記述されているため、エラーが発生します.

変更するソースファイルが多すぎるため、conは次のプログラムの開発を検討しています.

用語定義

文字列が

"("および")のみで構成され、"("の数と")の数が同じである場合は、バランスカッコ文字列と呼ばれます.

とここで「」(「和」)の括弧が一致している場合は、正しい括弧文字列と呼ばれます.

たとえば、「()」()などの文字列は、「カッコ文字列のバランス」ですが、「有効カッコ文字列」ではありません.

とは逆に、「()()」などの文字列は「バランスの取れた括弧文字列」であり、「正しい括弧文字列」でもある.

"("および")のみからなる文字列wが"バランス括弧文字列"である場合、以下の手順で"正しい括弧文字列"に変換できます.
入力

が空の文字列である場合、空の文字列が返されます.

文字列wを2つの「バランスカッコ」u,vに分割します.ただし、uは「バランスカッコ文字列」に区切ることはできず、vは空の文字列であってもよい.

文字列uが「正しい括弧文字列」である場合、ステップ1から文字列vの操作を開始します.

が完了したら、文字列をuに接続して戻ります.

文字列uが「正しいかっこ文字列」でない場合は、次の手順に従います.

の空の文字列では、最初の文字は「」です.

文字列vについては、ステップ1から再帰的に実行し、それを続行する.

「

」を貼り直します.

uの最初の文字と最後の文字を削除し、残りの文字列のカッコ方向を反転して後ろに貼り付けます.

生成された文字列

を返します.

パラメータとして

「バランスカッコ文字列」pが与えられた場合、解法関数を完了し、与えられたアルゴリズムで「正しいカッコ文字列」に変換された結果を返します.

パラメータの説明

pは、2または1000より長い偶数の「(」および「)」のみからなる文字列です.

文字列pを構成する「(」および「)」の数は常に同じである.

pがすでに「正しいカッコ文字列」である場合、戻ることができます.I/O例
presult"(()())()""(()())()"")(""()""()))((()""()(())()"

🧑‍💻 解決策

カッコが正しいかどうかを確認し、不正なブレークポイントを見つけるには関数が必要です.

正しくない部分に遭遇した場合、その部分から再貴関数で返却されます.

Replaceを使用してかっこを変換します.

🧑‍💻 コード#コード#

def correction(br):
   stack = []
   for b in br:
       if b == '(':
           stack.append(b)
       else:
           try:
               stack.pop()
           except:
               return False
   if len(stack) == 0:
       return True
   else:
       return False

# 분기점 만들어주기
def split_brack(br):
   cnt = 0
   for idx in range(len(br)):
       if br[idx] == '(':
           cnt += 1
       else:
           cnt -= 1
       if cnt == 0:
           return idx + 1
   return idx + 1

def solution(p):
   answer = ''
   if (p == "") or (correction(p) == True):
       return p

   idx = split_brack(p)
   u, v = p[:idx], p[idx:]

   if correction(u):
       answer = u + solution(v)
   else:
       answer = '(' + solution(v) + ')'
       u = u[1:-1].replace('(', 'a')
       u = u.replace(')', 'b')
       u = u.replace('a', ')')
       u = u.replace('b', '(')
       answer = answer + u

   return answer

🧑‍💻 総評

題から難点

人の後期から見ると、与えられた問題に従うのは難しい.

論理を実現する部分(特に補正関数部分)はまだよく知られていないので、暗記は避けるべきです.

は、「かっこ問題の修正」、「再帰関数」の実施が常に困難であることを明確にしている.

アルゴリズム問題の文字列が多く、把握しなければならない.