LeetCode - 역 폴란드어 표기법 평가

문제 설명

Reverse Polish Notation에서 산술 표현식의 값을 평가합니다.

유효한 연산자는 +, -, 및 */입니다. 각 피연산자는 정수 또는 다른 표현식일 수 있습니다.

두 정수 사이의 나눗셈은 0을 향해 잘려야 합니다.

주어진 RPN 표현식이 항상 유효함을 보장합니다. 즉, 표현식은 항상 결과로 평가되며 0으로 나누기 작업이 없습니다.

문제 진술 출처: https://leetcode.com/problems/evaluate-reverse-polish-notation

예 1:

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

예 2:

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

예 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

제약:

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

설명

Reverse Polish Notation은 연산자가 피연산자를 따르는 수학 표기법입니다.

기본 접근 방식은 스택을 사용하는 것입니다. 알고리즘을 직접 확인해 보겠습니다.

- create stack st
  initialize int op1, op2

- loop for i = 0; i < tokens.size; i++
  - if tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"
    - push to stack st.push(tokens[i])
  - else
    - set op2 = st.pop()
      set op1 = st.pop()

    - if tokens[i] == "+"
      - st.push(op1 + op2)
    - else if tokens[i] == "-"
      - st.push(op1 - op2)
    - else if tokens[i] == "*"
      - st.push(op1 * op2)
    - else
      - st.push(op1 / op2)
- for end

- return st.top()

이 함수의 시간 복잡도는 O(N)이고 공간 복잡도는 O(N)입니다.

C++, Golang 및 Javascript에서 솔루션을 확인합시다.

C++ 솔루션

typedef long long ll;

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<ll> st;
        ll op1, op2;

        for(int i = 0; i < tokens.size(); i++) {
            if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
                st.push(stol(tokens[i]));
            } else {
                op2 = st.top();
                st.pop();
                op1 = st.top();
                st.pop();

                if(tokens[i] == "+")
                    st.push(op1 + op2);
                else if(tokens[i] == "-")
                    st.push(op1 - op2);
                else if(tokens[i] == "*")
                    st.push(op1 * op2);
                else
                    st.push(op1 / op2);
            }
        }

        return (int) st.top();
    }
};

골랑 솔루션

func evalRPN(tokens []string) int {
    st := []int{}

    for _, token := range tokens {
        if token == "+" {
            st[len(st) - 2] += st[len(st) - 1]
            st = st[:len(st) - 1]
        } else if token == "-" {
            st[len(st) - 2] -= st[len(st) - 1]
            st = st[:len(st) - 1]
        } else if token == "*" {
            st[len(st) - 2] *= st[len(st) - 1]
            st = st[:len(st) - 1]
        } else if token == "/" {
            st[len(st) - 2] /= st[len(st) - 1]
            st = st[:len(st) - 1]
        } else {
            num, _ := strconv.Atoi(token)
            st = append(st, num)
        }
    }

    return st[0]
}

자바스크립트 솔루션

var evalRPN = function(tokens) {
    let st = [];
    let op1, op2;

    for(let i = 0; i < tokens.length; i++) {
        if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
                st.push(parseInt(tokens[i]));
        } else {
            op2 = st.pop();
            op1 = st.pop();

            if(tokens[i] === "+")
                st.push(op1 + op2);
            else if(tokens[i] === "-")
                st.push(op1 - op2);
            else if(tokens[i] === "*")
                st.push(op1 * op2);
            else
                st.push(op1 / op2 | 0);
        }
    }

    return st[0];
};

솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

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

Step 1: stack<ll> st
        int op1, op2

Step 2: loop for int i = 0; i < tokens.size()
          i < tokens.size()
          0 < 5
          true

          if tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"
             tokens[0] is "2"
             true

             st.push(stoi(tokens[i]))
             st.push(stoi(tokens[0]))
             st.push(2)

             st = [2]

          i++
          i = 1

Step 3: loop for i < tokens.size()
          1 < 5
          true

          if tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"
             tokens[1] is "1"
             true

             st.push(stoi(tokens[i]))
             st.push(stoi(tokens[1]))
             st.push(1)

             st = [2, 1]

          i++
          i = 2

Step 4: loop for i < tokens.size()
          2 < 5
          true

          if tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"
             tokens[1] is "+"
             false

          else
            op2 = st.top()
                = 1

            st.pop()
            st = [2]

            op1 = st.top()
                = 2

            st.pop()
            st = []

            if tokens[i] == "+"
               true

               st.push(op1 + op2)
               st.push(2 + 1)
               st.push(3)

               st = [3]

          i++
          i = 3

Step 5: loop for i < tokens.size()
          3 < 5
          true

          if tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"
             tokens[3] is "3"
             true

             st.push(stoi(tokens[i]))
             st.push(stoi(tokens[3]))
             st.push(3)

             st = [3, 3]

          i++
          i = 4

Step 6: loop for i < tokens.size()
          4 < 5
          true

          if tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"
             tokens[4] is "*"
             false

          else
            op2 = st.top()
                = 3

            st.pop()
            st = [3]

            op1 = st.top()
                = 3

            st.pop()
            st = []

            if tokens[i] == "+"
              false
            else if tokens[i] == "-"
              false
            else if tokens[i] == "*"
               st.push(op1 * op2)
               st.push(3 * 3)
               st.push(9)

               st = [9]

          i++
          i = 5

Step 7: loop for i < tokens.size()
          5 < 5
          false

Step 8: return st[0]

We return the answer as 9.