LeetCode[ 150 | Python ] Evaluate Reverse Polish Notation

문제

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

역폴란드 표기법을 통해 주어진 연산식의 결과를 반환해야하는 문제.

풀이

시도

실행 시간 : 94ms
메모리 : 15.5MB

역폴란드 표기법은 연산자를 만나면 이전에 등장한 피연산자 2개를 사용해 계산한다.
이에 맞게 코드를 작성했다.

1. 주어진 토큰 tokens를 순회한다.
   1. 순회한 토큰이 숫자인 경우 스택에 저장한다. 이 때, 음수를 고려하여 길이가 2 이상이 되는 토큰을 저장한다.
   2. 숫자가 아닌 경우 스택에서 pop 연산을 두번 수행해 피연산자들을 추출한다.
   3. 문자열을 수식으로 계산하기 위해 eval 함수를 사용해 res에 저장한다.
   4. 이 때 토큰이 /라면 소수점 아래의 수를 처리하기 위해 몫만은 계산하는 //연산을 사용하여 대체한다.
   5. 결과를 스택에 다시 저장한다.
2. tokens를 모두 순회할 때 까지 위 동작을 수행한다.
3. 스택에 남아있는 수를 반환한다.

class Solution(object):
    def evalRPN(self, tokens):
        stk = []
        
        for i in range(len(tokens)):
            if tokens[i].isdigit() or len(tokens[i]) >= 2: 
                stk.append(tokens[i])
            else:
                x = stk.pop()
                y = stk.pop()

                res = eval(y + (tokens[i]) + x)

                if tokens[i] == "/" and res < 0:
                    res = -1 * (abs(int(y)) // abs(int(x)))
                stk.append(str(res))

        answer= int(eval(stk.pop()))
        return answer  

개선 1

실행 시간 : 41ms 메모리 : 15.5MB

자주보는 개발자 유튜브를 통해서 알았던 사실이 하나 있다.
코드에 if 문 즉 분기점이 많아지면 좋지 못하다는 사실이다.

이유는 가독성과 유지보수성이 주요한 이유인데, 내가 개선한 코드는 유지보수성과 가독성을 람다식을 이용했기 때문에 큰 이점을 주지 못하지만, 연산자를 걸러내는데 if 문이나 다른 코드로 걸러내는 것 보다 해시테이블을 이용하면 더 판단하기 쉬울것이라고 판단했다.

또한 이러한 판단식을 “해시 테이블에 존재하는가” 로 간단하게 바꾸면서 실행 시간에 더욱 이점을 줄 것이라고 판단되었다.

class Solution(object):
    def evalRPN(self, tokens):
        stk = []
        ops = {"+" : lambda x, y : x + y, "-" : lambda x, y : x - y, "/" : lambda x, y : x // y if x // y > 0 else abs(x) // abs(y) * -1, "*" : lambda x, y : x * y}
       
        for i in range(len(tokens)):
            if tokens[i] in ops:
                x = int(stk.pop())
                y = int(stk.pop())
                stk.append(ops[tokens[i]](y, x))
            else:
                stk.append(tokens[i])
            

        return int(stk.pop())

생각 & 정리

“명령어에 따른 기능을 수행한다.” 라는 것은 아직 사용해보지 않았지만 시스템 외부에서 명령어를 전달하는 메시지큐와 비슷한 점을 가진 문제라고 생각됐다.

계산기가 연산자에 따라 그에 맞는 기능을 수행하듯, 메시지를 처리하는 시스템도 비슷할 것이라고 생각됐다.

이러한 알고리즘 문제 뿐 아니라 실제 메시지 큐를 이용하는 프로젝트에서도 if 문 보다는 해시테이블을 사용해 가독성을 키우고 중복을 줄이는 것이 좋을 것이라고 생각됐다.