Převod řetězce na číslo bez použití funkcí, které to udělají – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Kartik
~ Anonymní uživatel
35 příspěvků
16. 9. 2016   #1
-
0
-

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. 

Nahlásit jako SPAM
IP: 90.182.189.–
Reklama
Reklama
hlucheucho+10
Posthunter
16. 9. 2016   #2
-
0
-

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

Nahlásit jako SPAM
IP: 195.178.67.–
Staon0
Newbie
17. 9. 2016   #3
-
0
-

#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').

Nahlásit jako SPAM
IP: 94.112.135.–
Kartik
~ Anonymní uživatel
35 příspěvků
18. 9. 2016   #4
-
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ě. 

Nahlásit jako SPAM
IP: 90.178.131.–
MiCizek0
Stálý člen
19. 9. 2016   #5
-
0
-

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

Nahlásit jako SPAM
IP: 83.208.68.–
hlucheucho+10
Posthunter
19. 9. 2016   #6
-
0
-

   

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

Nahlásit jako SPAM
IP: 195.178.67.–
hlucheucho+10
Posthunter
19. 9. 2016   #7
-
0
-

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

Nahlásit jako SPAM
IP: 195.178.67.–
q
~ Anonymní uživatel
219 příspěvků
19. 9. 2016   #8
-
0
-

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

Nahlásit jako SPAM
IP: 213.211.51.–
hlucheucho+10
Posthunter
19. 9. 2016   #9
-
0
-

#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

Nahlásit jako SPAM
IP: 195.178.67.–
hlucheucho+10
Posthunter
19. 9. 2016   #10
-
0
-

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

Nahlásit jako SPAM
IP: 195.178.67.–
hlucheucho+10
Posthunter
19. 9. 2016   #11
-
0
-

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

Nahlásit jako SPAM
IP: 195.178.67.–
Staon0
Newbie
21. 9. 2016   #12
-
0
-

#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.

Nahlásit jako SPAM
IP: 94.142.234.–
Staon0
Newbie
21. 9. 2016   #13
-
+1
-
Zajímavé

#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.

Nahlásit jako SPAM
IP: 94.142.234.–
hlucheucho+10
Posthunter
21. 9. 2016   #14
-
0
-

#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

Nahlásit jako SPAM
IP: 195.178.67.–
Zjistit počet nových příspěvků

Přidej příspěvek

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 73 hostů

Podobná vlákna

Predani retezce funkci — založil Bananovnik

Nasobeni bez pouziti * — založil sniff

Prevod stringu na cislo — založil jirkab

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý