C++で文字列を整数に変換する方法（atoiの実装）

文字列を整数に変換する関数（atoi）を実装する問題を考えてみましょう。このモジュールは、まず不要な空白文字をすべて読み飛ばし、最初の空白以外の文字に到達するまで処理を進めます。その文字から開始して、任意の符号（プラスまたはマイナス）と、それに続くできるだけ多くの数字を読み取り、それらを数値として解釈します。

文字列内の最初の空白以外の文字の並びが有効な整数ではない場合、あるいは文字列が空であるか空白のみを含むためにそのような並びが存在しない場合は、変換は行われません。

例えば、入力が「-45」であれば、出力は -45 になります。

解決のアプローチ

この問題を解くには、以下の手順に従います。

• 変数を初期化します：sign = 1、base = 0、i = 0、n = 文字列 s の長さ
• i < n かつ s[i] が空白文字である間、i を1ずつ増やします
• 最初の文字が「-」であれば sign = -1 とし、そうでなければ sign = 1 とします
• s[i] が「0」から「9」の範囲にある間、以下を繰り返します
  • 各文字を読み取り、整数に変換します。そして、文字ごとに base を更新していきます（base = base × 10 + 現在の数字）
• オーバーフローのチェックを行い、値が int 型の範囲を超える場合は INT_MAX または INT_MIN を返します
• 最後に base × sign を返します

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int myAtoi(string str) {
        int sign = 1;
        int base = 0;
        int i = 0;
        int n = str.size();
        while(i < n && str[i] == ' '){
            i++;
        }
        if(str[i] == '-' || str[i] == '+') sign = 1 - 2*(str[i++] =='-');
        while(str[i] >= '0' && str[i] <='9'){
            if(base > INT_MAX/10 || base == INT_MAX/10 && str[i]- '0' > INT_MAX %10){
                if(sign == 1)return INT_MAX;
                return INT_MIN;
            }
            base = (base * 10) + (str[i++] - '0');
        }
        return base * sign;
    }
};
main(){
    Solution ob;
    cout << ob.myAtoi("-45")<<endl;
    cout << ob.myAtoi(" 56")<<endl;
    cout << ob.myAtoi("100")<<endl;
}

入力

"-45"
" 56"
"100"

出力

-45
56
100

実装のポイント

この実装における重要なポイントをいくつか紹介します。

• 空白のスキップ： 最初のループで、文字列の先頭にある連続した空白文字を読み飛ばします。
• 符号の判定： 「1 - 2*(str[i++] == '-')」という式は、マイナス記号が見つかった場合に sign を -1 にする賢いテクニックです。同時に i をインクリメントして符号文字をスキップしています。
• オーバーフロー処理： base が INT_MAX/10 を超える場合、または base が INT_MAX/10 と等しく次の数字が 7（INT_MAX % 10）より大きい場合に、int 型の範囲を超える可能性があります。この場合、符号に応じて INT_MAX（2147483647）または INT_MIN（-2147483648）を返すことで、安全にクランプ処理を行っています。

このアルゴリズムの計算量は O(n) で、文字列の長さに比例した時間で処理が完了します。空間計算量は O(1) で、追加のメモリをほとんど必要としません。