在递归函数中调用函数时出现'double free or corruption‘错误

Question

我有一个递归函数solveCountdownProblem，它调用evaluateCountdown，它接受反向波兰语表示法格式的表达式。evaluateCountdown位于一系列嵌套的for循环中(在solveCountdownProblem中)，因此经常被调用。

double evaluateCountdown(string rpnIn) {
    vector<double> stack;
    double a = 0, b = 0;
    string token = "";
    char arithToken;
    
    for (int i = 0; i < rpnIn.size(); ++i) {
        if (rpnIn[i] == ' ') {
            if (token != "") {
                stack.push_back(stod(token)); // Push number to stack   
                token = "";
            }
        } else {
            if (find(arithOperators.begin(), arithOperators.end(), rpnIn[i]) != arithOperators.end()) { //if char is arithmetic operator
                // Pop two numbers of stack and perform operation
                // Push result back into stack
                arithToken = rpnIn[i];
                a = stack.back(); stack.pop_back(); // pops and removes elements
                b = stack.back(); stack.pop_back();
                if (arithToken == '+') {
                    stack.push_back(b+a);
                } else if (arithToken == '-'){
                    stack.push_back(b-a);
                } else if (arithToken == '/') {
                    stack.push_back(b/a);
                } else if (arithToken == '*') {
                    stack.push_back(b*a);
                }
            } else {
                token += rpnIn[i]; //add chars to string
            }
        }
    }

    return stack.back();
}

它在一段时间后产生正确的计算结果，但最终我得到了一个内存错误‘双重释放或损坏(out)’。我已经使用gdb进行了调试，它产生了这个回溯。

Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
50  ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) backtrace
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x00007ffff7bee859 in __GI_abort () at abort.c:79
#2  0x00007ffff7c593ee in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7ffff7d83285 "%s\n") at ../sysdeps/posix/libc_fatal.c:155
#3  0x00007ffff7c6147c in malloc_printerr (str=str@entry=0x7ffff7d85670 "double free or corruption (out)") at malloc.c:5347
#4  0x00007ffff7c63120 in _int_free (av=0x7ffff7db4b80 <main_arena>, p=0x5555555733d0, have_lock=<optimized out>) at malloc.c:4314
#5  0x000055555555a932 in __gnu_cxx::new_allocator<double>::deallocate (this=0x7fffffffd270, __p=0x5555555733e0) at /usr/include/c++/9/ext/new_allocator.h:128
#6  0x0000555555559dc0 in std::allocator_traits<std::allocator<double> >::deallocate (__a=..., __p=0x5555555733e0, __n=4) at /usr/include/c++/9/bits/alloc_traits.h:470
#7  0x000055555555932e in std::_Vector_base<double, std::allocator<double> >::_M_deallocate (this=0x7fffffffd270, __p=0x5555555733e0, __n=4) at /usr/include/c++/9/bits/stl_vector.h:351
#8  0x00005555555588fe in std::_Vector_base<double, std::allocator<double> >::~_Vector_base (this=0x7fffffffd270, __in_chrg=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:332
#9  0x0000555555558953 in std::vector<double, std::allocator<double> >::~vector (this=0x7fffffffd270, __in_chrg=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:680
#10 0x0000555555556a9a in evaluateCountdown (rpnIn="4 6 5 * + +") at Countdown.h:58
#11 0x0000555555557762 in solveCountdownProblem (operands=std::vector of length 3, capacity 4 = {...}, targetValue=21) at Countdown.h:172
#12 0x0000555555556d61 in solveCountdownProblem (operands=std::vector of length 4, capacity 5 = {...}, targetValue=21) at Countdown.h:113
#13 0x0000555555556d61 in solveCountdownProblem (operands=std::vector of length 5, capacity 6 = {...}, targetValue=21) at Countdown.h:113
#14 0x0000555555556d61 in solveCountdownProblem (operands=std::vector of length 6, capacity 6 = {...}, targetValue=21) at Countdown.h:113
#15 0x0000555555557e17 in main () at TestCountdown.cpp:19

它似乎指向“向量栈”这一行；但是我不确定为什么我会得到一个内存错误。析构函数一旦超出作用域，难道不会自动释放'stack‘吗？

Answer 1

如果查看计算后的字符串"4 6 5 * + +"，就会发现最后一个操作+没有足够的操作数，并且在代码中，在两次调用stack.pop_back()之前没有检查stack是否有足够的元素。您需要添加该检查并执行相应的操作。可能最干净的方法是将popping封装在一个函数中：

double pop( std::vector<double> &stack )
{
    if( stack.empty() ) { // throw exception, return NaN or whatever logic of your program requires
       ...
    }
    auto r = stack.back();
    stack.pop_back();
    return r;
}

那么你的代码就会变得更短更整洁：

            // Pop two numbers of stack and perform operation
            // Push result back into stack
            arithToken = rpnIn[i];
            double a = pop( stack ); // pops and removes elements
            double b = pop( stack );

(更好的做法是在需要的时候声明和初始化变量，而不是提前)