前缀表达式求值c语言

前缀表达式，也称为逆波兰表示法（Reverse Polish Notation, RPN），是一种数学运算表达式的书写方式，操作数在操作符之前，不需要使用括号。在C语言中计算前缀表达式的值通常涉及两个步骤：解析和计算。

1. **解析**：首先，你需要将用户输入的 infix (常规的中缀表达式) 转换为 prefix (前缀表达式)。这涉及到栈的操作，遍历中缀表达式，遇到数字就压入栈，遇到运算符则弹出最近的两个数做运算并压回结果。

2. **计算**：接着，从左到右读取前缀表达式中的元素，如果遇到数字，则将其压入堆栈；如果遇到运算符，就从堆栈顶取出两个操作数进行相应的算术运算，并把结果压回堆栈。这个过程会一直持续到只剩下一个元素，即为最终的结果。

以下是简单的前缀表达式求值伪代码示例：

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

int eval(char* exp);

// 定义操作数和操作符函数
int number(char* token);
int apply(char op, int a, int b);

int main() {
    char* exp = "3 4 + 5 *"; // 假设的前缀表达式
    printf("%d\n", eval(exp));
    return 0;
}

// 核心的求值函数
int eval(char* exp) {
    stack_t *s = createStack();
    while (*exp != '\0') {
        if(isdigit(*exp)) {
            pushNumber(s, number(exp));
            exp++;
        } else {
            int val2 = pop(s);
            int val1 = pop(s);
            int result = apply(*exp, val1, val2);
            push(s, result);
            exp++;
        }
    }
    return pop(s);
}

// 其他辅助函数省略...