O******i
发帖数: 269 | 1 写了一个，要考虑的情况真多...
假定是16位整数，范围是-32768到+32767
bool my_atoi(const char* str, int16& num)
{
if (str == NULL || str[0] == '\0')
return false;
int i = 0;
bool IsNeg = (str[0] == '-')? true : false;
if (str[0] == '+' || str[0] == '-')
{
if (str[1] == '\0')
return false;
i = 1;
}
num = 0;
const int num_limit = 3276;
const int digit_limit = (IsNeg)? 8 : 7;
int digit = 0;
bool max_int_reached = false;
for (; str[i] != '\0'; i++)
{
if (str[i] >= '0' && str[i] <= '9')
{
digit = str[i] - '0';
if (max_int_reached || num > num_limit)
return false;
else if (num == num_limit && digit > digit_limit)
return false;
else if (num == num_limit && digit == digit_limit)
max_int_reached = true;
else
num = num * 10 + digit;
}
else
return false;
}
if (max_int_reached)
num = (IsNeg)? -32768 : 32767;
else
num *= (IsNeg)? -1 : 1;
return true;
} |
S*******0
发帖数: 198 | 2 这个版上讨论过多次了，这是我的code
//atoi
public static int atoi(String str) throws Exception{
String expression = str.trim();
if(expression==null||expression.equals("")){
throw new Exception("expression is empty");
}
int sign = 1;
int index = 0;
if(expression.charAt(0) == '-'){
sign = -1;
}
if(expression.charAt(0) == '-' || expression.charAt(0) == '+'){
index++;
if(expression.length()==1){
throw new Exception("expression is invalid");
}
}
int ret = 0;
while(index
char c = expression.charAt(index);
if(c < '0' || c > '9') throw new Exception("expression is
invalid");
int value = c - '0';
if(sign > 0){
if(ret > Integer.MAX_VALUE / 10) throw new Exception("
Integer overflow");
}else{
if(ret < Integer.MIN_VALUE / 10) throw new Exception("
Integer overflow");
}
ret = ret*10;
if(sign > 0){
if(ret > Integer.MAX_VALUE - value) throw new Exception("
Integer overflow");
}else{
if(ret < Integer.MIN_VALUE + value ) throw new Exception("
Integer overflow");
}
ret += value * sign;
index++;
}
return ret;
} |
P**l
发帖数: 3722 | 3 弱弱地问，我要是输入"thirty-five"，能输出啥 |
n*******w
发帖数: 687 | 4 这个题面试中经常问。最好一次性写到bug free。
个人感觉，一开始先别考虑那么多exception。容易忘。
另外还有一个处理exception的方法。可以尽量parse input string并返回一个整数值
。感觉更好。比如输入 “-123abc”，不要抛出异常，返回-123.
【在 O******i 的大作中提到】
: 写了一个，要考虑的情况真多...
: 假定是16位整数，范围是-32768到+32767
: bool my_atoi(const char* str, int16& num)
: {
: if (str == NULL || str[0] == '\0')
: return false;
: int i = 0;
: bool IsNeg = (str[0] == '-')? true : false;
: if (str[0] == '+' || str[0] == '-')
: {
|
A**u
发帖数: 2458 | 5 象c的atoi一样
不用处理溢出
只有在INT_MIN, INT_MAX范围内的，才是正确值
【在 S*******0 的大作中提到】
: 这个版上讨论过多次了，这是我的code
: //atoi
: public static int atoi(String str) throws Exception{
: String expression = str.trim();
: if(expression==null||expression.equals("")){
: throw new Exception("expression is empty");
: }
: int sign = 1;
: int index = 0;
: if(expression.charAt(0) == '-'){
|
d****n
发帖数: 1637 | 6 short int atoi(char s[])
{
short int i, n;
n = 0;
if (s[0]=='-' || s[0]=='+') i=1;else i=0;
for (; s[i] >= '0' && s[i] <= '9'; ++i)
n = 10 * n + (s[i] - '0');
return (s[0]=='-'?n*-1:n)
} |
t********0
发帖数: 118 | |
g*********8
发帖数: 64 | 8 int str2int(string s){
assert(s.length()>0);
bool isNeg=false;
unsigned int num=0,i=0,d=0;
if(s[0]=='-'){
isNeg=true;
i=1;
}
while(i
d=s[i]-'0';
num=num*10+d;
assert(d>=0&&d<=9);
assert(num<=INT_MAX);
i++;
}
if(isNeg) num=-1*num;
return num;
}
我写的代码，望指正，处理了溢出，负数，非数值，还有什么异常没有处理？ |
g*********8
发帖数: 64 | 9 测试用例： -123
1222121212212121
-1222121212212121
-dfd
"" |
r****t
发帖数: 10904 | 10 溢出以后结果值也在 INT_MIN, INT_MAX范围内，如果不查检查如何知道会溢出？
不过原版的也不查，咱们山寨也不用了。
【在 A**u 的大作中提到】
: 象c的atoi一样
: 不用处理溢出
: 只有在INT_MIN, INT_MAX范围内的，才是正确值
|
|
|
r****t
发帖数: 10904 | 11 this is required from the man page.
【在 n*******w 的大作中提到】
: 这个题面试中经常问。最好一次性写到bug free。
: 个人感觉，一开始先别考虑那么多exception。容易忘。
: 另外还有一个处理exception的方法。可以尽量parse input string并返回一个整数值
: 。感觉更好。比如输入 “-123abc”，不要抛出异常，返回-123.
|
r****t
发帖数: 10904 | 12 expression.equals("") is not sufficient.
man pages says strtol needs to call isspace to remove the leading spaces. atoi.c at least processed \t and spaces.
【在 S*******0 的大作中提到】
: 这个版上讨论过多次了，这是我的code
: //atoi
: public static int atoi(String str) throws Exception{
: String expression = str.trim();
: if(expression==null||expression.equals("")){
: throw new Exception("expression is empty");
: }
: int sign = 1;
: int index = 0;
: if(expression.charAt(0) == '-'){
|
j*******g
发帖数: 4 | 13 见过很多次这个题目了，一直没有招，下面写了一个又臭又长的， 方法很笨， 求建议
， 欢迎批评和指正
这样的代码面试可以通过吗？
////////////////////////////////////////////////////////////////
#include
#include
using namespace std;
//假设16位的整型
// -32768 , +32767
const char MAX_INT[] = "32767";
const char MIN_INT[] = "32768";
const int MAX_STRLEN = 5;
bool my_atoi(const char *str, int &res)
{
if(str == NULL)
{
cout << "Invalid pointer" << endl;
return false;
}
int index = 0;
if(str[index] == '-' || str[index] == '+')
{
index++;
}
if(str[index] == '\0')
{
cout << "Empty string" << endl;
return false;
}
if(strlen(str + index) > MAX_STRLEN)
{
if(str[0] == '-')
{
cout << "Underflow1" << endl;
}
else
{
cout << "Overflow1" << endl;
}
return false;
}
if(strlen(str + index) == MAX_STRLEN)
{
if(str[0] == '-' && strcmp(str + index, MIN_INT) > 0)
{
cout << "Underflow2" << endl;
return false;
}
else if(str[0] != '-' && strcmp(str + index, MAX_INT) > 0)
{
cout << "Overflow2" << endl;
return false;
}
}
/////////////////////////////////////////////////////////////////
res = 0;
bool is_neg = (str[0] == '-') ? true : false;
while(str[index] != '\0')
{
res = res * 10 + str[index++] - '0';
}
if(is_neg)
res = -res;
return true;
}
int main(int argc, char **argv)
{
while(true)
{
char *str = new char[120];
cin >> str;
int res;
if(my_atoi(str, res))
{
cout << "int(" << str << ") = " << res << endl;
}
delete []str;
}
return 0;
} |
l******d
发帖数: 530 | |
g*********e
发帖数: 14401 | 15 请问 INT_MAX INT_MIN是要自己define吗？c貌似不自带这个吧。 |
g*********e
发帖数: 14401 | 16 请问 INT_MAX INT_MIN是要自己define吗？c貌似不自带这个吧。 |
b******t
发帖数: 965 | 17 limits.h
【在 g*********e 的大作中提到】
: 请问 INT_MAX INT_MIN是要自己define吗？c貌似不自带这个吧。
|
w**z
发帖数: 8232 | 18 我再贴一下Java的sourcecode。不懂为什么要把正数转成负数再查溢出呢？有什么好处？
code里有Author的comments
// Accumulating negatively avoids surprises near MAX_VALUE
/**
* Parses the string argument as a signed integer in the radix
* specified by the second argument. The characters in the string
* must all be digits of the specified radix (as determined by
* whether {@link java.lang.Character#digit(char, int)} returns a
* nonnegative value), except that the first character may be an
* ASCII minus sign '-' ('\u002D') to
* indicate a negative value. The resulting integer value is returned.
*
* An exception of type NumberFormatException is
* thrown if any of the following situations occurs:
*
* - The first argument is
null or is a string of
* length zero.
* - The radix is either smaller than
* {@link java.lang.Character#MIN_RADIX} or
* larger than {@link java.lang.Character#MAX_RADIX}.
* - Any character of the string is not a digit of the specified
* radix, except that the first character may be a minus sign
* '-' ('\u002D') provided that the
* string is longer than length 1.
* - The value represented by the string is not a value of type
* int.
*
* Examples:
*
* parseInt("0", 10) returns 0
* parseInt("473", 10) returns 473
* parseInt("-0", 10) returns 0
* parseInt("-FF", 16) returns -255
* parseInt("1100110", 2) returns 102
* parseInt("2147483647", 10) returns 2147483647
* parseInt("-2147483648", 10) returns -2147483648
* parseInt("2147483648", 10) throws a NumberFormatException
* parseInt("99", 8) throws a NumberFormatException
* parseInt("Kona", 10) throws a NumberFormatException
* parseInt("Kona", 27) returns 411787
*
*
* @param s the String containing the integer
* representation to be parsed
* @param radix the radix to be used while parsing s.
* @return the integer represented by the string argument in the
* specified radix.
* @exception NumberFormatException if the String
* does not contain a parsable int.
*/
public static int parseInt(String s, int radix)
throws NumberFormatException
{
if (s == null) {
throw new NumberFormatException("null");
}
if (radix < Character.MIN_RADIX) {
throw new NumberFormatException("radix " + radix +
" less than Character.MIN_RADIX");
}
if (radix > Character.MAX_RADIX) {
throw new NumberFormatException("radix " + radix +
" greater than Character.MAX_RADIX");
}
int result = 0;
boolean negative = false;
int i = 0, max = s.length();
int limit;
int multmin;
int digit;
if (max > 0) {
if (s.charAt(0) == '-') {
negative = true;
limit = Integer.MIN_VALUE;
i++;
} else {
limit = -Integer.MAX_VALUE;
}
multmin = limit / radix;
if (i < max) {
digit = Character.digit(s.charAt(i++),radix);
if (digit < 0) {
throw NumberFormatException.forInputString(s);
} else {
result = -digit;
}
}
while (i < max) {
// Accumulating negatively avoids surprises near MAX_VALUE
digit = Character.digit(s.charAt(i++),radix);
if (digit < 0) {
throw NumberFormatException.forInputString(s);
}
if (result < multmin) {
throw NumberFormatException.forInputString(s);
}
result *= radix;
if (result < limit + digit) {
throw NumberFormatException.forInputString(s);
}
result -= digit;
}
} else {
throw NumberFormatException.forInputString(s);
}
if (negative) {
if (i > 1) {
return result;
} else { /* Only got "-" */
throw NumberFormatException.forInputString(s);
}
} else {
return -result;
}
} |
n**e
发帖数: 116 | 19 看到版上太多关于atoi的讨论，我贴一个我的实现，希望对有所帮助。如发现bugs，请
指正。
//--------------------------------------------------------------------
// Convert a string to an integer
// How to handle overflow issue:
// Compute the cutoff value between legal numbers and illegal
// numbers. That is the largest legal value, divided by the
// base. An input number that is greater than this value, if
// followed by a legal input character, is too big. One that
// is equal to this value may be valid or not; the limit
// between valid and invalid numbers is then based on the last
// digit. For instance, if the range for longs is
// [-2147483648..2147483647] and the input base is 10,
// cutoff will be set to 214748364 and cutLimit to either
// 7 (sign==1) or 8 (sign==-1), meaning that if we have accumulated
// a value > 214748364, or equal but the next digit is > 7 (or 8),
// the number is too big, and we will return a range error.
//-----------------------------------------------------------------
int atoi(const char* s) {
assert(s != NULL);
int c = 0;
int sign = 1;
//Skip leading white spaces and pick up the sign if any
do {
c = *s++;
} while (isspace(c));
// Check the sign if any
if (c == '-') {
sign = -1;
c = *s++;
} else if (c == '+') {
sign = 1;
c = *s++;
}
unsigned int result = 0;
int cutoff = (sign == -1) ? INT_MIN : INT_MAX;
int cutLimit = (sign == -1) ? -(cutoff % 10) : cutoff % 10;
cutoff /= 10;
if (sign == -1) cutoff = -cutoff;
bool overflow = false;
while (c) {
if (isdigit(c)) c -= '0';
else break;
// Check overflow
//printf("c = %d\n", c);
if (result == cutoff && c > cutLimit || result > cutoff) {
overflow = true;
break;
} else { // Accumulate the value
result *= 10;
result += c;
}
c = *s++; // next character
} // End of while loop
if (overflow) {
result = (int) (sign == -1) ? INT_MIN : INT_MAX;
errno = ERANGE;
} else {
result = (int) result * sign;
}
return (int) result;
} |
i**********e
发帖数: 1145 | 20 恭喜，跑了你的程序，结果如下：
Run Status: Accepted!
Program Runtime: 24 milli secs
Progress: 1039/1039 test cases passed.
【在 n**e 的大作中提到】
: 看到版上太多关于atoi的讨论，我贴一个我的实现，希望对有所帮助。如发现bugs，请
: 指正。
: //--------------------------------------------------------------------
: // Convert a string to an integer
: // How to handle overflow issue:
: // Compute the cutoff value between legal numbers and illegal
: // numbers. That is the largest legal value, divided by the
: // base. An input number that is greater than this value, if
: // followed by a legal input character, is too big. One that
: // is equal to this value may be valid or not; the limit
|
|
|
n**e
发帖数: 116 | 21 还不错哈，谢谢！看到很多人讨论溢出的处理，真的希望有些帮助。 |
l******d
发帖数: 530 | 22 你是用什么工具跑这些test case的？谢谢。
【在 i**********e 的大作中提到】
: 恭喜，跑了你的程序，结果如下：
: Run Status: Accepted!
: Program Runtime: 24 milli secs
: Progress: 1039/1039 test cases passed.
|
w**z
发帖数: 8232 | 23 I got the trick. It's very smart to convert positive number to negative
number and check the over flow.
If (result - digit) < Min-Value) equivalent to
if( result < min-value + digit)
But min-value will never be smaller than min-value. so it's easier to check
the negative number. just one line does the trick.
处？
【在 w**z 的大作中提到】
: 我再贴一下Java的sourcecode。不懂为什么要把正数转成负数再查溢出呢？有什么好处？
: code里有Author的comments
: // Accumulating negatively avoids surprises near MAX_VALUE
: /**
: * Parses the string argument as a signed integer in the radix
: * specified by the second argument. The characters in the string
: * must all be digits of the specified radix (as determined by
: * whether {@link java.lang.Character#digit(char, int)} returns a
: * nonnegative value), except that the first character may be an
: * ASCII minus sign '-' ('\u002D') to
|
i**********e
发帖数: 1145 | 24 这里：
leetcode.com/onlinejudge
Problem title: String to integer (atoi)
【在 l******d 的大作中提到】
: 你是用什么工具跑这些test case的？谢谢。
|
