LeetCode——8.字符串转整数(atoi)【有穷状态自动机DFA】

题解

AC-Code

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;typedef long long ll;class Solution {
    
public:int myAtoi(string str) {
    Automation automation;for (char c : str)automation.get(c);return automation.ans * automation.sign;}private:class Automation {
    private:string state = "start";unordered_map<string, vector<string>> table = {
    {
    "start",		{
    "start",	"signed",	"in_number",	"end"}},{
    "signed",		{
    "end",		"end",		"in_number",	"end"}},{
    "in_number",	{
    "end",		"end",		"in_number",	"end"}},{
    "end",			{
    "end",		"end",		"end",			"end"}}};int get_col(char c) {
    if (isspace(c))	return 0;if (c == '+' || c == '-')	return 1;if (isdigit(c))	return 2;return 3;}public:int sign = 1;ll ans = 0;void get(char c) {
    state = table[state][get_col(c)];if (state == "in_number") {
    ans = ans * 10 + c - '0';ans = sign == 1 ?min(ans, (ll)INT_MAX) :min(ans, -(ll)INT_MIN);}else if (state == "signed") {
    sign = c == '+' ? 1 : -1;}}};
};