[LeetCode] Medium - 150 Evaluate Reverse Polish Notation

▶150 - Evaluate Reverse Polish Notation

▶문제

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Reverse Polish notation - Wikipedia

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

 

▶예제

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

728x90

▶풀이

stack 리스트를 하나 만들어 준다.그다음 tokens에서 하나씩 가지고 오면서 operators인지 숫자인지 판단하고, 숫자라면 append 해준다.operators라면, stack에서 숫자 두 개를 pop 해서 가지고 온 후에 계산을 하고 다시 append 해주면 된다.

 

이때 pop를 먼저 하는 쪽이 뒤에서 계산되는 숫자라는 걸 까먹으면 안 된다.아무 생각 없이 a, b순서로 append 해주고 계산은 a + b 해서 자꾸 틀렸다.덧셈이나 곱셈은 상관없지만 뺄셈이나 나눗셈에서는 문제가 생겼다.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        result = []
        operators = {'+', '-', '*', '/'}

        if len(tokens) == 1: 
            return int(tokens[0])

        for t in tokens:
            if t not in operators:
                result.append(int(t))
            else:
                b = result.pop()
                a = result.pop()

                if t == '+':
                    result.append(a + b)
                elif t == '-':
                    result.append(a - b)
                elif t == '*':
                    result.append(a * b)
                elif t == '/':
                    result.append(int(a / b))

        return result.pop()

그 부분 신경 써서 하니까, runtime은 적당히 잘 나왔다.

아, 나눗셈할 때도 int를 해준후에 넣어주어야 한다.