Leetcode atoi (문자열에서 정수로)
저는 Python과 C ++로 된 솔루션을 포함 할 것이며 하나를 검토 할 수 있습니다. 저는 최근에 배우기 시작한 C ++ 코드를 검토하는 데 주로 관심이 있습니다. C ++를 모르는 사람들은 Python 코드를 검토 할 수 있습니다.
문제 설명
atoi문자열을 정수로 변환하는 구현 . 이 함수는 먼저 공백이 아닌 첫 번째 문자를 찾을 때까지 필요한만큼 공백 문자를 버립니다. 그런 다음이 문자에서 시작하여 선택적 초기 플러스 또는 마이너스 기호와 가능한 한 많은 숫자 숫자를 사용하여 숫자 값으로 해석합니다. 문자열은 정수를 구성하는 문자 뒤에 추가 문자를 포함 할 수 있으며, 이는 무시되며이 함수의 동작에 영향을주지 않습니다. str에서 공백이 아닌 문자의 첫 번째 시퀀스가 유효한 정수가 아니거나 str이 비어 있거나 공백 문자 만 포함되어 있기 때문에 그러한 시퀀스가 존재하지 않는 경우 변환이 수행되지 않습니다. 유효한 변환을 수행 할 수없는 경우 0 값이 반환됩니다.
노트 :
공백 문자 만 공백 문자
' '로 간주됩니다. 32 비트 부호있는 정수 범위 ([−2³¹, 2³¹ − 1]) 내에서만 정수를 저장할 수있는 환경을 다루고 있다고 가정합니다. 숫자 값이 표현 가능한 값의 범위를 벗어나면 2³¹ − 1 또는 −2³¹이 반환됩니다.
예 1 :
Input: str = "42"
Output: 42
예 2 :
Input: str = " -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign. Then take as many numerical digits as possible, which gets 42.
예 3 :
Input: str = "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
예 4 :
Input: str = "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical digit or a +/- sign. Therefore no valid conversion could be performed.
예 5 :
Input: str = "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer. Thefore INT_MIN (−231) is returned.
str_int.py
def convert(s):
chars = (c for c in s)
ss = []
while True:
try:
current = next(chars)
if (space := current.isspace()) and ss:
break
if (pm := current in '+-') and ss:
break
if not current.isnumeric() and not pm and not space:
break
if not space:
ss.append(current)
except StopIteration:
break
try:
number = int(''.join(ss).strip())
if number < 0:
return max(-2 ** 31, number)
return min(2 ** 31 - 1, number)
except ValueError:
return 0
if __name__ == '__main__':
print(convert(" 48-"))
str_int.h
#ifndef LEETCODE_STR_TO_INT_H
#define LEETCODE_STR_TO_INT_H
#include <string>
int atoi_impl(const std::string& s, size_t start_idx, size_t end_idx);
int convert_str(const std::string &s);
#endif //LEETCODE_STR_TO_INT_H
str_int.cpp
#include <string>
#include <iostream>
int atoi_impl(const std::string& s, size_t start_idx, size_t end_idx) {
try {
return std::stoi(s.substr(start_idx, end_idx));
}
catch (const std::out_of_range &e) {
return (s[start_idx] == '-') ? INT32_MIN : INT32_MAX;
}
catch (const std::invalid_argument &e) {
return 0;
}
}
int convert_str(const std::string &s) {
size_t start_idx = 0;
size_t end_idx = s.size();
for (size_t i = 0; i < s.size(); ++i) {
bool digit = std::isdigit(s[i]);
bool pm = s[i] == '+' || s[i] == '-';
bool space = std::isspace(s[i]);
if (i == start_idx && !space && !digit && !pm)
return 0;
if ((space || !digit) && i != start_idx) {
end_idx = i;
break;
}
if (space)
start_idx++;
}
if (start_idx != end_idx)
return atoi_impl(s, start_idx, end_idx);
return 0;
}
int main() {
std::cout << "result1: " << convert_str(" -912332") << "\n";
}
답변
코드가 의도 한대로 작동 함을 보여주고 확신을 가지고 리팩토링을 허용하기 위해 두 구현 모두 에 단위 테스트 를 추가하는 것이 좋습니다 . 사양의 모든 요구 사항을 실행하기에 충분한 테스트를 포함 합니다 (범위 외, 유효하지 않은 문자, +/ -/ 없음 등).
C ++ 코드를 좀 더 자세히 살펴 보겠습니다.
우리는이 누락 #include <cctype>에 필요한, std::isspace()와 std::isdigit(),와 #include <stdexcept>.
요구 사항에 따르면 " 공백 문자 ''만 공백 문자로 간주 되므로 std::isspace()줄 바꿈 및 탭을 포함하여 더 넓은 문자 집합과 일치하는 것을 사용해서는 안됩니다 .
알고리즘은 비효율적입니다. 문자열을 두 번 이상 탐색 할 이유가 없습니다. 한 번에 단일 문자를 고려하여 공백이 아닌 첫 번째 문자를 볼 때 변환을 시작하고 숫자 끝에서 끝낼 수 있습니다.
사용 std::stoi()은 아마도 이와 같은 연습의 정신을 벗어난 것일 수 있습니다. 핵심 알고리즘을 코딩하는 능력을 입증해야합니다!
정수 오버플로를 피하기 위해 매우주의해야합니다. 우리는 Undefined Behaviour의 세계에 들어가서 전체 프로그램이 지정되지 않은 상태 이므로 발생한 후에 확인할 수 없습니다 ! 한 가지 가능성은 해당 부호있는 유형보다 더 큰 범위를 가진 부호없는 유형에 결과를 누적하는 것입니다. 그러나 해당하는 양의 값이없는 범위에서 가장 음의 값을 다룰 때는주의하십시오!
대체 구현
위의 문제를 해결하는 방법은 다음과 같습니다. 몇 가지 테스트로 시작하십시오.
#include <iostream>
#include <cstdlib>
#define COMPARE(expected, actual) \
do { \
if (expected != actual) { \
ret = EXIT_FAILURE; \
std::cerr << "Expected " << (expected) \
<< " but got " << (actual) \
<< " from " << #actual << '\n'; \
} \
} while (0)
int main()
{
int ret = EXIT_SUCCESS;
COMPARE(0, convert_str(""));
COMPARE(0, convert_str("0"));
COMPARE(0, convert_str("-0"));
COMPARE(1, convert_str("1"));
COMPARE(1, convert_str(" 1"));
COMPARE(1, convert_str("1e2"));
COMPARE(0, convert_str("\t1"));
COMPARE(-1, convert_str(" -1"));
COMPARE(-1, convert_str(" -001"));
COMPARE(2147483647, convert_str("2147483647"));
COMPARE(2147483647, convert_str("2147483648"));
COMPARE(-2147483648, convert_str("-2147483648"));
COMPARE(-2147483648, convert_str("-2147483649"));
return ret;
}
이제 함수를 구현해 보겠습니다. 이를 위해 문자열 뷰 를 통해 반복기를 사용할 것입니다 .
#include <cctype>
#include <cstdint>
#include <string_view>
#include <type_traits>
int_fast32_t convert_str(std::string_view s)
{
uint_fast32_t value = 0;
bool negative = false;
auto i = s.begin();
auto const end = s.end();
// skip whitespace
while (i != end && *i == ' ') {
++i;
}
if (i == end) {
return 0;
}
// handle optional sign indicator
if (*i == '-') {
negative = true;
++i;
} else if (*i == '+') {
++i;
}
// process the digits
while (i != end && std::isdigit(unsigned(*i))) {
if (value > 214748364
|| value == 214748364 && *i > '7' + negative) {
// would overflow
return negative ? -2147483648 : 2147483647;
}
// usual case
value = value * 10 + (*i - '0');
++i;
}
// convert to result type
int_fast32_t signed_value = value;
return negative ? -signed_value : signed_value;
}
여전히 몇 가지 문제가 있지만 (하드 코딩 된 매직 넘버가 마음에 들지 않습니다) 원본보다 더 안전하고 명확합니다.
운동
이제 인터페이스를 변경하여 모든 종류의 문자 유형을 허용하고 원하는 정수 유형 (적절한 포화 값 포함)을 반환합니다.
template<typename Integer, typename Char, typename Traits>
Integer convert_str(std::basic_string_view<Char,Traits> s);