c语言用栈来实现表达式求值

在C语言中，利用栈数据结构可以有效地实现基于前缀或中缀（也称为运算符优先级队列）的表达式求值。这里我们以前缀表示法为例来说明：

1. **栈的数据结构**：栈是一种LIFO（Last In First Out，后进先出）的数据结构，常用于存储操作数。

2. **前缀表达式**：前缀表达式（也叫逆波兰表示法）的特点是操作符在操作数之后，例如 "3 + 4" 的前缀形式是 "3 4 +"。

3. **求解过程**：
- **遍历输入的前缀表达式**，遇到数字就压入栈。
- 遇到运算符时，从栈顶取出两个操作数，并按照操作符的优先级进行计算（如果栈太小，说明当前操作符需要等待前面的操作完成，此时将其压回栈中）。
- 计算结果替换掉原来的两个操作数，并将新的结果压入栈中。
- 最终栈中剩下的元素就是表达式的计算结果。

**示例代码片段**（简化版，未包含错误处理）：

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

int getOp(char op) {
    // 对于简单的情况，你可以创建一个映射表来确定操作符优先级
    if (op == '+') return 1;
    if (op == '-') return 2;
    // ... 其他运算符
    return 0;  // 如果不是运算符，返回0（一般作为终止条件）
}

double applyOp(int op, double b, double a) {
    switch (op) {
        case 1: return a + b; // 加法
        case 2: return a - b; // 减法
        // ...其他情况
    }
}

void evaluatePrefix(char* prefixExp) {
    char* token = prefixExp;
    stack<double> st;

    while (*token != '\0') {
        if (isdigit(*token)) {
            double num = 0.0;
            while (isdigit(*(++token))) {
                num = num * 10 + *token - '0';
            }
            st.push(num);
        } else {
            double operand2 = st.top(); st.pop();
            double operand1 = st.top(); st.pop();
            double result = applyOp(getOp(*token), operand2, operand1);
            st.push(result);
            ++token;
        }
    }

    printf("结果: %.2f\n", st.top());
}

int main() {
    char prefix[] = "2 3 + 4 *";
    evaluatePrefix(prefix);
    return 0;
}