// 演算法：用一個整數陣列當作堆疊，從左到右掃描 tokens。
// Algorithm: use an int array as a stack and scan tokens left to right.
// 遇到數字就 push；遇到運算子就 pop 兩個數、計算、再 push 回結果。
// Push numbers; on an operator pop two values, compute, push the result back.
// 掃完後堆疊頂端 (唯一元素) 就是答案。/ At the end the lone stack value is the answer.

#include <stdlib.h>   // 提供 malloc / free / atoi / String to int. (for malloc/free/atoi)
#include <string.h>   // 提供 strcmp 比較字串 / for strcmp to compare strings.

int evalRPN(char** tokens, int tokensSize) {
    // 配置一個堆疊；最壞情況全是數字，所以大小取 tokensSize 就一定夠。
    // Allocate a stack; worst case all tokens are numbers, so tokensSize slots suffice.
    int* stack = (int*)malloc(sizeof(int) * tokensSize);

    int top = 0;  // top 指向「下一個要寫入的位置」，同時等於目前堆疊大小。
                  // top is the next write index, and also the current stack size.

    // 逐一處理每個 token（tokens[i] 是一個字串，即 char*）。
    // Process each token one by one (tokens[i] is a string, i.e. a char*).
    for (int i = 0; i < tokensSize; i++) {
        char* t = tokens[i];  // t 指向目前這個字串 / t points to the current token string.

        // strcmp 回傳 0 代表兩字串完全相同。判斷 t 是否為四個運算子之一。
        // strcmp returns 0 when the two strings are equal. Check if t is an operator.
        if (strcmp(t, "+") == 0 || strcmp(t, "-") == 0 ||
            strcmp(t, "*") == 0 || strcmp(t, "/") == 0) {

            // 是運算子：先 pop 出右運算元（後進先出，最上面的是右邊）。
            // It's an operator: pop the right operand first (LIFO: top is the right side).
            int right = stack[--top];   // --top 先把 top 減 1，再取該位置的值 / pre-decrement then read.

            // 再 pop 出左運算元。/ Then pop the left operand.
            int left = stack[--top];

            int result;  // 存放這次運算的結果 / holds this operation's result.

            // 依運算子計算。t[0] 是字串的第一個字元（運算子只有一個字元）。
            // Compute based on the operator. t[0] is the first character of the string.
            if      (t[0] == '+') result = left + right;
            else if (t[0] == '-') result = left - right;   // 順序重要：左 - 右 / order matters: left - right.
            else if (t[0] == '*') result = left * right;
            else                  result = left / right;   // C 的整數除法本來就向 0 取整 / C int division already truncates toward zero.

            // 把結果 push 回堆疊（寫入 top 位置後 top 加 1）。
            // Push the result back (write at top, then increment top).
            stack[top++] = result;
        } else {
            // 不是運算子 → 是數字。atoi 把字串轉成整數（能處理負號，如 "-11"）。
            // Not an operator → a number. atoi converts the string to int (handles "-11").
            stack[top++] = atoi(t);  // push 該數字 / push the number.
        }
    }

    int answer = stack[0];  // 掃描結束，堆疊只剩一個值，在索引 0 / only one value remains, at index 0.
    free(stack);            // 釋放剛才 malloc 的記憶體，避免記憶體洩漏 / free the malloc'd memory to avoid a leak.
    return answer;          // 回傳答案 / return the answer.
}