首页 > 笔试面试题 > IP地址字符串转无符号整型uint—自动机思想【小米、腾讯面试题】

IP地址字符串转无符号整型uint—自动机思想【小米、腾讯面试题】

2013年5月6日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

题:写一个把字符串的IP地址变成32位整数的函数,要求考察程序健壮性。

这个很能考察眼高手低的问题;如果考虑程序健壮性,有很多的非法情况需要考虑,稍有不慎就会有欠考虑的情况;如不考虑非法情况,转换的过程无非就是分解整数,合并这两步;只需两句代码就可以搞定,如下:


sscanf(ipstr, "%d.%d.%d.%d", &a, &b, &c, &d);

return (a<<24)|(b<<16)|(c<<8)|d;

但是考虑程序健壮性就没这么简单了,不过核心思想也就是上面的两句话,下面将各种错误情况定义成状态表,程序如下:

#include <iostream>
#include <string>
using namespace std;

#define IPLEN 16  // 设输入ip地址长度不超过16

enum ERR_STATE
{
	SUCCESS = 0,
	NULL_POINTER,
	OVER_BOUNDARY,
	INVALID_CHAR,
	INVALID_FORM
};
char * ERR_Strings[5] = {
	"Success!",              // SUCCESS
	"Null pointer!",         // NULL_POINTER
	"Over boundary digits!", // OVER_BOUNDARY
	"Invalid char!",         // INVALID_CHAR
	"Invalid form!"          // INVALID_FORM
};

/* ip to unint
 * 一般返回一个int作为errorCode,真正的返回值放在参数里
 * para: ip,ip字符串; result,计算结果
 * return: ERROR & SUCCESS
 */
int ipToUnint(char * ip, unsigned int & result)
{
	if(NULL == ip)
	{
		return NULL_POINTER;
	}

	unsigned int digit = 0;  // 记录ip地址4个整数
	int dotNum = 0;    // num of dot
	int digitNum = 0;  // num of digit
	char input = 0;

	for(int ipIdx = 0; ; ++ipIdx)
	{
		input = ip[ipIdx];
		if(input >= '0' && input <= '9')   // 数字
		{
			++ digitNum;
			digit = 10 * digit + (input - '0');
			if(digit > 255 || digit < 0)   // 数字非法或长度过长
			{
				return OVER_BOUNDARY;
			}
		}else if(input == '.')       // 遇点,合并部分结果
		{
			++ dotNum;
			if(dotNum > digitNum)   // 诸如 ..0.1 or 4..0.1
			{
				return INVALID_FORM;
			}else // 合并
			{
				result = (result<<8) | digit;
				digit = 0;
			}
		}else if(input == '\0')    // 结束符,检查点数,返回结果
		{
			if(dotNum != 3)
			{
				return INVALID_FORM;
			}else
			{
				result = (result<<8) + digit;
				return SUCCESS;
			}
		}else  // 非法输入
		{
			return INVALID_CHAR;
		}
	}
}

void main()
{
	char ipStr[IPLEN] = {0};

	string input = "";
	cin>>input;
	sscanf(input.c_str(), "%15s", ipStr);

	unsigned int result = 0;
	int state = ipToUnint(ipStr, result);
	if(state == SUCCESS)
	{
		printf("result: %d\n", result);
	}else
	{
		printf("%s\n",ERR_Strings[state]);
	}
}

另外,程序可以换一种写法,考虑到转换的过程是处理数字和点,可以使用自动机的思想;自动机的思想就是整一个状态-转移表,根据输入自动判断,说白了就是正则表达式,在同一个状态下,不同的输入会转到不同的状态上去;也即:

while(true)
{
	i=nextInput();
	if(state==1)
	{
		switch(i)
		{
			input1:dosth. & change state;
			input2:dosth. & change state;
			...
		}
	}
	if (state==2)
	{
		...
	}
	...
}

对于ip,就只有两个状态,要么是正在输入数字,要么是正在输入点,至于点和数字的个数以及数字大小等情况可以另外优化。如果当前状态是正在输入数字,那么接下来的输入应该是数字,如果是数字则转入正在输入点的状态,否则返回错误。如果当前的状态是正在输入点,则接下来的输入应该是点,如果是点则转入正在输入数字状态;如果是数字,则说明数字还未接受结束,继续接受,然后维持该状态;如果是结束符则结算,否则返回错误。

伪代码如下:

for (input) {
	if(state=READING_DOT) {
		switch(input) {
		case digit: number=number*10+input; if(number>255) return err;
		case dot: if(dot_count==3) return err; sum=sum<<8+number; dot_count++; number=0;state=READING_NUM;
		case end: if(dot_count!=3) return err; sum=sum<<8+number; return sum;
		default: return err;
	  }
	} else {
		switch(input) {
		case digit: state=READING_DOT; number=digit;
		default: return err;
		}
	}
}

代码如下:

#include <iostream>
#include <string>
using namespace std;

#define IPLEN 16  // 设输入ip地址长度不超过16

enum STATECODE    // 状态
{
	ERROR = -1,
	SUCCESS,
	READING_DOT,
	READING_NUM
};

/* ip to unint
 * 一般返回一个int作为errorCode,真正的返回值放在参数里
 * para: ip,ip字符串; result,计算结果
 * return: ERROR & SUCCESS
 */
int ipToUnint(char * ip, unsigned int & result)
{
	if(NULL == ip)
	{
		return ERROR;
	}

	unsigned int digit = 0; // ip地址的每个整数
	int dotNum = 0;         // num of dot
	int digitNum = 0;       // num of digit
	char input = 0;         // 当前输入字符
	int state = READING_NUM; // state

	for(int i = 0; ; ++i)
	{
		input = ip[i];
		if(state == READING_NUM) // 状态 reading num
		{
			if(input >= '0' && input <= '9')
			{
				state = READING_DOT;
				digit = input - '0';
			}else
			{
				return ERROR;
			}
		}else   // 状态 reading dot
		{
			if(input >= '0' && input <= '9')
			{
				digit = digit * 10 + (input-'0');
				if(digit > 255 || digit < 0)
				{
					return ERROR;
				}
			}else if(input == '.')
			{
				if(dotNum == 3)
				{
					return ERROR;
				}
				++dotNum;
				result = (result<<8) + digit;
				digit = 0;
				state = READING_NUM;
			}else if(input == '\0')
			{
				if(dotNum != 3)
				{
					return ERROR;
				}
				result = (result<<8) + digit;
				return SUCCESS;
			}else
			{
				return ERROR;
			}
		}
	}
}

void main()
{
	char ipStr[IPLEN] = {0};

	string input = "";
	cin>>input;
	sscanf(input.c_str(), "%15s", ipStr);

	unsigned int result = 0;
	if(ipToUnint(ipStr, result) != ERROR)
	{
		printf("result: %d\n", result);
	}else
	{
		printf("ERROR!\n");
	}
}

(全文完)

  • 徐 子陵

    你好,第一种实现代码不能处理192.168..和192..0.1这种情况,我试着把处理dot那部分改了下,vs2008编译通过,运行无误,博主有空看看!#_#

    #include &lt;iostream&gt;
    
    #include &lt;string&gt;
    
    using namespace std;
    
    #define IPLEN 16  // 设输入ip地址长度不超过16
    
    enum ERR_STATE
    
    {
    
        SUCCESS = 0,
    
        NULL_POINTER,
    
        OVER_BOUNDARY,
    
        INVALID_CHAR,
    
        INVALID_FORM
    
    };
    
    char * ERR_Strings[5] = {
    
        &quot;Success!&quot;,              // SUCCESS
    
        &quot;Null pointer!&quot;,         // NULL_POINTER
    
        &quot;Over boundary digits!&quot;, // OVER_BOUNDARY
    
        &quot;Invalid char!&quot;,         // INVALID_CHAR
    
        &quot;Invalid form!&quot;          // INVALID_FORM
    
    };
    
    /* ip to unint
    
     * 一般返回一个int作为errorCode,真正的返回值放在参数里
    
     * para: ip,ip字符串; result,计算结果
    
     * return: ERROR &amp; SUCCESS
    
     */
    
    int ipToUnint(char * ip, unsigned int &amp; result)
    
    {
    
        if(NULL == ip)
    
        {
    
            return NULL_POINTER;
    
        }
    
        unsigned int digit = 0;  // 记录ip地址4个整数
    
        int dotNum = 0;    // num of dot
    
    	int valueNum = 0;
    
        char input = 0;
    
        for(int ipIdx = 0; ; ++ipIdx)
    
        {
    
            input = ip[ipIdx];
    
            if(input &gt;= '0' &amp;&amp; input &lt;= '9')   // 数字
    
            {
    
                digit = 10 * digit + (input - '0');
    
                if(digit &gt; 255 || digit &lt; 0)   // 数字非法或长度过长
    
                {
    
                    return OVER_BOUNDARY;
    
                }
    
            }else if(input == '.')       // 遇点,合并部分结果
    
            {
    
                ++ dotNum;
    
    			if(digit/100 || digit /10 || digit)
    
    				++valueNum;
    
    			if( dotNum &gt; valueNum){
    
    				return INVALID_FORM;
    
    			}else // 合并
    
                {
    
                    result = (result&lt;&lt;8) | digit;
    
                    digit = 0;
    
                }
    
            }else if(input == '')    // 结束符,检查点数,返回结果
    
            {
    
                if(dotNum != 3)
    
                {
    
                    return INVALID_FORM;
    
                }else
    
                {
    
                    result = (result&lt;&lt;8) + digit;
    
                    return SUCCESS;
    
                }
    
            }else  // 非法输入
    
            {
    
                return INVALID_CHAR;
    
            }
    
        }
    
    }
    
    void main()
    
    {
    
        char ipStr[IPLEN] = {0};
    
        string input = &quot;&quot;;
    
        cin&gt;&gt;input;
    
        sscanf(input.c_str(), &quot;%15s&quot;, ipStr);
    
        unsigned int result = 0;
    
        int state = ipToUnint(ipStr, result);
    
        if(state == SUCCESS)
    
        {
    
            printf(&quot;result: 0x%xn&quot;, result);
    
        }else
    
        {
    
            printf(&quot;%sn&quot;,ERR_Strings[state]);
    
        }
    
    	getchar();
    
    }
    
  • lw

    192..168.0 你的结果是成功,但是实际是非法的。

    问题的原因在于54行:if(dotNum > digitNum) 是有问题的, 192..168 到第二个点的时候没报错

  • 大菜峰

    程序只能处理个位数的ip比如3.2.2.7 要是输入ip是 123..12. 得不到正确结果

    • Yx.Ac

      非个位数的IP已测过,是没问题的,,你可以给个反例吗?