[C++] Ribaltamento stringa con ricorsione

[Iena87]

Mi direste un metodo per ribaltare una stringa utilizzando una procedura ricorsiva?

[LeleFT]

Crei una funzione che prende in input una stringa e restituisce in output l'ultimo carattere della stringa, concatenato al risultato della stessa funzione, a cui viene passata tutta la prima stringa tranne l'ultimo carattere.
Ecco un esempio:

char *ribalta(char *s) {
   char *tmp;
   char *s2;
   tmp = (char *) malloc(strlen(s) * sizeof(char));
   s2 = (char *) malloc(strlen(s) * sizeof(char));
   strcpy(s2, s);
   if (!strlen(s)) {
      strcat(tmp, "");
   } else {
      tmp[0] = s2[strlen(s2)-1];
      s2[strlen(s2)-1] = '\0';
      strcat(tmp, ribalta(s2));
   }
   
   return tmp;
}

Ciao.

[Iena87]

Originariamente inviato da LeleFT
Crei una funzione che prende in input una stringa e restituisce in output l'ultimo carattere della stringa, concatenato al risultato della stessa funzione, a cui viene passata tutta la prima stringa tranne l'ultimo carattere.
Ecco un esempio:

char *ribalta(char *s) {
   char *tmp;
   char *s2;
   tmp = (char *) malloc(strlen(s) * sizeof(char));
   s2 = (char *) malloc(strlen(s) * sizeof(char));
   strcpy(s2, s);
   if (!strlen(s)) {
      strcat(tmp, "");
   } else {
      tmp[0] = s2[strlen(s2)-1];
      s2[strlen(s2)-1] = '\0';
      strcat(tmp, ribalta(s2));
   }
   
   return tmp;
}

Ciao.

Ti ringrazio, ma a trascriverlo in maniera assai + semplice?
Sto ancora ad un basso livello di programmazione...malloc e funzioni riguardanti le stringhe ancore nn li conosco...

[internet]

una soluzione potrebbe essere questa

void ribalta(char* s, int i, int j)
{
  if (i < j)
  {
    /* scambia s[i] <-> s[j] */
    t = s[i]
    s[i] = s[j];
    s[j] = t;
    ribalta(s, i+1, j-1);
  }   
}

la chiamata

ribalta(s, 0, strlen(s)-1);

[anx721]

L'esempio che ti e stato fatto da LeleFT contiene qualche errore, ad esempio alloca un array piu corto di uno di quanto dovrebbe essere, questa è una versione corretta:

1  char *ribalta2(char *s){
2	int len = strlen(s);
3	char * rib_s = (char *)malloc((len + 1) * sizeof(char));
4	rib_s[len] = '\0';
5	if(len == 0)
6		return rib_s;
7	rib_s[0] = s[len - 1];
8	char *tmp = (char *)malloc((len + 1) * sizeof(char));
9	strcpy(tmp, s);
10	tmp[len - 1] = '\0';
11	strcpy(rib_s + 1, ribalta2(tmp));
12	free(tmp);
13	return rib_s;
14 }

quello che fa la funzione è allocare un nuovo array di caratteri rib_s che dovrà contenere la stringa ribaltata (3); quindi l'ultimo carattere della stringa originaria è copiato nella prima posizione della stringa ribaltata (7). La funzione deve poi essere richiamata ricorsivamente sulla stringa originaria 'accorciata di uno': per questo la stringa originaria viene ricopiata in un nuovo array tmp (9) il cui ultimo carattere viene cancellato ponendolo a '\0' in modo da accorciare la stringa tmp di uno (10). Il risultato della chiamata ricorsiva viene quindi appeso dopo il primo carattere della stringa risultato s_rib che stiamo costruendo (11).

[anx721]

Originariamente inviato da internet
una soluzione potrebbe essere questa

void ribalta(char* s, int i, int j)
{
  if (i < j)
  {
    /* scambia s[i] <-> s[j] */
    t = s[i]
    s[i] = s[j];
    s[j] = t;
    ribalta(s, i+1, j-1);
  }   
}

la chiamata

ribalta(s, 0, strlen(s)-1);

Il problema di questa versione è che modifica la stringa originaria e ad esempio non può essere invocata su letterali stringa come:

ribalta("ciao", 0, 3);

perche in C i letterali stringa non possono essere modificati.

[internet]

era sottointeso che la stringa andasse ribaltata in loco visto che non è stato specificato, e comunque anche la funzione
strrev() fa un revere inplace

non vedo il motivo di crearne una nuova dalla funzione

se c'è questa necessità e il cliente che se ne occupa

in c++

std::string myString = "hello";
std::reverse( myString.begin(), myString.end() );

[Iena87]

Grazie mille

[internet]

quest'altra versione usa un parametro in meno

void ribalta(char* s, int n)
{
  char t;

  if (n > 1)
  {
    t = s[0];
    s[0] = s[n-1];
    s[n-1] = t;
    ribalta(s+1, n-2);
  }   
}

la chiamata

ribalta(s, strlen(s));