Převod řetězce na číslo bez použití funkcí, které to udělají – C / C++ – Fórum – Programujte.com

Ahoj,

Jde mě spíš o popis toho co funkce, která převádí sekvenci znaků na nějaký číselný datový typ dělá. Nebo jak by jste to napsali, kdyby tyto funkce nebyly. 

Pro příklad budeme uvažovat desítkovou soustavu. Při pohledu do ASCII tabulky zjistíš, že "číselné" znaky mají hodnotu v intervalu <0x30, 0x39>, znaménko - má 0x2d. Kontroluješ, co každý znak "obsahuje" a v případě, že je to cifra, zpracuješ ji. V případě prvního znaku to může být i znaménko. Každá cifra má "váhu" danou mocninou základu číselné soustavy - u desítkové soustavy jsou to mocniny deseti:

356 = 3x(10^2) + 5x(10^1) + 6x(10^0)

Z toho pak vyplývá algoritmus zpracování řetězce - jak zjištění, zda obsahuje číslo, tak samotný převod.

hu

#1 Kartik
U převodu čísel se rozlišují dva směry: ze soustavy, ve které umíme počítat, a do soustavy, ve které umíme počítat. Převod do soustavy, ve které umíme počítat, je ten jednodušší. A to je přesně případ převodu čísla ze stringu (rozparsováním číslic máme soustavu, ve které nepočítáme) do binární soustavy (ta ve které počítáme).

Pokud převádíte do soustavy, ve které počítáme, je to v principu jednoduché. Číslice načtené ze stringu vyjádříme jako čísla v cílové soustavě a provedeme operace, tak jak je zdrojová soustava definovaná. U poziční desítkové soustavy to je tak, jak píše hlucheucho (v příkladu budu uvažovat 4 ciferné číslo a a0 znamená nejnižší pozici - a3a2a1a0): 

N = a3*10^3 + a2*10^2 + a1*10^1 + a0*10^0 

(konkrétní příklad viz. příspěvek hlucheucho).

Pro konkrétní algoritmus je dobré si všimnout, že základy se dají postupně vytknout. Tak lze vzoreček upravit do podoby tzv. Hornerova schématu: 

N = ((a3*10 + a2)*10 + a1)*10 + a0

Hornerovo schéma tak dává jednoduchý předpis jak konverzi naimplementovat. Číslo čtu odleva (tak jak jsme jako lidé zvyklí) a pro každou číslici opakuji: předchozí hodnotu vynásobím 10 a číslici přičtu: 

unsigned int stringToInt(const char* numstr_) {
  unsigned int value_ = 0;
  while(*numstr_ != 0) {
    value_ = value_ * 10 + (*numstr_ - '0');
    ++numstr_;
  }
  return value_;
}

(Algoritmus nekontroluje správnost formátu řetězce ani rozsah integeru, je to jenom kostra.)

Algoritmus lze snadno rozšířit na jiné základy (třeba osmičkovou nebo šestnáctkovou soustavu), jen převod číslice z textu na integer není tak jednoduchý jako (*numstr_ - '0').

#3 Staon
Moc dík. Šlo mě o to jak by to mělo být napsané trochu na úrovni, aby to bylo rychlé. Tu jednoduchou konverzi znaků jsem právě napsal a bylo to hrozně pomalé, tak mě zajmalo jestli na to není třeba nějakej matematickej fígl. Šlo klasicky o řetězec v 10kové soustavě. 

Někdy mám pocit, že funkce ze standardní knihovny jsou více optimalizovaný, než by šlo dosáhnout pouze s C nebo C++.

char* text;  //ukazatel na retezec k převodu
int deset = 1;
int signum = 1;
int cislo = 0;
int i = 0;

if(text[0] == '-')
{
   signum = -1;
   i = 1;
}
for( ; text[i] != 0; i++)
{
   if( (text[i] >= '0') && (text[i] <= '9') )
   {
      cislo = cislo * deset + text[i] - '0';
      deset = 10;
   }
   else break;
}
cislo = cislo * signum;

Pro vyšší efektivitu by šlo zpracovat první cifru před vstupem do cyklu.

Pro desetinná čísla musíš zpracovat des. čárku a pak přičítat cifra * mocnina(1/10).

hu

Zpracování první cifry před vstupem do cyklu:

char* text;  //ukazatel na retezec k převodu
int signum = 1;
int cislo;
int i = 0;

if(text[0] == '-')
{
   signum = -1;
   i = 1;
}

if( (text[i] >= '0') && (text[i] <= '9') )
{
   cislo = (text[i] - '0') * signum;
   for(i++ ; text[i] != 0; i++)
   {
      if( (text[i] >= '0') && (text[i] <= '9') )
      {
         cislo = cislo * 10 + text[i] - '0';
      }
      else break;
}
else cislo = 0;

Ješte s ukazatelem:

char* text;  //ukazatel na retezec k převodu
int signum = 1;
int cislo;

if(*text == '-')
{
   signum = -1;
   ++text;
}

if( (*text >= '0') && (*text <= '9') )
{
   cislo = (*text - '0') * signum;
   for(++text; *text != 0; ++text)
   {
      if( (*text >= '0') && (*text <= '9') )
      {
         cislo = cislo* 10 + *text - '0';
      }
      else break;
   }
}
else cislo = 0;

Truchu bojuji s editací příspěvku :(

hu

#7 hlucheucho
Jak může někdo vymyslet tohle po tom co napsal Staon ?

#8 q
jestli sis nevšiml, pracuji se znaménkem. Podud bych okopíroval jeho řešení za detekci znaménka, musel bych ho do výsledku dávat až nakonec. Těžko říci, která cesta by byla efektivnější. Kromě toho kontroluji každý znak, zda je cifra. Pokud řetězec nezačíná znaménkem - nebo cifrou, výsledek je 0, stejně tak pokud za znaménkem není cifra. Konverze se ukončí v okamžiku, kdy je zpracován celý řetězec nebo se narazí na neciferný znak.

hu

Na desetinné číslo by se dalo jít takto: 

char* text;  //ukazatel na retezec k převodu
int signum = 1;
double cislo = 0;
char dec_sep = '.';
double _tiny = 0.1;

if(*text == '-')
{
   signum = -1;
   ++text;
}

for( ; *text != 0; ++text)
{
   if( (*text >= '0') && (*text <= '9') )
   {  
      cislo = cislo* 10 + *text - '0';
   }
   else if(*text == dec_sep)
     {
        for( ++text; *text != 0; ++text)
        {
           if( (*text >= '0') && (*text <= '9') )
           {
              cislo += (*text - '0') * _tiny;
              _tiny = _tiny / 10;
           }
           else break;
        }
        break;
     }
     else break;
}
cislo = cislo * signum;

Jen ukázka, "učesat" jsem to nezkoušel. Na semilogaritmický tvar by to asi musel být stavový automat.

hu

Dokončíme genezi - semilogaritmický tvar:

char* text;  //ukazatel na retezec k převodu
int signum = 1;
double cislo = 0;
char dec_sep = '.';
double _tiny = 0.1;
int exponent = 0;
int e_sg = 1

//znamenkova cast
if(*text == '-')
{
   signum = -1;
   ++text;
}
else if(*text == '+')
   {
      ++text;
   }

//celociselna cast
for( ; (*text != 0) && (*text >= '0') && (*text <= '9'); ++text)
{
   cislo = cislo * 10 + *text - '0';
}

//desetinna cast
if( (*text != 0) && (*text == dec_sep) )
{
   for( ++text; (*text != 0) && (*text >= '0') && (*text <= '9'); ++text)
   {
      cislo += (*text - '0') * _tiny;
      _tiny = _tiny / 10;
   }
}

//exponencialni cast
if( (*text != 0) && ((*text == 'e') || (*text == 'E')) )
{
   ++text;
   //znamenkova cast exponentu
   if(*text == '-')
   {
      e_sg = -1;
      ++text;
   }
   else if(*text == '+')
      {
         ++text;
      }

   for( ; (*text != 0) && (*text >= '0') && (*text <= '9'); ++text)
   {
      exponent = exponent * 10 + *text - '0';
   }
   exponent = exponent * e_sg;
   cislo = cislo * pow(10, exponent);
}

//zapracuje znamenko do vysledku
cislo = cislo * signum;

hu

#5 MiCizek
Váš pocit není úplně správný. Když například kouknete do glibc na funkci strtol, tak zjistíte, že je dělaná v principu stejně, jako to, co jsem napsal tady já. Akorát ten kód vypadá strašně a něco z něho vyčíst je umění, protože řeší znaménka, různé základy, wide chars, oddělovače tisíců a má tam strašnou spoustu podmíněných překladů. Ale je to čisté C, o žádný assembler se tam nepokoušeli.

#7 hlucheucho
Ty algoritmy bohužel nejsou dobře. Pokud si znaménko k číslu přinásobíte před cyklem, tak se vám číslice pro záporná čísla budou odečítat, ne přičítat: 

-123: (-1 * 10 + 2) * 10 + 3 = -77

Znaménko musíte aplikovat vždy až na konec, přesně tak, jak to děláte u čísel s destinnými místy. Anebo byste ho musel přinásobit ke každé číslici.

#13 Staon
Měl jsem kód přezkoušet a odladit, přišel bych na to sám. Znaménko se musí zapracovat buď do každé cifry (neefektivní řešení) nebo až v závěru do výsledku.

hu