[리트코드] 150. Evaluate Reverse Polish Notation

문제

https://leetcode.com/problems/evaluate-reverse-polish-notation/?envType=study-plan-v2&envId=top-interview-150

Example 1:

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

Example 2:

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

Example 3:

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

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
  
  

---

✔ 문제접근 #1 스택[통과] ⭕

Intuition
스택을 사용하여 연산자가 들어왔을 때 연산한다.

Algorithm

모든 token 연산내역들을 순회하며 연산자가 들어왔을 때는 스택의 상단 두개의 데이터를 꺼내어 연산하고 연산결과를 stack에 삽입한다. 만약 그냥 숫자가 들어왔다면 곧바로 stack에 삽입한다.

 

    def evalRPN(self, tokens: List[str]) -> int:
        
        stack = []
        for token in tokens:
            if token == "/":
                num2, num1  = stack.pop(), stack.pop()
                stack.append(int(num1/num2))
            elif token == "*":
                num2, num1  = stack.pop(), stack.pop()
                stack.append(int(num1*num2))
            elif token == "+":
                num2, num1  = stack.pop(), stack.pop()
                stack.append(int(num1+num2))
            elif token == "-":
                num2, num1  = stack.pop(), stack.pop()
                stack.append(int(num1-num2))
        
            else:
                stack.append(int(token))
                
        return stack[-1]

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • 배열을 순차탐색 O(N)
  • 스택의 삽입, 삭제 연산 O(1)
  • 그러므로 전체시작복잡도 : O(N*1) = O(N)

• 공간복잡도 : O(N)
  
  • 연산데이터를 담을 stack을 사용한다.

---

기타풀이 및 회고

문제 요구사항에 0으로 나누는 일이 없다고했기 때문에 따로 주의를 해주지는 않았다. 하지만 나눗셈 연산이 있는 경우는 항상 주의해야한다.