如何在没有库函数的情况下将字符串解析为整数？

I was recently asked this question in an interview:

我最近在接受采访时被问到这个问题:

"How could you parse a string of the form '12345' into its integer representation 12345 without using any library functions, and regardless of language?"

“如何在不使用任何库函数的情况下将”12345“形式的字符串解析为其整数表示12345,而不管语言是什么?

I thought of two answers, but the interviewer said there was a third. Here are my two solutions:

我想到了两个答案,但面试官说有三分之一。这是我的两个解决方案:

Solution 1: Keep a dictionary which maps '1' => 1, '2' => 2, etc. Then parse the string one character at a time, look up the character in your dictionary, and multiply by place value. Sum the results.

解决方案1:保留一个映射'1'=> 1,'2'=> 2等的字典。然后一次解析一个字符,查找字典中的字符,然后乘以位值。总结结果。

Solution 2: Parse the string one character at a time and subtract '0' from each character. This will give you '1' - '0' = 0x1, '2' - '0' = 0x2, etc. Again, multiply by place value and sum the results.

解决方案2:一次解析一个字符串,并从每个字符中减去“0”。这将给你'1' - '0'= 0x1,'2' - '0'= 0x2等。再次,乘以位值并对结果求和。

Can anyone think of what a third solution might be?

任何人都可以想到第三种解决方案可能是什么?

Thanks.

8 个解决方案

#1

I expect this is what the interviewer was after:

我希望这是面试官所追求的:

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

This method uses far less operations than the method you outlined.

此方法使用的操作远少于您概述的方法。

#2

Parse the string in oposite order, use one of the two methods for parsing the single digits, multiply the accumulator by 10 then add the digit to the accumulator.

按相反顺序解析字符串,使用两种方法之一解析单个数字,将累加器乘以10,然后将数字添加到累加器。

This way you don't have to calculate the place value. By multiplying the accumulator by ten every time you get the same result.

这样您就不必计算位置值。每次得到相同的结果时,将累加器乘以10。

#3

Artelius's answer is extremely concise and language independent, but for those looking for a more detailed answer with explanation as well as a C and Java implementation can check out this page:

Artelius的答案非常简洁且与语言无关,但对于那些寻求更详细解释以及C和Java实现的人来说,可以查看此页面:

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

Scroll down (or search) to "Practice Question: Convert an ASCII encoded string into an integer."

向下滚动(或搜索)到“练习题:将ASCII编码的字符串转换为整数”。

#4

// java version

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



}

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

}

#5

Keep a dictionary which maps all strings to their integer counterparts, up to some limit? Doesn't maybe make much sense, except that this probably is faster if the upper limit is small, e.g. two or three digits.

保留一个字典,将所有字符串映射到它们的整数对应字符,达到某个限制?可能没有多大意义,除非如果上限很小,这可能会更快,例如,两三个数字。

#6

You could always try a binary search through a massive look up table of string representations!

您总是可以尝试通过字符串表示的大量查找表进行二进制搜索!

No-one said anything about efficiency... :-)

没人谈到效率...... :-)

#7

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

#8

This is Complete program with all conditions positive, negative without using library

这是完整的程序,所有条件都是正面,负面而不使用库

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

#1