用递归法求逆波兰表达式 c语言

逆波兰表达式，也称为后缀表达式，是一种无需使用括号就能明确表示运算顺序的数学表达式表示方式。在C语言中，可以使用递归算法来解析和计算这种类型的表达式。下面是一个简单的递归函数示例，用于处理逆波兰表达式的求值：

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

// 定义操作数栈
#define MAX_STACK_SIZE 100
int stack[MAX_STACK_SIZE];
int top = -1;

// 单元操作，如加减乘除
double operate(char op, double a, double b) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b; // 需要考虑除数为零的情况
        default: return 0;     // 如果遇到未知操作符，通常返回错误
    }
}

// 递归函数，处理逆波兰表达式的计算
double evalPostfix(char* tokens, int n) {
    if (n <= 0) return 0; // 栈空或只剩下一个操作数，直接返回
    char op = tokens[n-1]; // 取出最后一个字符作为操作符
    double val2 = evalPostfix(tokens, n-2); // 递归处理第二个操作数
    double val1 = top >= 0 ? stack[top--] : 0; // 弹出栈顶的操作数
    stack[top+1] = operate(op, val1, val2); // 计算结果并入栈
    return top >= 0 ? stack[top++] : 0;   // 返回当前栈顶元素，处理剩余的栈顶元素
}

// 主函数测试
int main() {
    char* postfix = "2 3 + 4 *"; // 示例逆波兰表达式
    int token_count = strlen(postfix);
    for (int i = 0; i < token_count; ++i) {
        if (isdigit(postfix[i])) {
            stack[++top] = postfix[i] - '0'; // 将数字压入栈
        } else {
            stack[top+1] = evalPostfix(postfix + i + 1, token_count - (i + 1)); // 调用递归处理操作符
            i--; // 回溯到上一个位置，因为刚刚处理了操作符
        }
    }
    printf("计算结果: %lf\n", stack[top]);
    return 0;
}

在这个例子中，`evalPostfix`函数负责处理逆波兰表达式，它会根据操作符不断从栈中弹出操作数并计算结果，直到所有操作完成。