[LeetCode][Python] 150. Evaluate Reverse Polish Notation

- 문제 링크: https://leetcode.com/problems/evaluate-reverse-polish-notation/

- 난이도: Medium

 

Reverse Polish Notation(RPN)의 형식으로 주어지는 계산식을 계산하는 문제다. 이 노테이션은 Postfix notation 이라고도 부른다

계산 방법은 간단한데, 토큰이 operator(+-*/)인 경우, 스택에서 두개 꺼내서 계산하고, 토큰이 숫자라면 스택에 넣는다.

그렇게 계산이 끝나면 스택에는 최종 값이 하나만 남게 된다

 

The division between two integers always truncates toward zero.

주의할 점은 나누기시 소수점 처리인데, 소수점을 전부 버린다. 예를 들어 0.3이면 0, -3.9이면 -3 이런 식이다

float 캐스팅 규칙이 기억이 잘 안나서 아래 코드엔 나눠서 ceil, floor를 했는데.. 그냥 int로 캐스팅해도 똑같다. 이건 C++도 마찬가지.

 

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for t in tokens:
            if t in '+-*/':
                rhs = stack.pop()
                lhs = stack.pop()

                if t == '+':
                    res = lhs + rhs
                elif t == '-':
                    res = lhs - rhs
                elif t == '*':
                    res = lhs * rhs
                else: # /
                    div = lhs / rhs
                    if div < 0:
                        div = math.ceil(div)
                    else:
                        div = math.floor(div)
                    res = div
                stack.append(res)

            else: # num
                stack.append(int(t))

        return stack[0]