C语言：计算中缀表达式

以下是C语言代码实现：

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

#define MAX_SIZE 100

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

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

void push(Stack *s, int x) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack overflow!\n");
        exit(1);
    } else {
        s->top++;
        s->data[s->top] = x;
    }
}

int pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack underflow!\n");
        exit(1);
    } else {
        int x = s->data[s->top];
        s->top--;
        return x;
    }
}

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

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

int peek(Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty!\n");
        exit(1);
    } else {
        return s->data[s->top];
    }
}

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

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

int evaluate(int a, int b, char op) {
    if (op == '+') {
        return a + b;
    } else if (op == '-') {
        return a - b;
    } else if (op == '*') {
        return a * b;
    } else if (op == '/') {
        return a / b;
    } else {
        printf("Invalid operator!\n");
        exit(1);
    }
}

int evaluateExpression(char *exp) {
    Stack operandStack, operatorStack;
    initStack(&operandStack);
    initStack(&operatorStack);

    int i = 0;
    while (exp[i] != '\0') {
        if (isdigit(exp[i])) {
            int num = 0;
            while (isdigit(exp[i])) {
                num = num * 10 + (exp[i] - '0');
                i++;
            }
            push(&operandStack, num);
        } else if (isOperator(exp[i])) {
            while (!isEmpty(&operatorStack) && precedence(peek(&operatorStack)) >= precedence(exp[i])) {
                int b = pop(&operandStack);
                int a = pop(&operandStack);
                char op = pop(&operatorStack);
                int result = evaluate(a, b, op);
                push(&operandStack, result);
            }
            push(&operatorStack, exp[i]);
            i++;
        } else if (exp[i] == '(') {
            push(&operatorStack, exp[i]);
            i++;
        } else if (exp[i] == ')') {
            while (peek(&operatorStack) != '(') {
                int b = pop(&operandStack);
                int a = pop(&operandStack);
                char op = pop(&operatorStack);
                int result = evaluate(a, b, op);
                push(&operandStack, result);
            }
            pop(&operatorStack);
            i++;
        } else {
            printf("Invalid character!\n");
            exit(1);
        }
    }

    while (!isEmpty(&operatorStack)) {
        int b = pop(&operandStack);
        int a = pop(&operandStack);
        char op = pop(&operatorStack);
        int result = evaluate(a, b, op);
        push(&operandStack, result);
    }

    return pop(&operandStack);
}

int main() {
    char exp[MAX_SIZE];

    printf("Enter an expression: ");
    fgets(exp, MAX_SIZE, stdin);

    int result = evaluateExpression(exp);

    printf("Result: %d\n", result);

    return 0;
}

这段代码中，我们使用两个栈，一个用于存储操作数，一个用于存储运算符。从左到右遍历表达式中的每一个字符，如果是数字，就把它压入操作数栈中；如果是运算符，就把它压入运算符栈中，但要考虑优先级，需要把优先级高的运算符先计算；如果是左括号，就直接把它压入运算符栈中；如果是右括号，就把栈顶的运算符弹出，并把两个操作数弹出，进行计算，然后把计算结果压入操作数栈中，直到遇到左括号为止。最后，当表达式扫描完毕后，我们需要把运算符栈中的所有运算符都弹出，并进行相应的计算，直到运算符栈为空。最终，操作数栈中剩下的就是表达式的值。