スタックの応用

スタックを使って、逆ポーランド記法で書かれた数式の計算法を紹介しました。
今度は、括弧の整合性判定をしてみます。

括弧の整合性とは、括弧の開き括弧（左側）と閉じ括弧（右側）の数があっているかどうかの判定です。
例えば
[({()()})]
は整合性があり、
[({())})]
は不整合である。

括弧の対応がとれているかどうかは、記号列を左から右へと読んでいったときに、直前の開き括弧 ( { [ どれかがが今注目している同じ種類の閉じ括弧 ] } ) に対応しているかを調べればよい。

アルゴリズム：括弧の整合性判定

1. 文字列のスタックSを宣言する
2. 文字列表現を探索する
   1. もし現在の文字が開始タグであればスタックにプッシュ
   2. もし現在の文字が閉じタグであればスタックからポップを実行し、ポップされた文字が開始タグと一致した場合整合性がとれている、そうでない場合は不整合
3. 全ての探索が終わった後、もしスタックに開始タグが残っていればそれも不整合である

んー。みづらい。。。

  [({()()})]
  ^ Push('[')
  | '[' | - | - | - | - | - | - | - | - | - | - | - |  
  ({()()})]
  ^ Push('(')
  | '(' | '[' | - | - | - | - | - | - | - | - | - | - |
  {()()})]
  ^ Push('{')
  | '{' | '(' | '[' | - | - | - | - | - | - | - | - | - |
  ()()})]
  ^ Push('(')
  | '(' | '{' | '(' | '[' | - | - | - | - | - | - | - | - | 
  ) ()})]
  ^ Pop()
  '(' ←　| '{' | '(' | '[' | - | - | - | - | - | - | - | - | - | 
  '('　’)' :整合性OK
  ()})]
  ^ Push('(')
  | '(' | '{' | '(' | '[' | - | - | - | - | - | - | - | - | 
  ) })]
  ^ Pop()
  '(' ←　| '{' | '(' | '[' | - | - | - | - | - | - | - | - | - | 
  '(' ')' ：整合性OK
  } )]
  ^　Pop()
  '{' ←　| '(' | '[' | - | - | - | - | - | - | - | - | - | - | 
  '{' '}' :整合性OK
   ) ]
   ^ Pop()
   '(' ←　| '[' | - | - | - | - | - | - | - | - | - | - | - |
   '(' ')'　：整合性OK
   ]
   ^ Pop()
   '[' ←　 | - | - | - | - | - | - | - | - | - | - | - |　- |
   '[' ']' :整合性OK
   
   文字列全て走査完了
   | - | - | - | - | - | - | - | - | - | - | - |　- |　空のスタック

その１．開きかっこが足らん？
({)})
  | - | - | - | - | - | - | - | - | - | - | - | - |  空のスタックを用意
({)})
^ Push('(')
  | '(' | - | - | - | - | - | - | - | - | - | - | - | 
{)})
^ Push('{')
  | '{' | '(' | - | - | - | - | - | - | - | - | - | - |
) })
^ Pop()
 '{' ←　| '(' | - | - | - | - | - | - | - | - | - | - |　- |
'{'　')' :不整合(´;ω;｀)

その２．閉じかっこが足らん？
({)
  | - | - | - | - | - | - | - | - | - | - | - | - |  空のスタックを用意
({)
^ Push('(')
  | '(' | - | - | - | - | - | - | - | - | - | - | - |
{)
^ Push('{')
  | '{' | '(' | - | - | - | - | - | - | - | - | - | - |
)
^ Pop()
'{' ← | '(' | - | - | - | - | - | - | - | - | - | - | - |
'{' ')' ：不整合(´；ω；`)ｳｩｩ