C语言用栈实现表达式求值

好的，我可以为您解答这个问题。

C语言可以通过栈来实现表达式求值。具体步骤如下：

1. 定义一个栈来存储操作数和运算符。

2. 从左到右扫描表达式中的每个字符。

3. 如果是数字，则将其压入栈中。

4. 如果是运算符，则将其与栈顶元素进行比较。

5. 如果栈顶元素优先级大于等于该运算符，则弹出栈顶元素并将其作为右操作数，再弹出栈顶元素并将其作为左操作数，将运算结果压入栈中。

6. 如果栈顶元素优先级小于该运算符，则将该运算符压入栈中。

7. 重复3-6步，直到扫描完整个表达式。

8. 最后栈中只剩下一个元素，即表达式的最终结果。

下面是一个简单的C语言代码实现：

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

#define STACK_MAX_SIZE 100

typedef struct {
    int top;
    int data[STACK_MAX_SIZE];
} Stack;

void stack_init(Stack *s) {
    s->top = -1;
}

int stack_empty(Stack *s) {
    return s->top == -1;
}

int stack_full(Stack *s) {
    return s->top == STACK_MAX_SIZE - 1;
}

int stack_push(Stack *s, int value) {
    if (stack_full(s)) {
        return 0;
    }
    s->data[++s->top] = value;
    return 1;
}

int stack_pop(Stack *s) {
    if (stack_empty(s)) {
        return 0;
    }
    return s->data[s->top--];
}

int stack_top(Stack *s) {
    if (stack_empty(s)) {
        return 0;
    }
    return s->data[s->top];
}

int is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int operator_priority(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}

int calculate(int left, int right, char op) {
    switch (op) {
        case '+': return left + right;
        case '-': return left - right;
        case '*': return left * right;
        case '/': return left / right;
        default: return 0;
    }
}

int evaluate_expression(char *expression) {
    Stack op_stack, num_stack;
    stack_init(&op_stack);
    stack_init(&num_stack);

    int len = strlen(expression);
    for (int i = 0; i < len; i++) {
        if (isdigit(expression[i])) {
            int num = 0;
            while (isdigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            i--;
            stack_push(&num_stack, num);
        } else if (is_operator(expression[i])) {
            int op_priority = operator_priority(expression[i]);
            while (!stack_empty(&op_stack) && operator_priority(stack_top(&op_stack)) >= op_priority) {
                int right = stack_pop(&num_stack);
                int left = stack_pop(&num_stack);
                char op = stack_pop(&op_stack);
                int result = calculate(left, right, op);
                stack_push(&num_stack, result);
            }
            stack_push(&op_stack, expression[i]);
        }
    }

    while (!stack_empty(&op_stack)) {
        int right = stack_pop(&num_stack);
        int left = stack_pop(&num_stack);
        char op = stack_pop(&op_stack);
        int result = calculate(left, right, op);
        stack_push(&num_stack, result);
    }

    return stack_pop(&num_stack);
}

int main() {
    char expression[100];
    printf("请输入表达式：");
    fgets(expression, sizeof(expression), stdin);
    expression[strcspn(expression, "\n")] = '\0';
    int result = evaluate_expression(expression);
    printf("表达式的结果为：%d\n", result);
    return 0;
}

以上代码将输入的中缀表达式转换为后缀表达式并计算结果。