## 150. Evaluate Reverse Polish Notation(Medium)

### 題目描述
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

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

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 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

Constraints:

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

### 解題思路
宣告一個變數（top）來追蹤堆疊中最頂層的項目，堆疊初始化為-1，當元素新增到堆疊時，頂部的位置會更新，一旦元素被彈出或刪除，最上面的元素就會被刪除並更新頂部的位置。
### 程式碼

int evalRPN(char ** tokens, int tokensSize){
    int stack[tokensSize];
    int top = -1;

    for (int i = 0; i < tokensSize; i++) {
        if (strcmp(tokens[i], "+") == 0) {
            //strcmp(str1, str2)函數比較兩個字串，如果相等，則回傳0。
            int temp1 = stack[top];
            top--;
            int temp2 = stack[top];
            stack[top] = temp2 + temp1;
        } else if (strcmp(tokens[i], "-") == 0) {
            int temp1 = stack[top];
            top--;
            int temp2 = stack[top];
            stack[top] = temp2 - temp1;
        } else if (strcmp(tokens[i], "*") == 0) {
            int temp1 = stack[top];
            top--;
            int temp2 = stack[top];
            stack[top] = temp2 * temp1;
        } else if (strcmp(tokens[i], "/") == 0) {
            int temp1 = stack[top];
            top--;
            int temp2 = stack[top];
            
            stack[top] = temp2 / temp1;
        } else {
            top++;
            stack[top] = atoi(tokens[i]);
            //atoi(const char *str)將字串參數str轉換為整數（int型）。
        }
    }
    return stack[top];
}

### 時間/空間複雜度
* 時間複雜度: $O(n)$
* 空間複雜度: $O(n)$