Как разобрать строку в целое число без библиотечных функций? - PullRequest
Новая
       15

Как разобрать строку в целое число без библиотечных функций?

6 голосов
/ 15 мая 2009

Мне недавно задали этот вопрос в интервью:

"Как можно разобрать строку формы '12345' в ее целочисленное представление 12345 без использования каких-либо библиотечных функций и независимо от языка?"

Я подумал о двух ответах, но интервьюер сказал, что был третий. Вот мои два решения:

Решение 1. Сохраните словарь, который отображает '1' => 1, '2' => 2 и т. Д. Затем анализируйте строку по одному символу за раз, ищите символ в своем словаре и умножайте на значение места , Подведите итоги.

Решение 2. Разберите строку по одному символу за раз и вычтите «0» из каждого символа. Это даст вам «1» - «0» = 0x1, «2» - «0» = 0x2 и т. Д. Опять же, умножьте на значение места и суммируйте результаты.

Кто-нибудь может подумать, каким может быть третье решение?

Спасибо.

Ответы [ 8 ]

8 голосов
/ 15 мая 2009

Я ожидаю, что после интервьюера было: 

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

Этот метод использует гораздо меньше операций, чем метод, который вы описали.

3 голосов
/ 15 мая 2009

Разобрать строку в обратном порядке, использовать один из двух методов анализа отдельных цифр, умножить аккумулятор на 10, а затем добавить цифру в аккумулятор.

Таким образом, вам не нужно рассчитывать стоимость места. Умножая аккумулятор на десять каждый раз, вы получаете один и тот же результат.

2 голосов
/ 06 ноября 2012

// Java-версия 

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;



}

// модульный тест 

@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");

}

2 голосов
/ 23 июня 2009

Ответ Артелиуса чрезвычайно лаконичен и не зависит от языка, но для тех, кто ищет более подробный ответ с объяснением, а также реализацию на C и Java, можете проверить эту страницу:

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

Прокрутите вниз (или выполните поиск) до «Практический вопрос: преобразовать строку в кодировке ASCII в целое число».

0 голосов
/ 01 сентября 2017

Это полная программа со всеми положительными и отрицательными условиями без использования библиотеки 

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;
 }
}
0 голосов
/ 02 июня 2010 
#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;
}
0 голосов
/ 15 мая 2009

Вы всегда можете попробовать бинарный поиск по огромной таблице поиска строковых представлений!

Никто ничего не говорил об эффективности ...: -)

0 голосов
/ 15 мая 2009

Держите словарь, который отображает все строки в их целочисленные аналоги, до какого-то предела? Возможно, не имеет особого смысла, за исключением того, что это, вероятно, быстрее , если верхний предел мал, например две или три цифры.

...