算法 8. 字符串转整数

LeetCode https://leetcode.cn/problems/string-to-integer-atoi/

题目描述

请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个32位有符号整数（类似 C/C++ 中的 atoi 函数)

1. 读入字符串并丢弃无用的前导空格
2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4. 将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
5. 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
6. 返回整数作为最终结果。

思路

可以参考有限状态机
总共包含以下状态
start, signed, number, over
start状态

当前字符是空格, 保持状态不变
当前字符是-/+, 计入signed状态
当前字符是数字, 进入number
当前字符是其他类型, 进入over
signed状态
如果当前字符是空格, 进入over状态
如果当前字符是-/+, 进入over状态
如果当前字符是数字, 保持状态不变
当前字符是其他类型, 进入over
number状态
如果当前字符是空格, 进入over状态
如果当前字符是-/+, 进入over状态
如果当前字符是数字, 保持状态不变
当前字符是其他类型, 进入over

状态转换为一个二维表:

|状  态|空 格|  -+  |number|other|
|start |start|signed|number|over |
|signed|over | over |number|over |
|number|over | over |number|over |

代码

class State {
public:
	State() {
		_signed = 1;
		_state = 0;
		stateMap[0] = { 0, 1, 2, 3 };
		stateMap[1] = { 3, 3, 2, 3 };
		stateMap[2] = { 3, 3, 2, 3 };
	}
	int get_state(const char & c) {
		if (c == ' ')
			return 0;
		if (c == '-' || c == '+')
			return 1;
		if (c >= '0' && c <= '9')
			return 2;
		return 3;
	}
	int transfer(const char & c, long long & result) {
		if (_state == 3)
			return -1;
		int index = get_state(c);
		const std::vector<int> & array = stateMap[_state];
		_state = array[index];
		if (_state == 2) {
			result = result * 10 + c - '0';
			result = _signed == 1 ? min(result, (long long)INT_MAX) : min(result, -(long long)INT_MIN);
		} else if (_state == 1)
			_signed = c == '+' ? 1 : -1;
		else if (_state == 3)
			return -1;
		return 0;
	}

public:
	int _signed;
	int _state;
	std::map<int, std::vector<int>> stateMap;
protected:
private:
};

class Solution {
public:
	int myAtoi(std::string str) {
		State state;
		long long result = 0;
		for (const char & c : str) {
			int r = state.transfer(c, result);
			if (r == -1)
				break;
		}
		result *= state._signed;
		if (result > 2147483647) {
			return 2147483647;
		} else if (result < -2147483648) {
			return -2147483648;
		}
		return (int)result;
	}
	void run() {
		int r = myAtoi(std::string("20000000000000000000"));
		printf("r : %d\n", r);
	}
protected:
private:
};