Evaluate Reverse Polish Notation - LeetCode

Problem

1. input: 후위 표기법 식이 담긴 문자열 리스트 tokens
2. output: 주어진 후위 표기법 식을 연산하여 결과 리턴
   • 1 <= tokens.length <= 10^4
   • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Idea

후위 표기법의 연산은 스택을 활용하면 쉽게 할 수 있다.

숫자는 스택에 삽입하고, 연산자가 나오면 스택의 최상단 2개의 값을 꺼내 연산하면 된다 → Sol1

Solution

1. Stack

   • 숫자 → 스택에 삽입
   • 연산자 → 스택에서 숫자 2개 pop 후, 두 숫자 연산한 결과 삽입

   import java.util.*
   
   class Solution {
       fun evalRPN(tokens: Array<String>): Int {
           val stack = Stack<Int>()
           for (token in tokens) {
               if(token.all { it.isDigit() } || (token[0] == '-' && token.length > 1 && token.substring(1, token.length).all { it.isDigit() })) {
                   stack.add(token.toInt())
               } else { // 연산자가 들어온 경우
                   val second = stack.pop()
                   val first = stack.pop()
                   when (token) {
                       "+" -> stack.add(first + second)
                       "-" -> stack.add(first - second)
                       "*" -> stack.add(first * second)
                       "/" -> stack.add(first / second)
                   }
               }
           }
           return stack.pop()
       }
   }
   

   시간 복잡도: 문자열 순회 = n

   

Point