用c语言实现中缀表达式的计算

以下是一个用C语言实现中缀表达式的计算的示例程序：

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

#define MAX_STACK_SIZE 100

typedef struct {
    int top;
    int stack[MAX_STACK_SIZE];
} Stack;

void push(Stack *s, int value) {
    if (s->top >= MAX_STACK_SIZE) {
        printf("Stack overflow\n");
        exit(EXIT_FAILURE);
    }
    s->stack[++s->top] = value;
}

int pop(Stack *s) {
    if (s->top < 0) {
        printf("Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return s->stack[s->top--];
}

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

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

int evaluate_expression(char *expr) {
    Stack operand_stack;
    operand_stack.top = -1;
    Stack operator_stack;
    operator_stack.top = -1;

    int i, len = strlen(expr);
    for (i = 0; i < len; i++) {
        if (isspace(expr[i])) {
            continue;
        } else if (isdigit(expr[i])) {
            int value = 0;
            while (isdigit(expr[i])) {
                value = value * 10 + (expr[i] - '0');
                i++;
            }
            push(&operand_stack, value);
            i--;
        } else if (is_operator(expr[i])) {
            while (operator_stack.top >= 0 && precedence(operator_stack.stack[operator_stack.top]) >= precedence(expr[i])) {
                int op2 = pop(&operand_stack);
                int op1 = pop(&operand_stack);
                int operator = pop(&operator_stack);
                switch (operator) {
                    case '+':
                        push(&operand_stack, op1 + op2);
                        break;
                    case '-':
                        push(&operand_stack, op1 - op2);
                        break;
                    case '*':
                        push(&operand_stack, op1 * op2);
                        break;
                    case '/':
                        push(&operand_stack, op1 / op2);
                        break;
                    default:
                        break;
                }
            }
            push(&operator_stack, expr[i]);
        } else {
            printf("Invalid character: %c\n", expr[i]);
            exit(EXIT_FAILURE);
        }
    }

    while (operator_stack.top >= 0) {
        int op2 = pop(&operand_stack);
        int op1 = pop(&operand_stack);
        int operator = pop(&operator_stack);
        switch (operator) {
            case '+':
                push(&operand_stack, op1 + op2);
                break;
            case '-':
                push(&operand_stack, op1 - op2);
                break;
            case '*':
                push(&operand_stack, op1 * op2);
                break;
            case '/':
                push(&operand_stack, op1 / op2);
                break;
            default:
                break;
        }
    }

    return pop(&operand_stack);
}

int main() {
    char expr[] = "3 + 4 * 2 / ( 1 - 5 )";
    printf("%s = %d\n", expr, evaluate_expression(expr));
    return 0;
}

该程序使用两个栈来实现中缀表达式的计算。其中，操作数栈用于存储操作数，操作符栈用于存储操作符。程序从左到右扫描表达式，遇到操作数则将其压入操作数栈中，遇到操作符则比较其与操作符栈栈顶操作符的优先级，若优先级较高则将其压入操作符栈中，否则将操作符栈栈顶的操作符弹出，同时弹出操作数栈栈顶的两个操作数进行计算，将结果压入操作数栈中，直到操作符栈为空或栈顶操作符的优先级较低为止。最后，操作符栈中剩余的操作符也需要进行相应的计算。

本程序仅支持整数的四则运算，对于浮点数、括号、负数、指数等情况尚未进行处理。