Valid Number
Validate if a given string is numeric.
Some examples:
"0"=>true
" 0.1 "=>true
"abc"=>false
"1 a"=>false
"2e10"=>trueNote: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
Update (2015-02-10):
The signature of theC++function had been updated. If you still see your function signature accepts aconst char *argument, please click the reload button to reset your code definition.
输入一个字符串，判断它是不是有效的数字。
从例子中可以看出，该数字可以是整数，小数，甚至是科学计数法表示的数字(2e10);字符串的开头和结尾可以是空白符。并且开头可以有符号(+/-)。
2e10表示2的10次方，在AeB形式的数字中，A为一个正（负）数，B为一个正（负）整数。
编译原理课和计算原理课上，我们曾学过有限状态自动机。其中的一种表示方法为DFA(Deterministic Finite Automata)，确定有限状态自动机。
其中正则表达式(Regular expression)等价于非确定有限状态自动机（NFA），等价于确定有限状态自动机（DFA）。
也即RE<==>NFA<==>DFA
并且我们有程序化的算法可以把RE转化为NFA再转化为DFA。然后借助DFA进行编程就非常容易了。（扯远了）
图1： Sildes of Compiling Techniques, the University of Hong Kong
对于此题，我们先从正则表达式入手，符合题目要求的字符串用一个正则表达式表示。然后将正则表达式转换为DFA，再进行编程。思路会比较清晰。
编程时我们考虑，每读入一个新字符，我们就在DFA中进行一次状态转移。
我们先从最简单的整数入手，并且假设输入中不含有空白符。
1. 整数的正则表达式和DFA
整数的开头可能带符号，并且有多个数字出现，0可以位于开头。(比如00032是合法的)
所以整数的正则表达式为：
(-|\+)?\d+ (1)
其中\d表示一个0-9的数字；(-|\+)?表示数字的开头可以有符号，或者没有。
注意这里是\d+而不是\d*。因为我们认为单有一个符号或是空字符串不是合法的。
把(1)式转化为DFA即为：
DFA中共有1,2,3三个状态。1为起始状态，3为结束状态(同心环)。
n表示输入时一个0-9的数字，即正则中的\d符号。（抱歉我画图时脑袋里想的是number的首字母）
如果输入字符串停在状态3，则该字符串是合法的(一个整数)。
如果输入字符串没有停在状态3，则该字符串是非法的。
如果输入字符串出现了未在DFA中表示的字符，则跳到错误状态，表示该字符串不合法(比如突然出现一个字母或是奇奇怪怪的符号)。
2.整数或小数的正则表达式和DFA
我们在1的基础上，把小数也添加到正则表达式中。
需要指出，”.3″或”3.”都是合法的小数(分别表示0.3和3.0)，但单独一个”.”符号则是非法的。(可以在Python中试一下)
包含整数和小数的正则表达式为：
(-|\+)?(\d+\.?\d*|\.\d+) (2)
上面的正则表达式很复杂，容易看晕。实际解题时，我们可以直接画DFA的，这样会更加直观。
把(2)式转化为DFA：
上图共有五个状态，如果输入停在了状态3，则是一个整数；如果停在了状态5，则是一个小数。
如果停在了其他状态，或是出现了一个DFA中没有标明的输入，则非法。
3.整数、小数或科学计数法的正则表达式和DFA
最后，我们把科学计数法表示的数也加入到我们的正则中。
还记得本文开头提到的，科学计数法表示的数可以写为AeB的形式，其中A为正（负）数，B为正（负）整数吗？
(2)式已经把A给表示出来了，我们需要在(2)式后面再添加上eB的形式。
注意，前方高能。。。
高能。。
能。
(-|\+)?(\d+\.?\d*|\.\d+)(e(-|\+)?\d+)? (3)
我们不管它 ，还是来看DFA吧：
（上图应为小数、整数、科学计数法的DFA，请忽略标题……）
图中共有8个状态，前五个状态与(2)中的DFA完全一致，新加入的6,7,8是对应AeB中的B部分。实际上，B是一个正整数，所以你会发现678状态和123状态惊人地相似。
如果停在状态8，则输入是一个科学计数法表示的数字。
4. 开始编程
好了，我们可以根据上图画出的完整DFA进行编程了。
且慢，我们忽视了字符串开头和结尾存在空白字符的情况，如果加入空白字符的情况的话，DFA中需要增加一个状态来处理结尾的空白符，然后在正则表达式的首尾增加\s*匹配空白符：
\s*(-|\+)?(\d+\.?\d*|\.\d+)(e(-|\+)?\d+)?\s* (4)
请忽视上面的正则，因为在编程中并不会用到。
表示有限状态自动机的方法有很多，可以用一个二维数组，数组中存储的是相应的输入所应该跳转到的状态位置。或者是用函数表示法，每个状态用一个函数表示，状态的转移用函数的调用表示。
比如该作者的解法，就是用了一个二维数组transitionTable来记录DFA。
链接：https://github.com/fuwutu/LeetCode/blob/master/Valid%20Number.cpp
我们则采用函数表示法，会更直观一些。
我们用函数state1-state9表示DFA中的状态1-状态9.其中状态9是为了处理末尾的空白符。（开头的空白符可以通过修改状态1，在状态1中处理掉）
函数的返回值为bool。true表示字符串合法，false表示非法。
函数的参数为一个string，表示程序运行到该状态时输入的字符串。这里我们传了string的引用来节省内存开销。
bool isNumber(string s) {
return state1(s);
}
首先主调函数调用state1，我们进入起始状态。
bool state1(string& s){
//parse whitespace
while(s.empty() == false && s[0] == ' '){
s.erase(s.begin());
}
//i'm not an end state
if(s.empty() == true){
return false;
}
//go to state 2
if(s[0] == '-' || s[0] == '+'){
s.erase(s.begin());
return state2(s);
}
//go to state 3
else if(isNumeric(s[0])){
s.erase(s.begin());
return state3(s);
}
//go to state 4
else if(s[0] == '.'){
s.erase(s.begin());
return state4(s);
}
//not an acceptable char
else{
return false;
}
}
state1不是终结状态，如果s.empty()，返回false；
否则，取出s的第一个字符c。根据DFA，如果c == ‘-‘ || c == ‘+’ 跳至state2
如果c==’.’ ，跳至state4；
如果c是一个数字，跳至state3；
否则，输入不合法，返回false；
其他状态与此类似，每个状态函数的结构都很相似。
C++代码如下，它很长，但每个函数的结构都很简单，只要把每个函数与DFA中的相应状态关联起来就好。
class Solution {
public:
bool isNumber(string s) {
return state1(s);
}
bool state1(string& s){
//parse whitespace
while(s.empty() == false && s[0] == ' '){
s.erase(s.begin());
}
//i'm not an end state
if(s.empty() == true){
return false;
}
//go to state 2
if(s[0] == '-' || s[0] == '+'){
s.erase(s.begin());
return state2(s);
}
//go to state 3
else if(isNumeric(s[0])){
s.erase(s.begin());
return state3(s);
}
//go to state 4
else if(s[0] == '.'){
s.erase(s.begin());
return state4(s);
}
//not an acceptable char
else{
return false;
}
}
bool state2(string &s){
//this is not the end state
if(s.empty()){
return false;
}
//go to state 3
if(isNumeric(s[0])){
s.erase(s.begin());
return state3(s);
}
//go to state 4
else if(s[0] == '.'){
s.erase(s.begin());
return state4(s);
}
//not an acceptable char
else{
return false;
}
}
bool state3(string &s){
//parse numbers
while(s.empty() == false && isNumeric(s[0])){
s.erase(s.begin());
}
//i'm an end state, got an integer
if(s.empty()){
return true;
}
//go to state 6, may be an exponent
if(s[0] == 'e'){
s.erase(s.begin());
return state6(s);
}
//go to state 5, may be a float
else if(s[0] == '.'){
s.erase(s.begin());
return state5(s);
}
//go to state 9, parse whitespaces at tail
else if(s[0] == ' '){
s.erase(s.begin());
return state9(s);
}
//not an acceptable char
else{
return false;
}
}
bool state5(string &s){
//parse number
while(s.empty() == false && isNumeric(s[0])){
s.erase(s.begin());
}
//i'm an end state
if(s.empty()){
return true;
}
//go to state 9, parse whitespace at tail
if(s[0] == ' '){
s.erase(s.begin());
return state9(s);
}
//go to state 6
else if(s[0] == 'e'){
s.erase(s.begin());
return state6(s);
}
//not an acceptable char
else{
return false;
}
}
bool state4(string &s){
//i'm not an end state
if(s.empty()){
return false;
}
//go to state 5
if(isNumeric(s[0])){
s.erase(s.begin());
return state5(s);
}
//not an acceptable char
else{
return false;
}
}
bool state6(string &s){
//i'm not an end state
if(s.empty()){
return false;
}
//go to state 7
if(s[0] == '-' || s[0] == '+'){
s.erase(s.begin());
return state7(s);
}
//go to state 8
else if(isNumeric(s[0])){
s.erase(s.begin());
return state8(s);
}
//not an acceptable char
else{
return false;
}
}
bool state7(string &s){
//i'm not an end state
if(s.empty()){
return false;
}
//go to state 8
if(isNumeric(s[0])){
s.erase(s.begin());
return state8(s);
}
//not an acceptable char
else{
return false;
}
}
bool state8(string &s){
//parse number
while(s.empty() == false && isNumeric(s[0])){
s.erase(s.begin());
}
//i'm an end state
if(s.empty()){
return true;
}
if(s[0] == ' '){
s.erase(s.begin());
return state9(s);
}
//not an acceptable char
else{
return false;
}
}
bool state9(string &s){
//parse whitespace
while(s.empty() == false && s[0] == ' '){
s.erase(s.begin());
}
//i'm an end state
if(s.empty()){
return true;
}
//not an acceptable char
else{
return false;
}
}
bool isNumeric(char c){
return c <= '9' && c >= '0';
}
};
时间复杂度o(n)，n为字符串长度。
因为DFA中没有环路出现。所以最大的调用深度即为最长的到结束状态的路径，为1->2->4->5->6->7->8，7层。
速度还是比较理想的。
2015.4.11
于浙大玉泉
讲得非常清楚，谢谢~