Wie analysiert man eine Zeichenkette zu einer Ganzzahl ohne Bibliotheksfunktionen?

Question

Ich wurde vor kurzem in einem Interview gefragt:

"Wie können Sie eine Zeichenfolge der Form '12345' in seine Ganzzahldarstellung 12345 ohne Verwendung von Bibliotheksfunktionen und unabhängig von der Sprache analysieren?"

Ich dachte an zwei Antworten, aber der Interviewer sagte, dass es einen dritten gab. Hier sind meine zwei Lösungen:

Lösung 1: Halten Sie ein Wörterbuch, das '1' => 1, '2' => 2 usw. Parsing die Zeichenfolge ein Zeichen nach dem anderen, suchen Sie das Zeichen in Ihrem Wörterbuch, und multiplizieren mit dem Ort Wert. Summiere die Ergebnisse.

Lösung 2: Analysieren Sie die Zeichenfolge jeweils um ein Zeichen und subtrahieren Sie '0' von jedem Zeichen. Dies wird Ihnen '1' - '0' = 0x1, '2' - '0' = 0x2, usw. geben. Wiederum multiplizieren Sie den Wert nach dem Platz und addieren Sie die Ergebnisse.

Kann jemand darüber nachdenken, was eine dritte Lösung sein könnte?

Danke.

Answer 1

Ich erwarte, dass das ist, was der Interviewer war nach:

number = "12345" 
value = 0 
for digit in number:     //Read most significant digit first 
    value = value * 10 + valueOf(digit) 

Diese Methode weit weniger Operationen als die Methode verwendet, die Sie beschrieben.

Answer 2

Behalten Sie ein Wörterbuch bei, das alle Zeichenfolgen ihren Integergegenstücken zuordnet, bis zu einem gewissen Grad? Es macht nicht viel Sinn, außer dass diese wahrscheinlich schneller ist, wenn die obere Grenze klein ist, z. zwei oder drei Ziffern.

Answer 3

Sie könnten immer eine binäre Suche durch eine massive Nachschlagetabelle von String-Darstellungen versuchen!

Niemand sagte etwas über Effizienz ... :-)

Answer 4

die Zeichenfolge in oposite um Parse, eine der beiden Methoden verwenden, um die einzelnen Ziffern für das Parsen, multiplizieren Sie den Akku von 10 fügen Sie dann die Ziffer der Akku.

Auf diese Weise müssen Sie den Ortswert nicht berechnen. Multiplizieren Sie den Akkumulator jedes Mal mit zehn, wenn Sie das gleiche Ergebnis erhalten.

Answer 5

Artelius Antwort ist äußerst präzise und sprachunabhängig, aber für diejenigen, für eine detailliertere Antwort mit Erläuterungen Umsetzung sowie eine C und Java suchen, können Sie diese Seite an:

http://www.programminginterview.com/content/strings

Scroll down (oder Suche) zu "Praxisfrage: Konvertiere eine ASCII-kodierte Zeichenkette in eine Ganzzahl."

Answer 6

#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 

int nod(long); 
char * myitoa(long int n, char *s); 
void main() 
{ 

    long int n; 
    char *s; 
    printf("Enter n"); 
    scanf("%ld",&n); 
    s=myitoa(n,s); 
    puts(s); 
} 

int nod(long int n) 
{ 
    int m=0; 
    while(n>0) 
    { 
    n=n/10; 
    m++; 
    } 
    return m; 
} 

char * myitoa(long int n, char *s) 
{ 

    int d,i=0; 
    char cd; 
    s=(char*)malloc(nod(n)); 
    while(n>0) 
    { 
    d=n%10; 
    cd=48+d; 
    s[i++]=cd; 
    n=n/10; 
    } 
    s[i]='\0'; 
    strrev(s); 
    return s; 
} 

Answer 7

// java version

public static int convert(String s){ 
    if(s == null || s.length() == 0){ 
     throw new InvalidParameterException(); 
    } 

    int ret = 0; 

    boolean isNegtive = false; 

    for(int i=0;i<s.length();i++){ 
     char c = s.charAt(i); 

     if(i == 0 && (c == '-')){ 
      isNegtive = true; 
      continue; 
     } 

     if(c - '0' < 0 || c - '0' > 10){ 
      throw new InvalidParameterException(); 
     } 

     int tmp = c - '0'; 

     ret *= 10; 
     ret += tmp; 

    } 

    return isNegtive ? (ret - ret * 2) : ret; 



} 

// Unit-Test

@Test 
public void testConvert() { 

    int v = StringToInt.convert("123"); 
    assertEquals(v, 123); 

    v = StringToInt.convert("-123"); 
    assertEquals(v, -123); 

    v = StringToInt.convert("0"); 
    assertEquals(v, 0); 


} 

@Test(expected=InvalidParameterException.class) 
public void testInvalidParameterException() { 
    StringToInt.convert("e123"); 
} 

@Rule 
public ExpectedException exception = ExpectedException.none(); 
@Test 
public void testInvalidParameterException2() { 

    exception.expect(InvalidParameterException.class); 
    StringToInt.convert("-123r"); 

}

Answer 8

Dies ist die komplette Programm mit allen Bedingungen positiv, negativ, ohne Bibliothek

import java.util.Scanner; 


public class StringToInt { 
public static void main(String args[]) { 
    String inputString; 
    Scanner s = new Scanner(System.in); 
    inputString = s.nextLine(); 

    if (!inputString.matches("([+-]?([0-9]*[.])?[0-9]+)")) { 
    System.out.println("error!!!"); 
    } else { 
    Double result2 = getNumber(inputString); 
    System.out.println("result = " + result2); 
    } 

} 
public static Double getNumber(String number) { 
    Double result = 0.0; 
    Double beforeDecimal = 0.0; 
    Double afterDecimal = 0.0; 
    Double afterDecimalCount = 0.0; 
    int signBit = 1; 
    boolean flag = false; 

    int count = number.length(); 
    if (number.charAt(0) == '-') { 
    signBit = -1; 
    flag = true; 
    } else if (number.charAt(0) == '+') { 
    flag = true; 
    } 
    for (int i = 0; i < count; i++) { 
    if (flag && i == 0) { 
    continue; 

    } 
    if (afterDecimalCount == 0.0) { 
    if (number.charAt(i) - '.' == 0) { 
    afterDecimalCount++; 
    } else { 
    beforeDecimal = beforeDecimal * 10 + (number.charAt(i) - '0'); 
    } 

    } else { 
    afterDecimal = afterDecimal * 10 + number.charAt(i) - ('0'); 
    afterDecimalCount = afterDecimalCount * 10; 
    } 
    } 
    if (afterDecimalCount != 0.0) { 
    afterDecimal = afterDecimal/afterDecimalCount; 
    result = beforeDecimal + afterDecimal; 
    } else { 
    result = beforeDecimal; 
    } 

    return result * signBit; 
} 
}