LeetCodeのEvaluate Reverse Polish Notation解いてみた

始めに

時間はかかったがMedium問題を初見で解けたのでまとめてみる。
LeetCodeを使い始めて1ヶ月だが実力不足を感じる日々
同じようにもがいてる人の一助になれば幸いです

ちなみにより良い解法は存在すると思うので色々とコメント頂けると勉強になります！

問題

問題は逆ポーランド記法の配列を計算して返す関数の作成
逆ポーランド記法？？と思った方もいると思うので軽く解説

["2","1","+","3","*"]
↓
(2 + 1) * 3 = 9

上記のように計算対象の後に演算子が来るようなものを逆ポーランド記法という。
逆ポーランド記法というのは後置記法とも呼ばれ、私たちが馴染みある記法は中置記法というらしい

この問題に出会わなければ知らなかった...

考察

こんな感じでスタックを使い、順番にオペランドをスタックに追加していき、直前の値と演算子で計算していけばいけそう

["2","1","+","3","*"]
↓
[2, 1] -> 2 + 1
↓ 3を追加
[3, 3] -> 3 * 3

答え9

• スタックを使い効率的に解く
• オペランドと演算子の判別
• 演算子の処理
• 除算の取り扱い

上記のポイントを意識しながら解いていく

解法

オペランドと演算子の判別

演算子以外はスタックに追加していく

stack = []
for token in tokens:
    if token not in  ["+", "-", "*", "/"]:
        stack.append(token)

各演算子の結果をスタックに追加

スタックの直前の値ともう一つ前の値をpopして各演算子で計算
この時、引き算と割り算のみx,yの順番を気をつける必要がある

elif token == "+":
    x,y = int(stack.pop()), int(stack.pop())
    stack.append(x + y)
elif token == "-":
    x,y = int(stack.pop()), int(stack.pop())
    stack.append(y - x)
elif token == "*":
    x,y = int(stack.pop()), int(stack.pop())
    stack.append(x * y)
elif token == "/":
    x,y = int(stack.pop()), int(stack.pop())
    stack.append(int(y / x))

問題文にもある通り、除算の時は切り捨てになるようにする

stack.append(int(y / x))

あとはスタックの先頭をpopすればOK
いかに全文載せておきます

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in  ["+", "-", "*", "/"]:
                stack.append(token)
            elif token == "+":
                x,y = int(stack.pop()), int(stack.pop())
                stack.append(x + y)
            elif token == "-":
                x,y = int(stack.pop()), int(stack.pop())
                stack.append(y - x)
            elif token == "*":
                x,y = int(stack.pop()), int(stack.pop())
                stack.append(x * y)
            elif token == "/":
                x,y = int(stack.pop()), int(stack.pop())
                stack.append(int(y / x))

        return int(stack.pop())

感想

逆ポーランド式とは初対面ですが、　それほど難しい訳では無かったので初見で解けました。
Mediumは初見で突破できる問題が少なかったので多少は成長したのかも？
この問題でLeetCodeで解いた問題数が50問を超えたので振り返りながら精進してみよう