[LC] 150. Evaluate Reverse Polish Notation

[seungriyou]

https://leetcode.com/problems/evaluate-reverse-polish-notation/

Approach

연산자를 적용해야 하므로 stack을 이용한다. tokens를 순회하며 다음과 같이 동작한다.

1. token이 연산자라면, stack에서 두 번 pop() 하여 두 값에 대해 연산한다. (stack에 먼저 push된 값이 첫 번째 operand)
2. 아니라면, token을 int로 변환 후 stack에 push 한다.

위 과정을 완료한 뒤 stack에 남아있는 값이 결과 값이 된다.

[!note] 연산자에 대해, 수행해야 하는 계산 동작을 dict & lambda 로 구현해두면 매우 편리하다! (if 문 불필요)

Tip 💡

파이썬에서는 a // b와 int(a / b)가 다음과 같은 차이점이 있다. (본 문제에서는 int(x / y)를 택해야 한다!)

• a와 b가 부호가 같다면, 결과가 동일하다.

  >>> x = 5
  >>> y = 2
  >>> x // y
  2
  >>> int(x / y)
  2

• a와 b가 부호가 다르다면, 결과가 다르다!

  >>> x = -5
  >>> y = 2
  >>> x // y
  -3
  >>> int(x / y)
  -2

  [!caution] 즉, int(x / y)는 그냥 소수점 아래를 버려버리는 것이다!!

Complexity

• Time: O(n)
• Space: O(n)