Week 1-2. [Stack] 150. Evaluate Reverse Polish Notation (Python)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Evaluate Reverse Polish Notation - LeetCode

후위표기식을 계산하라.

• 유효한 연산자는 +, -, *, / 이다.
• 두 정수 사이 나눗셈은 always truncates toward zero
• 0으로 나누는 일은 없다.

🔎 어떤 식으로 접근했는가?

주어진 tokens 중 숫자는 무조건 스택에 집어 넣는다. 연산자는 스택에서 숫자를 꺼내 계산한 뒤 결과를 스택에 집어 넣는다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

반복문을 이용해 tokens를 순회할 것이다.

 

📝 의사 코드

tokens에서 값을 하나씩 꺼낸다:
	if (연산자가 아니라면):
    	스택에 넣는다.
    else:
    	스택의 top에 있는 값 두 개를 가져와 해당 연산자와 계산한다.
        계산한 결과를 stack에 넣는다.
        
반복문이 종료된 후 stack[0]을 반환한다.

 

🎯 구현 코드

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stk = []
        for x in tokens:
            if x not in '+-*/':
                stk.append(x)
            else:
                a, b = stk.pop(), stk.pop()
                tmp = eval(str(b) + x + str(a))
                if x == '/':
                    if int(a) < 0 or int(b) < 0:
                        stk.append(round(tmp))
                    else:
                        stk.append(eval(str(b) + '//' + str(a)))
                else:
                    stk.append(tmp)

        return int(stk[0])

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

linear search 이기 때문에 시간 복잡도는 O(N)이다.

 

✍️ 성능 회고

성능은 나쁘지 않으나 모든 히든 케이스를 통과하지 못한다.

 

💡 무엇을/어떻게 개선할 수 있을까?

tokens에 음수도 존재하기 때문에, 음수 계산에서 의도치 않은 결과가 나온 것 같다.

 

예를 들면, 6/(-132)는 실제로 -0.045454545454545456 이다. 우리가 의도했던 것은 이를 0으로 계산하는 것이다.

처음에는 6//(-132)라고 적용하였으나 이는 의도와 다르게 -1이 나온다.

따라서 A//B 에서 A 혹은 B가 음수일 경우 예외처리를 해주었다.

 

하지만 그 외의 어떤 논리 오류가 있는지는 알아내지 못했다ㅠ

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

우선, 매개변수로 주어지는 tokens의 요소(=x)들은 str이기 때문에 처음에 스택에 넣어줄 때 int(x)로 넣어주면 아래에서 편하다.

스택에서 두 개를 pop하여 계산하는 것은 내 코드와 같지만, 아래에서는 eval을 사용하지 않고 조건문을 이용해 직접 계산했다.

특히 음수가 포함된 나눗셈을 int(b/a)로 계산하였다.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stk = []
        for x in tokens:
            if x not in '+-*/':
                stk.append(int(x))
            else:
                a, b = stk.pop(), stk.pop()
                if x == '+':
                    stk.append(b+a)
                elif x == '-':
                    stk.append(b-a)
                elif x == '*':
                    stk.append(b*a)
                else:
                    stk.append(int(b/a))

        return int(stk[0])

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

마찬가지로 O(N)의 시간 복잡도를 가진다.

 

느낀 점

숫자는 스택에 넣고, 연산자는 스택에서 꺼내 계산한다는 사고는 좋았으나,

구현에서 논리 오류가 있었던 것 같아 아쉽다.