C++中缀转后缀程序出现free() invalid pointer错误如何解决

核心报错原因（free() invalid pointer） #

你出现free() invalid pointer的直接原因是原始内存分配的首地址被覆盖丢失：

• 你在setexpr方法中给成员指针s、t分配了堆内存，保存了new返回的首地址
• 但在convert方法中你直接对s、t执行++操作偏移指针，到convert执行结束时，s和t已经指向了字符串末尾，不再是最初new返回的地址
• 析构函数执行delete[] s和delete[] t时，传入的不是堆内存分配的合法首地址，直接触发内存错误

其他逻辑问题 #

• show方法输出的t已经偏移到后缀表达式末尾，只会输出空值或者乱码
• 缺少<cctype>头文件，isdigit、isalpha函数行为未定义
• 处理数字后没有判断当前是否已经遍历完输入串，后续判断逻辑可能访问空指针
• 处理右括号时没有做栈空校验，输入括号不匹配时会触发异常

修复方案 #

1. 新增临时指针遍历输入串和写入后缀表达式，不要修改s、t的原始首地址
2. 补充缺失的头文件
3. 增加边界校验逻辑

修复后完整代码 #

#include<iostream>
#include<string.h>
#include<cctype>
using namespace std;

const int MAX=50;

class infix{
private:
    char Stack[MAX];
    char *s,*t; // 始终保存内存分配的首地址，不做偏移
    int top;
public:
    infix();
    ~infix();
    void setexpr(char *s);
    void push(char c);
    char pop();
    void convert();
    int priority(char c);
    void show();
};

infix::infix(){
    top=-1;
    s = nullptr;
    t = nullptr;
}

infix::~infix(){
    if(s) delete[] s;
    if(t) delete[] t;
}

void infix::setexpr(char *str){
    s=new char[strlen(str)+1];
    t=new char[strlen(str)+1];
    strcpy(s,str);
}

void infix::push(char c){
    if(top==MAX-1)
        cout<<"Stack is full.";
    else
        Stack[++top]=c;
}

char infix::pop(){
    if(top==-1){
        cout<<"Stack is empty";
        return -1;
    }
    else
        return Stack[top--];
}

void infix::convert(){
    char *p = s; // 用临时指针遍历输入
    char *q = t; // 用临时指针写后缀表达式
    while(*p){
        if(*p==' ' || *p=='\t'){
            p++;
            continue;
        }

        if(isdigit(*p) || isalpha(*p)){
            while(isdigit(*p) || isalpha(*p)){
                *q=*p;
                p++;
                q++;
            }
        }
        if(*p == '\0') break; // 遍历完直接退出

        if(*p=='('){
            push(*p);
            p++;
        }

        char opr;
        if(*p=='*' ||*p=='+' ||*p=='/' ||*p=='%' ||*p=='-' ||*p=='$'){
            int flag=1;
            if(top!=-1){
                opr=pop();
                while(priority(opr)>=priority(*p)){
                    *q=opr;
                    q++;
                    if(top!=-1)
                        opr=pop();
                    else{
                        flag=0;
                        break;
                    }
                }
                if(flag)
                    push(opr);
                push(*p);
            }
            else
                push(*p);
            p++;
        }

        if(*p==')'){
            opr=pop();
            while(opr!='(' && top != -1){
                *q=opr;
                q++;
                opr=pop();
            }
            p++;
        }
    }
    while(top!=-1){
        char opr=pop();
        *q=opr;
        q++;
    }
    *q='\0';
}

int infix::priority(char c){
    if(c=='$')
        return 3;
    if(c=='*' || c=='/'||c=='%')
        return 2;
    else if(c=='+' || c=='-')
        return 1;
    else
        return 0;
}

void infix::show(){
    cout<<t<<endl;
}

int main(){
    char expr[MAX];
    infix q;
    cout<<"\nEnter an expression in infix form :";
    cin.getline(expr,MAX,'\n');

    q.setexpr(expr);
    q.convert();

    cout<<"\nThe postfix expression is :";
    q.show();

    return 0;
}

测试结果 #

输入测试用例4$2*3-3+8/4/(1+1)，输出结果为42$3*3-84/11+/+，符合手动推演结果。

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