Leetcode journey - Question 8 - String to Integer (atoi)

Problem:

Q8. String to Integer (atoi) Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
6. Return the integer as the final result.

Note:

• Only the space character ' ' is considered a whitespace character.
• Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: s = "42"
Output: 42
Explanation:

The underlined characters are what is read in, the caret is the current reader position.
 Step 1: "42" (no characters read because there is no leading whitespace)
          ^
 Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
 Step 3: "42" ("42" is read in)
            ^
 The parsed integer is 42.
 Since 42 is in the range [-231, 231 - 1], the final result is 42.

Constraints:

• 0 <= s.length <= 200
• s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Solution:

Approach:

This is a typical finite state machine problem. We define a state transition table, and use it to determine the state of the automaton as we process each character in the string. The state transition table is shown below.

• The table consists of 4 columns.
• The first column is the current state, the second column is the current character, the third column is the sign of the number, the fourth column is the next state. The next state is determined by the current state and the current character.
• The initial state is "start". The final state is "end". The "end" state is the only state that can be a final state. The other states can only be intermediate states. The "start" state can be an intermediate state or a final state. The "signed" state can be an intermediate state or a final state. The "in_number" state can only be an intermediate state. The "end" state can only be a final state.

every thing is automated

Now let's look at the coding part

Code

#include <iostream>
#include <string>

using namespace std;

class Solution
{
public:
    int myAtoi(string str)
    {
        int i = 0;
        while (i < str.size() && str[i] == ' ')
        {
            i++;
        }
        if (i == str.size())
        {
            return 0;
        }
        bool negative = false;
        if (str[i] == '-')
        {
            negative = true;
            i++;
        }
        else if (str[i] == '+')
        {
            i++;
        }
        long result = 0;
        while (i < str.size() && str[i] >= '0' && str[i] <= '9')
        {
            result = result * 10 + (str[i] - '0');
            if (result > INT_MAX)
            {
                return negative ? INT_MIN : INT_MAX;
            }
            i++;
        }
        return negative ? -result : result;
    }
};

Hope this helps!

• If you have any questions, please leave a comment below. 💭
  

• If you like this article, please share it with your friends. 💖
  

• If you want to read more articles like this, please follow me.
  

Thank you for reading!