# 前言

藉由 LeetCode 磨練演算法

# 題目連結

LeetCode - The World's Leading Online Programming Learning Platform

# 解題思路

我覺得這一題主要是難在 RPN (Reverse Polish notation) 的概念，若是理解這個概念之後，就大概率可以用 Stack 的結構來解題

• 我們將 $tokens 依序的 push 進 stack
• 當 $token 為 + or — or * or / 之一時，表示遇到了 $operator，則從 stack pop 兩個 item 出來，分別為 $operand1 & $operand2，然後再與 $operator 計算
• 計算後的答案，在 push 進 stack，待 loop $tokens 結束後，stack 中的唯一 & 最後一個 item，即為我們要的計算結果

以下為程式碼

<?php
class Solution {

    /**
     * @param String[] $tokens
     * @return Integer
     */
    function evalRPN($tokens) {
        $stack = [];
        $len = count($tokens);
        $operators = ['+' => true, '-' => true, '*' => true, '/' => true];

        for ($i = 0; $i < $len; $i++) {
            if (isset($operators[$tokens[$i]])) {
                $operator = $tokens[$i];
                $operand2 = array_pop($stack);
                $operand1 = array_pop($stack);
                $result = $this->calculate($operator, $operand1, $operand2);
                $stack[] = $result;
                continue;
            }

            $stack[] = $tokens[$i];
        }

        return array_pop($stack);
    }

    function calculate(string &$operator, int &$operand1, int &$operand2): int
    {
        switch($operator) {
            case '+':
            return intval($operand1 + $operand2);
            case '-':
            return intval($operand1 - $operand2);
            case '*':
            return intval($operand1 * $operand2);
            case '/':
            return intval($operand1 / $operand2);
        }
    }
}

# 複雜度

時間複雜度:

時間複雜度為 O(n)

空間複雜度

• calculate() 中都使用 reference 即可，這樣就不須產生新的 variable

空間複雜度為 O(n)