Description

150. Evaluate Reverse Polish Notation

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].

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int evalRPN(char** tokens, int tokensSize) {
    int *stack = (int *)malloc(tokensSize * sizeof(int)); // 用於存放操作數字的Stack
    int top = -1; // top指標

    for (int i = 0; i < tokensSize; i++) {
        // 如果 token 是數字，將其轉換為整數並推入堆疊
        if (isdigit(tokens[i][0]) || (tokens[i][0] == '-' && tokens[i][1] != '\0')) {
            stack[++top] = atoi(tokens[i]);
        } else {
            // token 是操作符號
            int b = stack[top--]; // 從堆疊pop頂端元素（右操作數）
            int a = stack[top--]; // 從堆疊pop第二頂端元素（左操作數）
            int result;

            // 執行相應的操作
            switch (tokens[i][0]) {
                case '+':
                    result = a + b;
                    break;
                case '-':
                    result = a - b;
                    break;
                case '*':
                    result = a * b;
                    break;
                case '/':
                    // 除法
                    result = a / b;
                    break;
                default:
                    // 無效的操作符（根據題目描述不會發生）
                    free(stack); //釋放空間
                    return 0;
            }

            // 將結果推回Stack
            stack[++top] = result;
        }
    }

    // 最後的結果將在Stack top
    int finalResult = stack[top];
    free(stack); // 釋放記憶體空間
    return finalResult;
}

Testing

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int evalRPN(char** tokens, int tokensSize) {
    int *stack = (int *)malloc(tokensSize * sizeof(int)); // 用於存放操作數字的Stack
    int top = -1; // top指標

    for (int i = 0; i < tokensSize; i++) {
        // 如果 token 是數字，將其轉換為整數並推入堆疊
        if (isdigit(tokens[i][0]) || (tokens[i][0] == '-' && tokens[i][1] != '\0')) {
            stack[++top] = atoi(tokens[i]);
        } else {
            // token 是操作符號
            int b = stack[top--]; // 從堆疊pop頂端元素（右操作數）
            int a = stack[top--]; // 從堆疊pop第二頂端元素（左操作數）
            int result;

            // 執行相應的操作
            switch (tokens[i][0]) {
                case '+':
                    result = a + b;
                    break;
                case '-':
                    result = a - b;
                    break;
                case '*':
                    result = a * b;
                    break;
                case '/':
                    // 除法
                    result = a / b;
                    break;
                default:
                    // 無效的操作符（根據題目描述不會發生）
                    free(stack); //釋放空間
                    return 0;
            }

            // 將結果推回Stack
            stack[++top] = result;
        }
    }

    // 最後的結果將在Stack top
    int finalResult = stack[top];
    free(stack); // 釋放記憶體空間
    return finalResult;
}

int main() {
    // 範例使用
    char *tokens1[] = {"2", "1", "+", "3", "*"};
    int result1 = evalRPN(tokens1, 5);
    printf("Result 1: %d\n", result1); // 輸出：9

    char *tokens2[] = {"4", "13", "5", "/", "+"};
    int result2 = evalRPN(tokens2, 5);
    printf("Result 2: %d\n", result2); // 輸出：6

    char *tokens3[] = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
    int result3 = evalRPN(tokens3, 13);
    printf("Result 3: %d\n", result3); // 輸出：22

    return 0;
}