C语言 用栈求算数运算式

在C语言中，使用栈（stack）来求解算术运算表达式通常涉及到前缀表达式（也称为逆波兰表示法， postfix notation），因为这种方式可以避免括号嵌套带来的复杂性。这种算法通常涉及以下几个步骤：

1. **输入表达式**：将给定的算术运算符和操作数转换成前缀或后缀形式的字符串。

2. **解析栈操作**：
- 从左到右扫描输入表达式。
- 遇到数字时，将其压入栈中。
- 遇到运算符时，比较其优先级，如果当前栈顶元素的优先级低，则把栈顶元素弹出并压入新运算符；直到遇到优先级更高的运算符或栈为空。
- 当遇到右括号'('时，将其忽略，并继续处理下一个字符。

3. **计算结果**：
- 最终栈中只剩下了计算的结果，即整数或变量。

4. **输出结果**：从栈中取出所有元素，恢复原表达式的值。

下面是一个简单的示例，说明如何通过栈实现加减乘除运算：

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

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0; // 非运算符字符
}

int applyOp(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b; // 注意这里假设除数不为零
        default: return -1; // 错误的操作符
    }
}

void evaluatePostfix(char* exp) {
    int stack[100], top = -1;
    for (char* token = exp; *token != '\0'; token++) {
        if (*token >= '0' && *token <= '9') {
            while (top > -1 && *token > '0' && *token <= '9') {
                stack[++top] = *token - '0';
                token++;
            }
        } else {
            while (top > -1 && precedence(token) <= precedence(stack[top])) {
                int b = stack[top--];
                int a = stack[top--];
                stack[top++] = applyOp(a, b, stack[top]);
            }
            stack[++top] = *token; // 将运算符压入栈
        }
    }

    // 处理剩余的数值
    while (top > -1) {
        int b = stack[top--];
        int a = stack[top--];
        stack[top++] = applyOp(a, b, stack[top]);
    }

    printf("Result: %d\n", stack[0]); // 输出最终结果
}

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

这个例子中，`evaluatePostfix`函数实现了上述流程。运行上面的`main`函数会输出 `20`，因为 `(2+3)*4=20`。