C语言利用栈将中缀表达式转换成后缀表达式并进行运算

以下是利用栈将中缀表达式转换成后缀表达式并进行运算的C语言代码：

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

typedef struct stack_node {
    char data;
    struct stack_node *next;
} stack_node;

typedef struct {
    stack_node *top;
} stack;

stack *create_stack() {
    stack *s = (stack *)malloc(sizeof(stack));
    s->top = NULL;
    return s;
}

void push(stack *s, char c) {
    stack_node *node = (stack_node *)malloc(sizeof(stack_node));
    node->data = c;
    node->next = s->top;
    s->top = node;
}

char pop(stack *s) {
    if (s->top == NULL) {
        printf("Error: stack is empty\n");
        exit(1);
    }
    char c = s->top->data;
    stack_node *temp = s->top;
    s->top = s->top->next;
    free(temp);
    return c;
}

char peek(stack *s) {
    if (s->top == NULL) {
        printf("Error: stack is empty\n");
        exit(1);
    }
    return s->top->data;
}

int is_empty(stack *s) {
    return (s->top == NULL);
}

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

int precedence(char c) {
    switch (c) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

char *infix_to_postfix(char *infix) {
    stack *s = create_stack();
    char *postfix = (char *)malloc(sizeof(char) * (strlen(infix) + 1));
    int i, j;
    for (i = 0, j = 0; infix[i] != '\0'; i++) {
        if (isdigit(infix[i])) {
            postfix[j++] = infix[i];
        } else if (is_operator(infix[i])) {
            while (!is_empty(s) && is_operator(peek(s)) && precedence(peek(s)) >= precedence(infix[i])) {
                postfix[j++] = pop(s);
            }
            push(s, infix[i]);
        } else if (infix[i] == '(') {
            push(s, infix[i]);
        } else if (infix[i] == ')') {
            while (!is_empty(s) && peek(s) != '(') {
                postfix[j++] = pop(s);
            }
            if (is_empty(s)) {
                printf("Error: mismatched parentheses\n");
                exit(1);
            }
            pop(s);
        } else {
            printf("Error: invalid character\n");
            exit(1);
        }
    }
    while (!is_empty(s)) {
        if (peek(s) == '(') {
            printf("Error: mismatched parentheses\n");
            exit(1);
        }
        postfix[j++] = pop(s);
    }
    postfix[j] = '\0';
    return postfix;
}

int evaluate_postfix(char *postfix) {
    stack *s = create_stack();
    int i, operand1, operand2, result;
    for (i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i])) {
            push(s, postfix[i] - '0');
        } else if (is_operator(postfix[i])) {
            operand2 = pop(s);
            operand1 = pop(s);
            switch (postfix[i]) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                case '/':
                    if (operand2 == 0) {
                        printf("Error: division by zero\n");
                        exit(1);
                    }
                    result = operand1 / operand2;
                    break;
            }
            push(s, result);
        } else {
            printf("Error: invalid character\n");
            exit(1);
        }
    }
    result = pop(s);
    if (!is_empty(s)) {
        printf("Error: invalid expression\n");
        exit(1);
    }
    return result;
}

int main() {
    char infix[100], *postfix;
    int result;
    printf("Enter an infix expression: ");
    scanf("%s", infix);
    postfix = infix_to_postfix(infix);
    printf("Postfix expression: %s\n", postfix);
    result = evaluate_postfix(postfix);
    printf("Result: %d\n", result);
    free(postfix);
    return 0;
}

该程序中，`stack_node`结构体表示栈中的节点，包含一个字符类型的数据`data`和一个指向下一个节点的指针`next`。`stack`结构体表示栈，包含一个指向栈顶节点的指针`top`。`create_stack`函数用于创建一个空栈，`push`函数用于将一个字符压入栈中，`pop`函数用于弹出栈顶字符，`peek`函数用于获取栈顶字符而不弹出，`is_empty`函数用于判断栈是否为空。

`is_operator`函数用于判断一个字符是否为运算符，`precedence`函数用于获取运算符的优先级。`infix_to_postfix`函数用于将中缀表达式转换成后缀表达式，采用经典的算法：从左到右遍历中缀表达式，如果是数字直接输出到后缀表达式中，如果是左括号入栈，如果是右括号则弹出栈中的元素直到遇到左括号，如果是运算符则弹出栈中优先级大于等于它的元素并输出到后缀表达式中，然后将自己入栈。最后将栈中剩余的元素弹出并输出到后缀表达式中。在转换过程中需要处理一些错误情况，如不合法的字符、不匹配的括号等。

`evaluate_postfix`函数用于计算后缀表达式的值，也是采用经典的算法：从左到右遍历后缀表达式，如果是数字则入栈，如果是运算符则弹出栈中的两个操作数进行运算，并将结果入栈。最后栈中剩下的元素就是表达式的值。

在`main`函数中，首先读入中缀表达式，然后调用`infix_to_postfix`函数将其转换成后缀表达式，并输出后缀表达式。接着调用`evaluate_postfix`函数计算后缀表达式的值，并输出结果。最后释放动态分配的内存。