C语言中缀转后缀表达式后求值功能异常排查求助

核心错误点 #

• 类型与野指针问题
  • 原有struct stack的存储数组为char类型，无法存放求值过程中的float类型结果，会出现精度截断甚至数据错误
  • 求值函数evaulate内部的栈指针sp、main函数中传入的栈指针sp均为未分配内存的野指针，仅赋值top属于非法内存访问，直接导致程序崩溃
  • main函数中将infixToPostfix返回的char*类型字符串错误赋值给char类型变量oprnd，类型不匹配导致后续传参完全错误
  • 输出求值结果时用%d格式化float类型返回值，输出内容会完全错乱
• 中缀转后缀逻辑缺陷
  • 栈空时调用stackTop会访问arr[-1]非法内存，栈空状态下遇到运算符应该直接入栈不需要判断优先级
  • 仅支持单个数字的操作数，无法识别多位数（如示例中的20、15），转后缀时会将多位数拆分为单个字符，后续求值无法正确识别
• 求值函数逻辑错误
  • 第二个参数定义错误，应为char* postfix而非char* postfix[]
  • 用于判断运算符的变量ch从未赋值，运算符分支永远不会触发
  • 用atoi转换运算符字符没有意义，直接判断postfix[i]即可
  • push1的入参为char类型，传入float类型的计算结果会被强制转换丢失数据

修复后完整代码 #

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

// 运算符栈，用于中缀转后缀
struct OprStack {
    int size;
    int top;
    char *arr;
};

// 数值栈，用于后缀求值
struct NumStack {
    int size;
    int top;
    float *arr;
};

// 运算符栈操作
int isOprEmpty(struct OprStack *ptr) {
    return ptr->top == -1;
}

int isOprFull(struct OprStack *ptr) {
    return ptr->top == ptr->size - 1;
}

void pushOpr(struct OprStack* ptr, char val) {
    if(isOprFull(ptr)) {
        printf("Stack Overflow! Cannot push %c to the stack\n", val);
        return;
    }
    ptr->arr[++ptr->top] = val;
}

char popOpr(struct OprStack* ptr) {
    if(isOprEmpty(ptr)) {
        printf("Stack Underflow! Cannot pop from the operator stack\n");
        return -1;
    }
    return ptr->arr[ptr->top--];
}

char stackTopOpr(struct OprStack* sp) {
    if(isOprEmpty(sp)) return 0;
    return sp->arr[sp->top];
}

// 数值栈操作
int isNumEmpty(struct NumStack *ptr) {
    return ptr->top == -1;
}

int isNumFull(struct NumStack *ptr) {
    return ptr->top == ptr->size - 1;
}

void pushNum(struct NumStack* ptr, float val) {
    if(isNumFull(ptr)) {
        printf("Stack Overflow! Cannot push %f to the stack\n", val);
        return;
    }
    ptr->arr[++ptr->top] = val;
}

float popNum(struct NumStack* ptr) {
    if(isNumEmpty(ptr)) {
        printf("Stack Underflow! Cannot pop from the number stack\n");
        return -1;
    }
    return ptr->arr[ptr->top--];
}

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

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

// 中缀转后缀，多位数用空格分隔
char* infixToPostfix(char* infix) {
    struct OprStack * sp = (struct OprStack *) malloc(sizeof(struct OprStack));
    sp->size = 100;
    sp->top = -1;
    sp->arr = (char *) malloc(sp->size * sizeof(char));
    char * postfix = (char *) malloc((strlen(infix)*2 +1) * sizeof(char)); // 预留空格位置
    int i=0, j = 0;
    while (infix[i]!='\0') {
        if(isdigit(infix[i])) {
            // 处理多位数，连续数字直接存，后面加空格分隔
            while(isdigit(infix[i])) {
                postfix[j++] = infix[i++];
            }
            postfix[j++] = ' ';
        } else if(isOperator(infix[i])) {
            while(!isOprEmpty(sp) && precedence(infix[i]) <= precedence(stackTopOpr(sp))) {
                postfix[j++] = popOpr(sp);
                postfix[j++] = ' ';
            }
            pushOpr(sp, infix[i]);
            i++;
        } else {
            i++; // 跳过非法字符
        }
    }
    while (!isOprEmpty(sp)) {
        postfix[j++] = popOpr(sp);
        postfix[j++] = ' ';
    }
    postfix[--j] = '\0'; // 去掉最后多余的空格
    free(sp->arr);
    free(sp);
    return postfix;
}

float evaluate(char *postfix) {
    struct NumStack *sp = (struct NumStack *) malloc(sizeof(struct NumStack));
    sp->size = 100;
    sp->top = -1;
    sp->arr = (float *) malloc(sp->size * sizeof(float));
    int i = 0;
    float num, a, b, res;
    while(postfix[i] != '\0') {
        if(isdigit(postfix[i])) {
            // 解析多位数
            num = 0;
            while(isdigit(postfix[i])) {
                num = num * 10 + (postfix[i] - '0');
                i++;
            }
            pushNum(sp, num);
        } else if(isOperator(postfix[i])) {
            a = popNum(sp);
            b = popNum(sp);
            switch(postfix[i]) {
                case '*': res = b * a; break;
                case '+': res = b + a; break;
                case '-': res = b - a; break;
                case '/': res = b / a; break;
                default: res = 0;
            }
            pushNum(sp, res);
            i++;
        } else {
            i++; // 跳过空格
        }
    }
    res = popNum(sp);
    free(sp->arr);
    free(sp);
    return res;
}

int main() {
    char * infix = "20-15/5-3*2";
    char * postfix = infixToPostfix(infix);
    printf("postfix is %s\n", postfix);
    float result = evaluate(postfix);
    printf("result is::%.2f\n", result);
    free(postfix); // 释放内存
    return 0;
}

运行示例输出：

postfix is 20 15 5 / - 3 2 * -
result is::11.00

内容的提问来源于stack exchange，提问作者Azqaf