Cómo analizar una cadena en un entero sin funciones de biblioteca?

Question

Hace poco me preguntaron esta pregunta en una entrevista:

"¿Cómo podría analizar una cadena de la forma '12345' en su representación entera 12345 sin usar ninguna función de biblioteca, e independientemente del idioma?"

Pensé en dos respuestas, pero el entrevistador dijo que había una tercera. Aquí están mis dos soluciones:

Solución 1: Guarde un diccionario que mapea '1' => 1, '2' => 2, etc. Luego analice la cadena un carácter a la vez, busque el carácter en su diccionario, y multiplicar por el valor de lugar. Suma los resultados.

Solución 2: Analice la cadena un carácter a la vez y restar '0' de cada carácter. Esto le dará '1' - '0' = 0x1, '2' - '0' = 0x2, etc. Nuevamente, multiplique por el valor de posición y sume los resultados.

¿Alguien puede pensar en qué podría ser una tercera solución?

Gracias.

Answer 1

espero que esto es lo que el entrevistador fue después:

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

Este método utiliza mucho menos operaciones que el método ha rememorado.

Answer 2

¿Tiene un diccionario que mapea todas las cadenas con sus homólogos enteros, hasta cierto límite? Quizás no tenga mucho sentido, excepto que probablemente sea más rápido si el límite superior es pequeño, p. dos o tres dígitos

Answer 3

¡Siempre se puede intentar una búsqueda binaria a través de una tabla de búsqueda masiva de representaciones de cadenas!

Nadie ha dicho nada de la eficiencia ... :-)

Answer 4

analizar la cadena con el fin opuesto, utilice uno de los dos métodos para analizar un solo dígito, hay que multiplicar por el acumulador 10 a continuación, agregar el dígito de el acumulador.

De esta forma no tiene que calcular el valor posicional. Al multiplicar el acumulador por diez cada vez que obtienes el mismo resultado.

Answer 5

respuesta de Artelius es extremadamente concisa independiente y lengua, pero para aquellos que buscan una respuesta más detallada con la explicación, así como una C y la aplicación Java puede echa un vistazo a esta página:

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

de desplazamiento hacia abajo (o búsqueda) a "Pregunta de práctica: convierte una cadena codificada en ASCII en un número entero."

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 versión

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; 



} 

// unidad de prueba

@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

Este es el programa completo con todas las condiciones positivas y negativas sin el uso de la biblioteca

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; 
} 
}