[LeetBook]【学习日记】有效数字——状态机

题目

有效数字

有效数字（按顺序）可以分成以下几个部分：

• 若干空格
• 一个小数或者整数
• （可选）一个’e’或’E’，后面跟着一个整数
• 若干空格

小数（按顺序）可以分成以下几个部分：

• （可选）一个符号字符（‘+‘或’-’）
• 下述格式之一：
  • 至少一位数字，后面跟着一个点 ‘.’
  • 至少一位数字，后面跟着一个点 ‘.’,后面再跟着至少一位数字
  • 一个点 ‘.’,后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

• （可选）一个符号字符（‘+‘或’-’）
• 至少一位数字

部分有效数字列举如下：[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”,
“-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]

部分无效数字列举如下：[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”,
“95a54e53”]

给你一个字符串 s，如果 s 是一个有效数字，请返回 true。

示例 1：

输入：s = “0” 输出：true

示例 2：

输入：s = “e” 输出：false

示例 3：

输入：s = “.” 输出：false

提示：

1 <= s.length <= 20 s 仅含英文字母（大写和小写），数字（0-9），加号’+‘，减号’-‘，空格’ ‘或者点’.'。

解法

• 这道题很容易想到遍历字符串，对不同情况进行判断，遇到不符合题意的情况就直接退出
• 但是情况数比较多，需要写很多判断分支，比如底数是否有正负符号就有3种情况，指数有没有正负符号又是三种情况，这已经有九种情况符合题意了
• 能不能有一种方法，以简洁的方式规定好每种情况后面可以出现的情况，一旦出现了不在规定里的情况，就不为有效数字；并且如果在还未完成有效数字时，在某个中间情况戛然而止，也不为有效数字
• 这其实有点像拓扑排序，在这题中，对有向无环图，定义每个节点以及所有有效的最终节点，查找从起始节点 u 是否有路径 u->v 通往最终节点 v
  

class Solution {
public:bool validNumber(string s) {//0.前导空格->0,1,2,4//1.底数正负符号->2,4//2.底数有整数部分的整数（234的2）->2,3,5,8//3.小数点或者点后的数字->3,5,8//4.底数没有整数部分时的小数点（.123的.），当小数点后有数字->3//5.e或者E->6,7//6.指数正负符号->7//7.指数部分的数字->7,8//8.后导空格->8//2,3,7,8为正确的出口vector<map<char, int>> states = {{{' ',0}, {'s',1}, {'d',2}, {'.',4}},   //在0状态遍历到的符号对应的可以转移的状态{{'d',2}, {'.',4}},                     //1状态转移{{'d',2}, {'.',3}, {'e',5}, {' ',8}},   //2状态转移{{'d',3}, {'e',5}, {' ',8}},            //3{{'d',3}},                              //4{{'s',6}, {'d',7}},                     //5{{'d',7}},                              //6{{'d',7}, {' ',8}},                     //7{{' ',8}}                               //8};char curChType = '?';//当前字符类型，数字'd'、符号's'、幂符号'e'、点'.'、空格' 'int curState = 0;//初始状态设置为0，因为0没有前驱状态for(auto &ch:s){if(isdigit(ch)) curChType='d';else if(ch=='+' || ch=='-') curChType='s';else if(ch=='e' || ch=='E') curChType='e';else if(ch=='.') curChType='.';else if(ch==' ') curChType=' ';else return false;if(states[curState].find(curChType) != states[curState].end()){curState = states[curState].find(curChType)->second;}else return false;}return curState==2 || curState==3 || curState==7 || curState==8;}
};