20. Valid Parentheses Easyの解説

問題文：
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だよ！というわけである。