[LeetCode 해석 및 풀이] 150. Evaluate Reverse Polish Notation

LeetCode 문제 해석 및 풀이 방법

 

문제 150. Evaluate Reverse Polish Notation(역폴란드 표기법 계산)

바로가기

 

문제 설명

영문

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.

 

한글

역 폴란드 표기법의 산술 표현식을 나타낸 문자열 토큰들로 이루어진 배열이 주어집니다.

표현식을 계산하세요. 표현식의 값이 나타내는 정수를 반환합니다.

 

노트:

• 유효한 연산자는 +, -, *, / 입니다.
• 각 피연산자는 정수이거나 다른 표현식입니다.
• 두 수의 나눗셈은 항상 0으로 잘립니다.
• 0으로 나누는 경우는 없습니다.
• 입력값은 유효한 역 폴란드 표기법의 산술 표현식을 나타냅니다.
• 답과 중간 계산 결과는 32-bit 정수로 나타내어집니다.

 

제한조건

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

 

입출력 예

입력	출력
["2","1","+","3","*"]	9
["4","13","5","/","+"]	6
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]	22

 

 

해답 및 해설

파이썬 (Python)

neetcode 로드맵에 나온대로 괄호 문제와 함께 대표적인 stack 문제 중 하나.

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

                if c == "+":
                    a = x+y
                elif c == "-":
                    a = x-y
                elif c == "*":
                    a = x*y
                elif c == "/":
                    a = int(x/y)
                stack.append(a)
                
        return stack[0]

숫자들을 stack에 계속 넣다가 연산자가 나오면 숫자 2개를 뽑는다. 그 후 계산 결과를 다시 stack에 넣는 과정을 반복한다.