問題文：
https://leetcode.com/problems/valid-parentheses/
正解者さん：
https://leetcode.com/problems/valid-parentheses/discuss/9203/Simple-Python-solution-with-stack
class Solution:
# @return a boolean
def isValid(self, s):
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []
【ぷよぷよみたいに括弧同士を相殺するプログラム】
まず、
Input: s = "()"
Output: true
とする。
dict = {"]":"[", "}":"{", ")":"("}
⇒今後inputされる全ての括弧を先に辞書型で作成しておく。
for char in s:
⇒s = "()"をcharに入れていく間に下のコードを実行する。
if char in dict.values():
stack.append(char)
⇒もしも0回目のループ時に、dict内のvalue(右側の値)と同じものがcharに入っていた場合、
ループ外に用意しておいたstackリストの中に、char(s内の0番目："(")を入れる。
(0回目のループでは、charに入った要素が"("であったため、このif文が実行されて、stack = ["("]となる。)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
⇒あるいは、もしもdict内のkey(左側の値)と同じものがcharに入っていた場合、
次のifを実行する。
もしも、stack内が空っぽだった場合、
または、dict内のcharと同じ記号が、stackリストの最後の要素を消した時の残った要素と違っていた場合、
Falseを返す。
※このif文が読み込まれた時点で、合っているかどうかに関わらず、stack.pop()が発動されて、stackリストの最後の要素が消される。
(0回目のループでは、すでにif char in dict.values():に当てはまっているため実行はされない。)
次の1回目のループでは、charに入る要素は")"である。
dict内のkeyと同じのため、elif char in dict.keys():が実行される。
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
⇒dict内のkey(左側の値)と同じものがcharに入っているため、
次のifを実行する。
もしも、stack内が空っぽだった場合、
または、dict内のcharと同じ記号が、stackリストの最後を消した時の要素と違っていた場合、
Falseを返す。
しかし、1回目のループでも、このif文はどちらの条件とも当てはまらない。
したがって、このif文を読み込んだらstack.pop()が発動されて、
stackリストの最後の要素が消されたまま、最後のreturn stack == []が実行される。
return stack == []
⇒stackが[]と同じだった場合、Trueを返す。
つまり上のループ文で、ぷよぷよみたいに"("、")"が揃って相殺されていたら、stackリストが空っぽになるはず。
だから、もしstackが空っぽなら全部括弧が揃ってるからTrueだよ！というわけである。