LeetCode Top Interview 150) Evaluate Reverse Polish Notation

Question

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.

Constraints:

• 1 <= tokens.length <= 10^4
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

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

---

---

문자열 tokens가 후위식 계산 순서로 정수 또는 사칙연산 기호를 가지고 있습니다. 이를 계산한 결과를 반환하는 문제입니다. 후위식 계산은 스택으로 계산이 가능한 대표 계산방법입니다.
zeroDivision 에러는 나지 않는다고 했으므로 예외처리 없이 코드 작성이 가능합니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def calc(self,n1:int,n2:int,op:str)->int:
        if op == '+':
            return n1+n2
        elif op =='-':
            return n1-n2
        elif op == '*':
            return n1 * n2
        else:
            return int(n1 / n2)

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        op_set = {"+","-","*","/"}
        for token in tokens:
            if token not in op_set:
                stack.append(int(token))
            else:
                n2 = stack.pop()
                n1 = stack.pop()
                stack.append(self.calc(n1,n2,token))
        return stack[0]

• calc() 함수 : 앞 숫자n1, 뒷 숫자n2, 사칙연산의 연산자op를 받아서 계산 결과를 반환합니다.

  나눗셈을 할 때 n1//n2가 아닌 int(n1/n2)인 이유는 음수몫 때문입니다. 이는 나머지의 정의로 생겨나는 문제입니다. 수학적으로 나머지는 0이상으로 두기 때문입니다.
  예를 들어, -1 / 4의 결과는 -0.25이고 몫과 나머지로 표기하면 몫: -1, 나머지:0.75가 됩니다.
  해당 코딩 문제에서는 나눗셈에서 몫이 아닌 정수 부분을 취하도록 얘기했기 때문에 //연산자로 몫을 취하는 것이 아니라 int를 통해 정수 부분만 취하도록 합니다.

• stack :tokens의 정수를 담을 스택입니다.
• op_set : 사칙연산의 연산자를 저장한 집합입니다. tokens를 탐색할 때 정수인지 연산자인지 구분하는 기준이 됩니다.
• tokens를 탐색하며 정수인지 연산자인지 판별을 합니다. tokens가 op_set내부에 존재한다면 연산자이므로 이를 기준으로 구분합니다. (set이 내부 탐색에 가장 빠르므로 튜플이나 리스트가 아닌 set을 사용합니다)
  • 정수라면 stack에 담습니다.
  • 연산자가 나왔다면 스택에서 두 숫자를 꺼내어 연산자로 계산을 합니다. 최근의 숫자일수록 뒷 숫자이므로 처음 꺼내는 숫자를 n2, 이후를 n1이라고 정의합니다.
• 모든 계산이 끝났다면 stack에는 최종값 하나만이 남습니다.

---

후위 계산과 스택에 대해 알고있다면 구현에는 큰 어려움이 없는 문제였습니다.
하지만 연산자와 정수를 구분할 때 아무생각없이 str.isdigit()으로 정수를 판별했기에 오류가 났습니다. isdigit(), isnumeric()등의 함수는 앞의 -기호를 구분하지 않기에 음수를 알 수 없습니다. 이 때문에 op_set을 두었습니다.

다음은 몫과 나머지에서 아차했습니다. 나머지가 양수여야 한다는 것이 생각보다 애매한게 나머지를 처음 배우는 시점엔 음수 개념이 없을 때고, 음수 개념을 배우는 시점엔 이를 크게 안다루고, 고1 때는 곱셈 정리에서 다시 나오지만 기억에 남을 만큼 비중있게 나오지 않습니다.
그나마 수학을 가르쳐본 경험덕에 금방 눈치챘지만 그런 경험이 없었다면 내장 함수 특징으로 넘어가는 사람도 있을거란 생각도 들었습니다. 다들 조심..!