LeetCode-150 Evaluate Reverse Polish Notation 파이썬 문제 풀이

Evaluate Reverse Polish Notation - LeetCode

문제

역폴란드 표기법으로 작성된 계산식을 푸는 문제입니다. 배열 안에 숫자와 연산자가 입력되어있고, 역폴란드 표기법에 맞게 계산하면 됩니다.

 

풀이

역폴란드 표기법은 우리가 사용하는 중위 표기법과는 반대로 계산됩니다.

1. 배열을 순회하며 숫자를 만날 경우 postfixResult 배열에 추가합니다.

2. 연산자를 만날경우 postfixResult를 stack으로 생각하였을때 가장 상단의 값 두개를 pop하여 연산합니다.

3. 연산 결과를 다시 postfixResult에 추가합니다.

 

처음에는 tokens를 reverse하여 하나씩 해결하면 될 것이라 생각했지만, 이 경우 먼저 계산되어야 하는 부분들이 고려되지 않을 수 있어 실패 했습니다..

 

또, 나누기 연산 시 정수가 아닐 경우를 생각하지 못하고 단순히 나누기 연산을 하였을 때 특정 케이스에서 정답보다 1 작게 나오는 오류가 있었습니다. 나누기 연산시 연산 결과가 정수가 아닌 경우도 있을 수 있기 때문에 나누기 연산시 float으로 반환된 결과를 int로 변경하여 postfixResult에 추가해주어야 합니다. 마찬가지로 결과값에도 int형으로 반환하여 출력합니다.

 

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

        for token in tokens:
            if token == '+':
                n1 = postfixResult.pop()
                n2 = postfixResult.pop()
                postfixResult.append(n1 + n2)
            elif token == '-':
                n1 = postfixResult.pop()
                n2 = postfixResult.pop()
                postfixResult.append(n2 - n1)
            elif token == '*':
                n1 = postfixResult.pop()
                n2 = postfixResult.pop()
                postfixResult.append(n2 * n1)
            elif token == '/':
                n1 = postfixResult.pop()
                n2 = postfixResult.pop()
                postfixResult.append(int(n2/ n1))
            else:
                postfixResult.append(int(token))
        return int(postfixResult[0])