[Leetcode/파이썬] 150. Evaluate Reverse Polish Notation

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.

 

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

 

Constraints:

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

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

        for t in tokens :
            if t in ["+", "-", "*", "/"] :
                second = stack.pop()
                first = stack.pop()

                if t == '+' :
                    stack.append(first + second)
                elif t == '-' :
                    stack.append(first - second)
                elif t == '*' :
                    stack.append(first * second)
                elif t == '/' :
                    stack.append(int(first/second))
            else :
                stack.append(int(t))
        
        return stack[0]

조금 더 깔끔해 보여서 처음 풀었던거 보다 이런 방식으로 바꾸었다. 

처음에 이 문제를 유사한 버전의 백준 문제를 풀어본 적이 있어서 Stack을 활용해서 문제를 풀이하는 것 까지 알고 있었으나, 구현까지 가지 못한 것을 보니 제대로 공부하지 않았기 때문이라고 생각한다.

이 문제는 후위 표기법으로 된 수식을 계산하는 문제입니다. 이는 숫자가 먼저 오고 연산자가 나중에 오는 표기법으로, 우리가 평소 사용하는 표기법은 중위 표기법으로, 연산자가 두 피연산자 사이에 오도록 위치시키는 것이고, 후위 표기법은 연산자가 마지막에 오도록 표기처리 하는 것이다.

1. 입력되는 데이터를 확인해보자.
   1. 숫자, +, -, *, / 가 문자 형태로 입력이 되어있다. 
   2. 숫자와 연산으로 분류해야할 것이라고 생각이 든다.
2. 우리는 숫자와 연산으로 분류를 할 것이다. 연산에 해당하는 것은 stack에 바로바로 추가하고, 연산이 나오면 계산을 진행하기로 하자. 
3. 기본적으로 연산을 하려면, 하나의 연산자에 두 개의 숫자가 필요하기 때문에 첫번째 pop되는 숫자는 second 에, 두 번째로 pop되는 숫자는 first 에 추가한다. 만약 이 전에 연산이 끝난 숫자가 있으면 first가 되는 것이다.