====== スタックの応用 ======
スタックを使って、逆ポーランド記法で書かれた数式の計算法を紹介しました。\\
今度は、括弧の整合性判定をしてみます。\\
\\
== 括弧の整合性判定 ==
括弧の整合性とは、括弧の開き括弧（左側）と閉じ括弧（右側）の数があっているかどうかの判定です。\\
例えば\\
**[({()()})]**\\
は整合性があり、\\
**[({())})]**\\
は不整合である。

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

==== アルゴリズム ====
アルゴリズム：括弧の整合性判定
  - 文字列のスタックSを宣言する
  - 文字列表現を探索する
    - もし現在の文字が開始タグであればスタックにプッシュ
    - もし現在の文字が閉じタグであればスタックからポップを実行し、ポップされた文字が開始タグと一致した場合整合性がとれている、そうでない場合は不整合
  - 全ての探索が終わった後、もしスタックに開始タグが残っていればそれも不整合である

==== 例題 ====
んー。みづらい。。。
== 整合性ありの場合 ==

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



== 不整合な場合 ==


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

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

</code>