表达式求值：将中缀表达式转换为后缀表达式，然后使用栈来进行计算。，用c语言实现

下面是一个用 C 语言实现中缀表达式转后缀表达式并计算的示例代码：

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

#define MAX_EXPR_LEN 100
#define MAX_STACK_SIZE 100

typedef struct {
    int top;
    char data[MAX_STACK_SIZE];
} Stack;

void push(Stack *s, char c) {
    if (s->top < MAX_STACK_SIZE - 1) {
        s->top++;
        s->data[s->top] = c;
    } else {
        printf("Stack overflow!");
        exit(1);
    }
}

char pop(Stack *s) {
    if (s->top >= 0) {
        char c = s->data[s->top];
        s->top--;
        return c;
    } else {
        printf("Stack underflow!");
        exit(1);
    }
}

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

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

void infix_to_postfix(char *infix_expr, char *postfix_expr) {
    Stack s;
    s.top = -1;
    int i = 0, j = 0;
    while (infix_expr[i] != '\0') {
        if (isdigit(infix_expr[i])) {
            postfix_expr[j] = infix_expr[i];
            j++;
        } else if (is_operator(infix_expr[i])) {
            while (s.top >= 0 && precedence(s.data[s.top]) >= precedence(infix_expr[i])) {
                postfix_expr[j] = pop(&s);
                j++;
            }
            push(&s, infix_expr[i]);
        } else if (infix_expr[i] == '(') {
            push(&s, infix_expr[i]);
        } else if (infix_expr[i] == ')') {
            while (s.top >= 0 && s.data[s.top] != '(') {
                postfix_expr[j] = pop(&s);
                j++;
            }
            pop(&s); // pop the left parenthesis
        }
        i++;
    }
    while (s.top >= 0) {
        postfix_expr[j] = pop(&s);
        j++;
    }
    postfix_expr[j] = '\0';
}

int evaluate_postfix(char *postfix_expr) {
    Stack s;
    s.top = -1;
    int i = 0;
    while (postfix_expr[i] != '\0') {
        if (isdigit(postfix_expr[i])) {
            push(&s, postfix_expr[i] - '0');
        } else if (is_operator(postfix_expr[i])) {
            int operand2 = pop(&s);
            int operand1 = pop(&s);
            switch (postfix_expr[i]) {
                case '+':
                    push(&s, operand1 + operand2);
                    break;
                case '-':
                    push(&s, operand1 - operand2);
                    break;
                case '*':
                    push(&s, operand1 * operand2);
                    break;
                case '/':
                    push(&s, operand1 / operand2);
                    break;
            }
        }
        i++;
    }
    return pop(&s);
}

int main() {
    char infix_expr[MAX_EXPR_LEN];
    char postfix_expr[MAX_EXPR_LEN];
    printf("Enter an infix expression: ");
    fgets(infix_expr, MAX_EXPR_LEN, stdin);
    infix_to_postfix(infix_expr, postfix_expr);
    printf("Postfix expression: %s\n", postfix_expr);
    int result = evaluate_postfix(postfix_expr);
    printf("Result: %d\n", result);
    return 0;
}

在上面的示例代码中，我们实现了两个函数：`infix_to_postfix` 和 `evaluate_postfix`。`infix_to_postfix` 函数将中缀表达式转换为后缀表达式，`evaluate_postfix` 函数计算后缀表达式的值。

在 `infix_to_postfix` 函数中，我们使用了一个 `Stack` 结构体来维护运算符的优先级和顺序。对于每个字符，我们执行以下操作：

1. 如果是数字，直接将其添加到后缀表达式中。

2. 如果是运算符，将其与栈顶的运算符比较，如果栈顶的运算符优先级大于等于当前运算符，则将栈顶的运算符弹出并添加到后缀表达式中，直到栈顶的运算符优先级小于当前运算符或栈为空，然后将当前运算符压入栈中。

3. 如果是左括号，将其压入栈中。

4. 如果是右括号，将栈顶的运算符弹出并添加到后缀表达式中，直到遇到左括号，然后将左括号弹出。

最后，将栈中剩余的运算符弹出并添加到后缀表达式中。

在 `evaluate_postfix` 函数中，我们使用了相同的 `Stack` 结构体来计算后缀表达式的值。对于每个字符，我们执行以下操作：

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

2. 如果是运算符，弹出栈顶的两个操作数，执行相应的运算，并将结果压入栈中。

最后，弹出栈中的唯一元素，即为后缀表达式的值。

在 `main` 函数中，我们首先读取用户输入的中缀表达式，然后调用 `infix_to_postfix` 函数将其转换为后缀表达式，并输出后缀表达式。最后，我们调用 `evaluate_postfix` 函数计算后缀表达式的值，并输出结果。