C语言用栈实现中缀表达式求值代码

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

#define MAXSIZE 100

// 定义栈结构
typedef struct {
    int top;
    double data[MAXSIZE];
} Stack;

// 初始化栈
void InitStack(Stack *s) {
    s->top = -1;
}

// 入栈
void Push(Stack *s, double x) {
    if (s->top == MAXSIZE - 1) {
        printf("Stack Overflow!\n");
        exit(1);
    }
    s->data[++s->top] = x;
}

// 出栈
double Pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack Underflow!\n");
        exit(1);
    }
    return s->data[s->top--];
}

// 获取栈顶元素
double GetTop(Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty!\n");
        exit(1);
    }
    return s->data[s->top];
}

// 判断运算符优先级
int Priority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
            return 0;
        default:
            printf("Invalid operator!\n");
            exit(1);
    }
}

// 中缀表达式求值
double Evaluate(char *exp) {
    Stack s_op; // 运算符栈
    Stack s_num; // 数字栈
    InitStack(&s_op);
    InitStack(&s_num);

    while (*exp != '\0') {
        if (isdigit(*exp) || *exp == '.') { // 数字
            double num = 0.0;
            while (isdigit(*exp) || *exp == '.') {
                num = num * 10 + (*exp - '0');
                exp++;
            }
            if (*exp == ' ') {
                Push(&s_num, num);
            }
        } else if (*exp == '+' || *exp == '-' || *exp == '*' || *exp == '/') { // 运算符
            while (Priority(*exp) <= Priority(GetTop(&s_op))) {
                double b = Pop(&s_num);
                double a = Pop(&s_num);
                char op = Pop(&s_op);
                double result;
                switch (op) {
                    case '+':
                        result = a + b;
                        break;
                    case '-':
                        result = a - b;
                        break;
                    case '*':
                        result = a * b;
                        break;
                    case '/':
                        result = a / b;
                        break;
                }
                Push(&s_num, result);
            }
            Push(&s_op, *exp);
            exp++;
        } else if (*exp == '(') { // 左括号
            Push(&s_op, *exp);
            exp++;
        } else if (*exp == ')') { // 右括号
            while (GetTop(&s_op) != '(') {
                double b = Pop(&s_num);
                double a = Pop(&s_num);
                char op = Pop(&s_op);
                double result;
                switch (op) {
                    case '+':
                        result = a + b;
                        break;
                    case '-':
                        result = a - b;
                        break;
                    case '*':
                        result = a * b;
                        break;
                    case '/':
                        result = a / b;
                        break;
                }
                Push(&s_num, result);
            }
            Pop(&s_op);
            exp++;
        } else { // 空格
            exp++;
        }
    }

    while (s_op.top != -1) { // 将剩余的运算符全部取出并计算
        double b = Pop(&s_num);
        double a = Pop(&s_num);
        char op = Pop(&s_op);
        double result;
        switch (op) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                result = a / b;
                break;
        }
        Push(&s_num, result);
    }

    return Pop(&s_num);
}

int main() {
    char exp[MAXSIZE];
    printf("请输入中缀表达式：");
    fgets(exp, MAXSIZE, stdin);
    printf("表达式的值为：%g\n", Evaluate(exp));
    return 0;
}