题目
有效数字
有效数字（按顺序）可以分成以下几个部分：
- 若干空格
- 一个小数或者整数
- （可选）一个’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;
}
};
