3

重複の可能性：
基本的な再帰、バランスのとれた括弧の確認

最近、アルゴリズム設計マニュアルでこの問題に遭遇しました。スタックベースのアルゴリズムは非常に簡単ですが、この問題に対して再帰的なアルゴリズムを作成したいと思います。しかし、再帰の初心者であるため、多くのことを思い付くことができません。誰かがこの問題で私を助けますか？

PS私はこの質問について他の投稿を見ただけですが、それらはあまり効率的ではなく、そうである人は非常に説明的ではありません。

4

1 に答える 1

12

背景：括弧のバランスが取れているかどうかを見つける問題は、実際には決定問題であり、それを記述する言語1は文脈自由言語です。 文脈自由文法は、スタック2
のオートマトンを使用して解析できます。

したがって、この問題に対して次の反復解を得ることができます。

iterative(str):
  stack <- empty stack
  for each char in str:
     if char is open paranthesis: //push the paranhtesis to stack
         stack.push(char)
     else if char is close parantesis: //if close paranthesis - check if it is closing an open parenthesis
         if stack.head() == matchingParanthesis(char):
            stack.pop()
         else: //if the closing parenthesis do not close anything previously opened, return false
             return false 
   //end of loop - check if all opened parenthesis were closed:
   return stack.isEmpty()

開いたスコープを表す括弧はスタックの先頭にあり、各閉じ括弧は、スタックの先頭を調べることで、適切な開いた括弧を閉じているかどうかを検証できます。

注：単一のタイプの括弧の場合、整数を使用してスタックを模倣できることは簡単にわかります（実際には数を数えるだけでよく、括弧のタイプは気にしないため）。

また、ループ+スタックアルゴリズムは実際には再帰に非常に似ているため、次の再帰アルゴリズムを導出できます。

checkValidty(str,currentParenthesis,currentIndex): 
//currentIndex is a common variable, changed by reference to affect all levels of recursion!
   while (currentIndex < str.size()):
      char <- str[currentIndex]
      currentIndex <- currentIndex + 1
      if char is open paranthesis: 
        //if the recursive call is unseccesfull - end the check, the answer is no
         if !checkValidity(str,char,currentIndex): 
            return false
      else if char is close parantesis: 
         if currentParenthesis == matchingParanthesis(char):
            return true
         else: //if the closing parenthesis do not close anything previously opened, return false
             return false 
   //end of loop - check if all opened parenthesis were closed:
   return currentParenthesis == nil

checkValidty(str,nil,0)-で呼び出します。ここstrで、は検証された文字列です。

反復アルゴリズムと再帰アルゴリズムが実際には同じであることが簡単にわかります。2番目のアルゴリズムでは、呼び出しスタックと変数lastParenthesisをスタックの先頭として使用します。

（1）言語は、問題によって受け入れられるすべての単語です。たとえば(w)、言語で)w(はありませんが、そうではありません。
（2）正確には：一部のグラマーは非決定性オートマトンとスタックを必要としますが、これはもう少し理論的なことであり、ここでは問題ではありません。

于 2012-09-22T06:30:24.957 に答える