请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。
数值(按顺序)可以分成以下几个部分:
若干空格 一个 小数 或者 整数 (可选)一个 'e' 或 'E' ,后面跟着一个 整数 若干空格
小数(按顺序)可以分成以下几个部分:
(可选)一个符号字符('+' 或 '-') 下述格式之一: 至少一位数字,后面跟着一个点 '.' 至少一位数字,后面跟着一个点 '.' ,后面再跟着至少一位数字 一个点 '.' ,后面跟着至少一位数字
整数(按顺序)可以分成以下几个部分:
(可选)一个符号字符('+' 或 '-') 至少一位数字
部分数值列举如下:
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下:
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
示例 1:
输入:s = “0”
输出:true
示例 2:
输入:s = “e”
输出:false
示例 3:
输入:s = “.”
输出:false
示例 4:
输入:s = " .1 "
输出:true
提示:
1 <= s.length <= 20 s 仅含英文字母(大写和小写),数字(0-9),加号 '+' ,减号 '-' ,空格 ' ' 或者点 '.' 。
作者:Krahets
链接:https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5d6vi6/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
这个题目,一开始我是考虑使用c++的正则表达式来实现的,简单方便,几行代码搞定,但是1400+的测试用例执行超时,说明直接使用正则表达式并非最优解。因此,考虑自己编写代码,通过状态机来识别字符串是否是数值,通过同样的1400+测试用例测试,效率明显提高。
class Solution { private: enum state_t { start, space, symbol_e,//e/E uper_case_e,//大写E dot,//小数点开头的小数 dot_after_number,//小数点在数字后的小数 first_plus_minus,//实数符号 second_plus_minus,//虚数符号 numbers,//实数整数部分数字 mumbers_after_dot,//实数小数部分数字 mumbers_after_e//虚数部分数字 }; public: bool isNumber(string s) { state_t state = start; bool ret = false; int i = 0; int length = s.length(); while (i < length) { switch (state) { case start: //去除前面的空格 while (s[i] == ' ' && i < length) ++i; if (i >= length) goto end_flag; if (s[i] == '+' || s[i] == '-') { state = first_plus_minus; } else if (s[i] == '.') { state = dot; } else if (s[i] >= '0' && s[i] <= '9') { state = numbers; } else { ret = false; goto end_flag; } break; case space: while (i < length && s[i] == ' ') ++i; ret = i >= length ? true : false; goto end_flag; break; case symbol_e: ++i; if (i >= length) { ret = false; goto end_flag; } if (s[i] == '+' || s[i] == '-') { state = second_plus_minus; } else if (s[i] >= '0' && s[i] <= '9') { state = mumbers_after_e; } else { ret = false; goto end_flag; } break; case dot: ++i; if (i >= length) { ret = false; goto end_flag; } if (s[i] >= '0' && s[i] <= '9'){ state = mumbers_after_dot; } else { ret = false; goto end_flag; } break; case dot_after_number: ++i; if (i >= length) { ret = true; goto end_flag; } if (s[i] == 'e' || s[i] == 'E') { state = symbol_e; } else if (s[i] == ' ') { state = space; } else if (s[i] >= '0' && s[i] <= '9'){ state = mumbers_after_dot; } else { ret = false; goto end_flag; } break; case first_plus_minus: ++i; if (i >= length) { ret = false; goto end_flag; } if (s[i] >= '0' && s[i] <= '9') { state = numbers; } else if (s[i] == '.') { state = dot; } else { ret = false; goto end_flag; } break; case second_plus_minus: ++i; if (i >= length) { ret = false; goto end_flag; } if (s[i] >= '0' && s[i] <= '9') { state = mumbers_after_e; } else { ret = false; goto end_flag; } break; case numbers: ++i; if (i >= length) { ret = true; goto end_flag; } while (i < length && s[i] >= '0' && s[i] <= '9') ++i; if (i >= length) { ret = true; goto end_flag; } else if (s[i] == '.') { state = dot_after_number; } else if (s[i] == 'e' || s[i] == 'E') { state = symbol_e; } else if (s[i] == ' ') { state = space; } else { ret = false; goto end_flag; } break; case mumbers_after_dot: while (i < length && s[i] >= '0' && s[i] <= '9') ++i; if (i >= length) { ret = true; goto end_flag; } if (s[i] == ' ') { state = space; } else if (s[i] == 'e' || s[i] == 'E') { state = symbol_e; } else { ret = false; goto end_flag; } break; case mumbers_after_e: while (i < length && s[i] >= '0' && s[i] <= '9') ++i; if (i >= length) { ret = true; goto end_flag; } if (s[i] == ' ') { state = space; } else { ret = false; goto end_flag; } break; default://stop goto end_flag; } } end_flag: return ret; } };
c++的正则表达式实现见下面的代码,代码结构简单,难点的实现正则表达式的匹配规则,可能这些规则有瑕疵,也有可能是正则表达式的库实现效率不高,用来判断一个字符串是否为数值时效率很慢,总是超时,/(ㄒoㄒ)/~~。如下代码如果有修改建议,请留言评论,相互学习,共同进步,感激涕零,O(∩_∩)O~
class Solution { public: bool isNumber(string s) { if (s.length() == 0) return false; //小数 regex xiaoshu(" *[+-]?(([0-9]+[.]{1}[0-9]*)|([.]{1}[0-9]+))(([eE]{1}[+-]?[0-9]+)|( *))"); regex zhengshu(" *[+-]?[0-9]+(([eE]{1}[+-]?[0-9]+)|( *))"); return regex_match(s, xiaoshu) || regex_match(s, zhengshu); } };