LC 150. Reverse Polish Notation: 후위표기법

후위표기법 을 기본 연산자로 변환해 계산하는 문제

• 2 1 + 3 * => (2 + 1) * 3으로 연산 해야한다.

• 활용 자료구조

  • 스택을 이용해 구현
    • 먼저 들어간 값들을 확인 후 연산 해야하기 때문에 스택이 적절하다.

• 문제해결 시나리오

  1. 배열을 반복문 돌려 값 확인 후 값이 숫자일 경우 스택에 추가한다.
  2. 값이 연산자일 경우 스택에서 값을 차례대로 두 개 pop()해서 빼낸다.
  3. 연산자에 맞게 연산 후 다시 스택에 추가한다.
  4. 마지막 스택에 남은 값을 return 한다.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        # 반복문 돌며 숫자일 경우 stack에 추가
        # 연산자가 나올 경우
        # 이전 값 2개 pop 후 연산
        # 연산한 값을 다시 스택에 넣기

        stack = []

        for token in tokens:
            if token == '+':
                a, b = stack.pop(), stack.pop()
                stack.append(b + a)
            elif token == '-':
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif token == '*':
                a, b = stack.pop(), stack.pop()
                stack.append(b * a)
            elif token == '/':
                a, b = stack.pop(), stack.pop()
                stack.append(int(b / a))
            else:
                stack.append(int(token))
        return stack.pop()

• lamda를 활용한 풀이

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        op = {
            '+': lambda a, b: a + b,
            '-': lambda a, b: a - b,
            '*': lambda a, b: a * b,
            '/': lambda a, b: int(a/b)
        }

        for token in tokens:
            if token in op:
                b = stack.pop()
                a = stack.pop()
                stack.append(op[token](a, b))
            else: 
                stack.append(int(token))
        
        return stack.pop()