Блог

У меня есть рекурсивная функция 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();
}
  

Через некоторое время он работает, производя правильные вычисления, но в конечном итоге я получаю ошибку памяти ‘double free или corruption (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 "%sn") 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

  

Кажется, это указывает на строку ‘векторный стек;’ но я не уверен, почему я получаю ошибку памяти. Разве деструктор автоматически не освобождает «стек», когда он выходит за рамки?

Если вы посмотрите на вычисляемую строку "4 6 5 * " , вы увидите, что для последней операции недостаточно операндов , и в вашем коде вы не проверяете, stack достаточно ли элементов перед stack.pop_back() повторным вызовом. Вам нужно добавить эту проверку и действовать соответствующим образом. Вероятно, самый чистый способ — обернуть popping в функцию:

 double pop( std::vector<double> amp;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 );
  

(и лучше объявлять и инициализировать переменные, когда они вам нужны, а не заранее)