Skip to main content

Evaluate Reverse Polish Notation

문제​

당신은 역폴란드 표기법으로 표현된 산술 식을 나타내는 문자열 배열 tokens을 주어지게 됩니다. 이 표현식을 평가하세요. 표현식의 값을 나타내는 정수를 반환하세요.

주의할 점:

  • 유효한 연산자는 '+', '-', '*', '/' 입니다.
  • 각 피연산자는 정수 또는 다른 표현식이 될 수 있습니다.
  • 두 정수 사이의 나눗셈은 항상 0을 향해 절삭됩니다.
  • 0으로 나누는 경우는 없습니다.
  • 입력은 유효한 역폴란드 표기법으로 표현된 산술식을 나타냅니다.
  • 답과 모든 중간 계산 결과는 32비트 정수로 나타낼 수 있습니다.

접근 방향​

tokens = ["2", "1", "+", "3", "*"]

# 1. 숫자를 만나면 스택에 푸쉬
stack = [2, 1]
# 2. 연산자 "+"를 만나면 stack에서 pop하여 숫자를 추출 후 연산, 연산값을 스택에 푸시
res => 2 + 1 = 3
stack = [3]
# 3. 숫자를 만나면 스택에 푸쉬
stack = [3, 3]
# 4. 연산자 "*"를 만나면 stack에서 pop하여 숫자를 추출 후 연산
res => 3 * 3 = 9

tokens = ["4", "13", "5", "/", "+"]

# 1. 숫자를 만나면 스택에 푸쉬
stack = [4, 13, 5]
# 2. 연산자 "/"를 만나면 stack에서 pop하여 숫자를 추출 후 연산, 연산값을 스택에 푸시
res => 13 / 5 = 2
stack = [2, 4]
# 3. 연산자 "+"를 만나면 stack에서 pop하여 숫자를 추출 후 연산
res => 2 + 4 = 6

위와 같은 방식으로 후위 표기법 순으로 요소가 담긴 배열을 중위 표기법으로 계산할 때 숫자는 스택에 추가하고 연산자를 만났을 경우 스택에 추가한 숫자를 뒤에서부터 추출하여 계산하도록 합니다. 숫자를 만나서 스택에 넣을 때는 문자열 타입을 int 타입으로 변경하여 스택에 푸시하도록 합니다.

나의 풀이​

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """

        stack = []
        for t in tokens:
            # tokens 내 요소가 숫자일 경우 스택에 추가
            if t not in ["+", "-", "*", "/"]:
                stack.append(int(t))
            else:
                num_1 = stack.pop()
                num_2 = stack.pop()
                # 요소가 숫자가 아닐 경우 연산자 별로 연산
                if t == "+":
                    temp = (num_2 + num_1)
                    stack.append(temp)
                elif t == "-":
                    temp = (num_2 - num_1)
                    stack.append(temp)
                elif t == "/":
                    temp = int(num_2 / num_1)
                    stack.append(temp)
                else:
                    temp = (num_2 * num_1)
                    stack.append(temp)

        # 마지막으로 남은 stack 내 요소는 결괏값을 의미
        return stack.pop()