Как динамически развернуть строку в C

Question

У меня есть функция, которая рекурсивно делает некоторые вычисления для набора чисел. Я хочу также красиво распечатать вычисления в каждом вызове рекурсии, передав строку из предыдущего вычисления и конкатенируя ее с текущей операцией. Пример вывода может выглядеть следующим образом:

3
(3) + 2
((3) + 2) / 4
(((3) + 2) / 4) x 5
((((3) + 2) / 4) x 5) + 14
... and so on

Итак, второй вызов получает 3 и добавляет + 2 к нему, третий вызов проходит (3) + 2 и т. Д. Мой прототип рекурсивной функции выглядит так:

void calc_rec(int input[], int length, char * previous_string);

Я написал 2 вспомогательные функции, чтобы помочь мне с операцией, но они взрываются, когда я проверяю их:

/**********************************************************************
 * dynamically allocate and append new string to old string and return a pointer to it
 **********************************************************************/
 char * strapp(char * old, char * new)
 {
     // find the size of the string to allocate
     int len = sizeof(char) * (strlen(old) + strlen(new));

     // allocate a pointer to the new string
     char * out = (char*)malloc(len);

     // concat both strings and return
     sprintf(out, "%s%s", old, new);

     return out;
 }

/**********************************************************************
 * returns a pretty math representation of the calculation op
 **********************************************************************/
 char * mathop(char * old, char operand, int num)
 {
     char * output, *newout;
     char fstr[50]; // random guess.. couldn't think of a better way.
     sprintf(fstr, " %c %d", operand, num);
     output = strapp(old, fstr);
     newout = (char*)malloc( 2*sizeof(char)+sizeof(output) );
     sprintf(newout, "(%s)", output);
     free(output);
     return newout;  
 }


void test_mathop()
{
    int i, total = 10;
    char * first = "3";
    printf("in test_mathop\n");
    while (i < total)
    {
        first = mathop(first, "+", i);
        printf("%s\n", first);
        ++i;
    }
}

strapp () возвращает указатель на вновь добавленные строки (works), а mathop () должен принимать старую строку вычисления ("(3) +2"), операнд с символом ('+', '-' и т. д.) и int, и возвращают указатель на новую строку, например "((3) +2) / 3". Есть идеи, где я все испортил? спасибо.

Answer 1

Вы должны выделить дополнительный байт для завершающего 0.

И вы должны использовать strlen вместо sizeof здесь:

newout = (char*)malloc( 2*sizeof(char)+sizeof(output) );

Sizeof возвращает размер char* (что-то вроде 4 в средней системе) вместо длины строки, на которую указывает output.

Более того, как правильно заметил @Agnel, i неинициализирован, хотя это не приводит к сбою вашей программы, просто выполните цикл случайное число раз.

Кроме того, я бы порекомендовал strstr strcat для объединения ваших строк.

Answer 2

Попробуйте, для начала:

char * append_strings(const char * old, const char * new)
{
    // find the size of the string to allocate
    size_t len = strlen(old) + strlen(new) + 1;

    // allocate a pointer to the new string
    char *out = malloc(len);

    // concat both strings and return
    sprintf(out, "%s%s", old, new);

    return out;
}

Это просто ваш код с рядом исправлений:

• Входные строки не изменены, поэтому они должны быть объявлены const.
• Добавьте единицу к размеру, необходимому для нового буфера, чтобы было место для терминатора.
• Длина строк лучше всего хранить в переменных типа size_t.
• Удалено ненужное масштабирование на sizeof (char).
• Не разыгрывайте возвращение malloc().
• Не определяйте функции, имена которых начинаются с str, это зарезервированное пространство. Указано комментатором, спасибо!

Для производительности вы можете использовать тот факт, что вы звоните strlen() на оба входа, и избегать использования sprintf():

char * append_strings(const char * old, const char * new)
{
    // find the size of the string to allocate
    const size_t old_len = strlen(old), new_len = strlen(new);
    const size_t out_len = old_len + new_len + 1;

    // allocate a pointer to the new string
    char *out = malloc(out_len);

    // concat both strings and return
    memcpy(out, old, old_len);
    memcpy(out + old_len, new, new_len + 1);

    return out;
}

Это должно быть немного быстрее, но я не проверял это. Обратите внимание, что окончательный memcpy() включает терминатор из строки new, поэтому нет необходимости устанавливать его вручную.

Answer 3

Одна непосредственная проблема, которую я вижу:

int len = sizeof(char) * (strlen(old) + strlen(new));

не выделяет место для символа NULL в конце. Таким образом, вам нужно выделить один дополнительный символ.

Answer 4

Спасибо за все ответы, они были очень полезны - особенно предложения strcat и выяснение того, что мне нужно выделить место для символа \ 0В итоге я использовал realloc, чтобы «растянуть» строку и добавить начальные и конечные символы.Я также исключил функцию strapp (append_strings) и заставил все это работать внутри mathop.Вот как:

/**********************************************************************
 * returns a pretty math representation of the calculation op
 **********************************************************************/
 char * mathop(char * previous, char operand, float num)
 {
     char *output, *temp, calculation[50];
     size_t newlen;

     // copy the previous data into the temp string     
     temp = (char*)malloc( strlen(previous) + 1 );
     output = (char*)malloc(2);

     strcpy(temp, previous);
     strcpy(output, "(\0");

     // create the string portion to append to the output
     sprintf(calculation, " %c %.1f)\0", operand, num);

     // reallocate the output to append the additional string
     newlen = strlen(temp) + strlen(calculation) + 1;
     temp = realloc(temp, newlen);

     // append the new data to output
     strcat(temp, calculation);
     output = realloc(output, strlen(temp) + 2);
     strcat(output, temp);
     printf("%s\n", output);

     free(temp);
     return output;  
 }

еще раз спасибо!