1、使用栈

使用栈数据结构是计算逆波兰表达式的经典方法。

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

#define MAX_STACK_SIZE 100

// 判断是否为运算符
int isOperator(char *token) {
    return (strcmp(token, "+") == 0 ||
            strcmp(token, "-") == 0 ||
            strcmp(token, "*") == 0 ||
            strcmp(token, "/") == 0);
}

// 执行运算
int performOperation(int a, int b, char *operator) {
    if (strcmp(operator, "+") == 0) return a + b;
    if (strcmp(operator, "-") == 0) return a - b;
    if (strcmp(operator, "*") == 0) return a * b;
    if (strcmp(operator, "/") == 0) return a / b;
    return 0; // 不会执行到这里
}

// 计算逆波兰表达式的函数
int evaluateRPN(char **tokens, int tokensSize) {
    int stack[MAX_STACK_SIZE];
    int top = -1;

    for (int i = 0; i < tokensSize; i++) {
        if (isOperator(tokens[i])) {
            int b = stack[top--];
            int a = stack[top--];
            int result = performOperation(a, b, tokens[i]);
            stack[++top] = result;
        } else {
            stack[++top] = atoi(tokens[i]);
        }
    }

    return stack[top];
}

int main() {
    char *tokens1[] = {"2", "1", "+", "3", "*"};
    int size1 = sizeof(tokens1) / sizeof(tokens1[0]);
    printf("Result: %d\n", evaluateRPN(tokens1, size1)); // 输出: 9

    char *tokens2[] = {"4", "13", "5", "/", "+"};
    int size2 = sizeof(tokens2) / sizeof(tokens2[0]);
    printf("Result: %d\n", evaluateRPN(tokens2, size2)); // 输出: 6

    return 0;
}

2、递归方法

使用递归方法可以简化部分逻辑，但需要更多的内存和栈深度。

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

// 判断是否为运算符
int isOperator(char *token) {
    return (strcmp(token, "+") == 0 ||
            strcmp(token, "-") == 0 ||
            strcmp(token, "*") == 0 ||
            strcmp(token, "/") == 0);
}

// 执行运算
int performOperation(int a, int b, char *operator) {
    if (strcmp(operator, "+") == 0) return a + b;
    if (strcmp(operator, "-") == 0) return a - b;
    if (strcmp(operator, "*") == 0) return a * b;
    if (strcmp(operator, "/") == 0) return a / b;
    return 0; // 不会执行到这里
}

// 递归计算逆波兰表达式
int evaluateRPNRecursively(char **tokens, int *index) {
    char *token = tokens[(*index)--];

    if (!isOperator(token)) {
        return atoi(token);
    } else {
        int b = evaluateRPNRecursively(tokens, index);
        int a = evaluateRPNRecursively(tokens, index);
        return performOperation(a, b, token);
    }
}

int evaluateRPN(char **tokens, int tokensSize) {
    int index = tokensSize - 1;
    return evaluateRPNRecursively(tokens, &index);
}

int main() {
    char *tokens1[] = {"2", "1", "+", "3", "*"};
    int size1 = sizeof(tokens1) / sizeof(tokens1[0]);
    printf("Result: %d\n", evaluateRPN(tokens1, size1)); // 输出: 9

    char *tokens2[] = {"4", "13", "5", "/", "+"};
    int size2 = sizeof(tokens2) / sizeof(tokens2[0]);
    printf("Result: %d\n", evaluateRPN(tokens2, size2)); // 输出: 6

    return 0;
}

3、手动模拟栈操作

手动模拟栈操作可以实现更低层次的控制，但代码较复杂。

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

#define MAX_STACK_SIZE 100

// 判断是否为运算符
int isOperator(char *token) {
    return (strcmp(token, "+") == 0 ||
            strcmp(token, "-") == 0 ||
            strcmp(token, "*") == 0 ||
            strcmp(token, "/") == 0);
}

// 执行运算
int performOperation(int a, int b, char *operator) {
    if (strcmp(operator, "+") == 0) return a + b;
    if (strcmp(operator, "-") == 0) return a - b;
    if (strcmp(operator, "*") == 0) return a * b;
    if (strcmp(operator, "/") == 0) return a / b;
    return 0; // 不会执行到这里
}

// 手动模拟栈操作
int evaluateRPN(char **tokens, int tokensSize) {
    int stack[MAX_STACK_SIZE];
    int top = -1;

    for (int i = 0; i < tokensSize; i++) {
        if (isOperator(tokens[i])) {
            if (top < 1) {
                fprintf(stderr, "Error: Insufficient values in the expression\n");
                exit(EXIT_FAILURE);
            }
            int b = stack[top--];
            int a = stack[top--];
            int result = performOperation(a, b, tokens[i]);
            stack[++top] = result;
        } else {
            char *endptr;
            long val = strtol(tokens[i], &endptr, 10);
            if (*endptr != '\0') {
                fprintf(stderr, "Error: Invalid number %s\n", tokens[i]);
                exit(EXIT_FAILURE);
            }
            stack[++top] = val;
        }
    }

    if (top != 0) {
        fprintf(stderr, "Error: The expression does not evaluate to a single result\n");
        exit(EXIT_FAILURE);
    }

    return stack[top];
}

int main() {
    char *tokens1[] = {"2", "1", "+", "3", "*"};
    int size1 = sizeof(tokens1) / sizeof(tokens1[0]);
    printf("Result: %d\n", evaluateRPN(tokens1, size1)); // 输出: 9

    char *tokens2[] = {"4", "13", "5", "/", "+"};
    int size2 = sizeof(tokens2) / sizeof(tokens2[0]);
    printf("Result: %d\n", evaluateRPN(tokens2, size2)); // 输出: 6

    return 0;
}