Evaluate Reverse Polish Notation

문제

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

풀이

• 후위표기법으로 작성된 수식을 스택을 이용하여 계산하는 문제이다.
• 연산자(+, -, /, *)를 만나면 계산후 다시 스택에 push
  • -와 /의 경우 순서 주의
    • /는 마이너스 나누기 주의
• 피연산자(숫자)라면, 스택에 push

수도 코드

stack = []

for tokens의 처음부터 끝까지:
	if token이 연산자라면:
    	stack.append(stack.pop() 연산 stack.pop())
    else: # 숫자
    	stack.append(int(token))
return stack.top()

Solution Python (Runtime: 62ms)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        OPS = {
            '+': lambda x, y: x + y,
            '-': lambda x, y: y - x,
            '*': lambda x, y: x * y,
            '/': lambda x, y: int(y / x)
        }
        stack = []

        for token in tokens:
            if token in '+-*/':
                stack.append(OPS[token](stack.pop(), stack.pop()))
                continue
            stack.append(int(token))
        
        return stack[-1]

마이너스 나누기 부분을 처리하는데 제일 오래걸렸다. 6 / -132일 때, 로컬의 파이참으로 계산했을때 0으로 정상 출력되었지만, leetcode에서는 -1이라고 처리되었다. (python2와 python3에서 차이가 발생하는듯?)

• python2: 정수끼리 나눌 때 정수형 리턴
• python3: 정수끼리 나눌 때 실수형 리턴