A string representing a numeric value
1, Title Description
Please implement a function to judge whether the string represents a numeric value (including integer and decimal).
The values (in order) can be divided into the following parts:
Several spaces A decimal or integer ((optional) one 'e' or 'E' ，Followed by an integer Several spaces
Decimals (in order) can be divided into the following parts:
((optional) one symbolic character('+' or '-')
One of the following formats:
At least one digit followed by a dot '.'
At least one digit followed by a dot '.' ，Followed by at least one digit
One point '.' ，Followed by at least one digit
Integers (in order) can be divided into the following parts:
((optional) one symbolic character('+' or '-')
At least one digit
Some values are listed as follows:
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
Some non numerical values are listed as follows:
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
Example 1:
Input: s = "0"
Output: true
Example 2:
Input: s = "e"
Output: false
Example 3:
Input: s = "
Output: false
Example 4:
Input: S = ". 1"
Output: true
Tips:
1 <= s.length <= 20 s Only English letters (uppercase and lowercase) and numbers (0-9)，plus '+' ，minus sign '-' ，Space ' ' Or point '.' .
Author: Krahets
Link: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5d6vi6/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.
2, Problem solving ideas and code implementation
1. Problem solving ideas
At the beginning, I considered using c + + regular expression to realize this problem. It is simple and convenient. It can be solved in a few lines of code, but the execution of 1400 + test cases timed out, indicating that using regular expression directly is not the optimal solution. Therefore, consider writing your own code to identify whether the string is a value through the state machine. Through the same 1400 + test case, the efficiency is significantly improved.
2. C + + code implementation
class Solution {
private:
enum state_t {
start,
space,
symbol_e,//e/E
uper_case_e,//Capital E
dot,//Decimal point beginning with decimal point
dot_after_number,//A decimal point after a number
first_plus_minus,//Real sign
second_plus_minus,//Imaginary sign
numbers,//Real integer partial number
mumbers_after_dot,//Real decimal part
mumbers_after_e//Imaginary part number
};
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:
//Remove preceding spaces
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;
}
};
3, Submit results
summary
See the following code for the implementation of regular expression in c + +. The code structure is simple and difficult to implement the matching rules of regular expression. These rules may be flawed, or the implementation efficiency of regular expression library is not high. When it is used to judge whether a string is a numeric value, the efficiency is very slow and always times out, / ㄒo ㄒ) / ~ ~. If you have any suggestions to modify the following code, please leave a message and comment, learn from each other and make common progress. Thank you very much, O(∩∩) O~
class Solution {
public:
bool isNumber(string s) {
if (s.length() == 0) return false;
//decimal
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);
}
};