数据结构c语言版求解中缀表达式

在C语言中，我们可以使用栈数据结构来解决中缀表达式的求值问题，也称为逆波兰表示法（Reverse Polish Notation, RPN）。这种方法通常涉及以下几个步骤：

1. **扫描输入表达式**：遍历给定的中缀表达式，遇到数字就直接压入栈中，遇到运算符则按照操作数优先级处理。

2. **处理运算符**：对于每个运算符，检查其优先级并与栈顶运算符比较。如果栈顶运算符优先级低，就将栈顶的运算符弹出并推到结果，然后将当前运算符压入栈。若当前运算符优先级高于或等于栈顶运算符，则继续压入。

3. **遇到右括号时**：当遇到右括号，说明已经处理完了左括号对应的子表达式。此时将栈顶运算符弹出并推到结果，直到遇到左括号为止。

4. **最后处理剩余的运算符**：当只剩下一对括号时，将剩余的所有运算符依次弹出并推到结果。

5. **计算结果**：最终栈中只剩下一个元素，即为整个表达式的值。

下面是一个简单的C语言函数示例，用于求解中缀表达式：

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int isOperator(char op) {
    // 检查op是否是运算符...
}

stack createStack() {
    // 初始化栈...
}

void push(stack s, char item) {
    // 向栈中添加元素...
}

char pop(stack s) {
    // 弹出栈顶元素...
}

int evaluate(char *exp) {
    stack s = createStack();
    int i = 0;
    while (exp[i] != '\0') {
        if (isdigit(exp[i])) {
            push(s, exp[i++] - '0');
        } else {
            int val2 = pop(s);
            int val1 = pop(s);
            switch (exp[i]) {
                case '+':
                    push(s, val1 + val2);
                    break;
                case '-':
                    push(s, val1 - val2);
                    break;
                case '*':
                    push(s, val1 * val2);
                    break;
                case '/':
                    push(s, val1 / val2);
                    break;
            }
            i++;
        }
    }
    return pop(s);
}

int main() {
    char exp[] = "3+2*2";
    printf("Value of expression %s is: %d\n", exp, evaluate(exp));
    return 0;
}