LeetCode 有一道叫 Valid Number 的题，题目很简单，就是判断一个字符串是不是合法数字。
Valid Number
有趣的是，这道题是 Hard 级别，总的提交次数有70多万次，最后通过的只有9万，12.9%的通过率。谷歌搜了一下，网上对这道题骂声一片。
因为数字的规则实在比想象中复杂太多了，不仅要考虑 + - 号，考虑小数点，还要考虑科学记数法的规则，例如 1.2e−4 里面幂的处理。复杂如下，这是Grandyang 调试测出来的规则。
string s1 = "0"; // True
string s2 = " 0.1 "; // True
string s3 = "abc"; // False
string s4 = "1 a"; // False
string s5 = "2e10"; // True
string s6 = "-e10"; // False
string s7 = " 2e-9 "; // True
string s8 = "+e1"; // False
string s9 = "1+e"; // False
string s10 = " "; // False
string s11 = "e9"; // False
string s12 = "4e+"; // False
string s13 = " -."; // False
string s14 = "+.8"; // True
string s15 = " 005047e+6"; // True
string s16 = ".e1"; // False
string s17 = "3.e"; // False
string s18 = "3.e1"; // True
string s19 = "+1.e+5"; // True
string s20 = " -54.53061"; // True
string s21 = ". 1"; // False
能搜到的有两种解答方式，要么用 while 循环硬扛，要么如下面的有限状态机示意图，这两种方法都极其考验人类的耐心，实在敬佩用这两种方法答题还能通过的人。
通过循环判断，并且添加各种条件判断的问题在于，复杂度太高了，人脑处理这么多规则根本处理不过来，这是非常糟糕的做法，不易维护，可读性差。这是 Grandyang 的解法，丧心病狂的复杂。
class Solution {
public:
bool isNumber(string s) {
int len = s.size();
int left = 0, right = len - 1;
bool eExisted = false;
bool dotExisted = false;
bool digitExisited = false;
// Delete spaces in the front and end of string
while (s[left] == ' ') ++left;
while (s[right] == ' ') --right;
// If only have one char and not digit, return false
if (left >= right && (s[left] < '0' || s[left] > '9')) return false;
//Process the first char
if (s[left] == '.') dotExisted = true;
else if (s[left] >= '0' && s[left] <= '9') digitExisited = true;
else if (s[left] != '+' && s[left] != '-') return false;
// Process the middle chars
for (int i = left + 1; i <= right - 1; ++i) {
if (s[i] >= '0' && s[i] <= '9') digitExisited = true;
else if (s[i] == 'e' || s[i] == 'E') { // e/E cannot follow +/-, must follow a digit
if (!eExisted && s[i - 1] != '+' && s[i - 1] != '-' && digitExisited) eExisted = true;
else return false;
} else if (s[i] == '+' || s[i] == '-') { // +/- can only follow e/E
if (s[i - 1] != 'e' && s[i - 1] != 'E') return false;
} else if (s[i] == '.') { // dot can only occur once and cannot occur after e/E
if (!dotExisted && !eExisted) dotExisted = true;
else return false;
} else return false;
}
// Process the last char, it can only be digit or dot, when is dot, there should be no dot and e/E before and must follow a digit
if (s[right] >= '0' && s[right] <= '9') return true;
else if (s[right] == '.' && !dotExisted && !eExisted && digitExisited) return true;
else return false;
}
};
看看 SimonS 用有限状态机的图解：
状态机
这个图的复杂度也尤其高。
其实这种题最适合用解析器组合子来做。
写个parser combinator 边看着《幸福三重奏》福原爱秀恩爱边 debug 不怎么费脑细胞就搞定了，就是 Java 代码太累赘，200行代码看起来比别的答案都长，用Kotlin 应该能短点。
通过组合子定义 Number 规则，复杂度瞬间降低
Parser validNumberRule1 = new And(new ZeroOrOne(sign), multiDigit, dot, multiDigit);
Parser validNumberRule2 = new And(new ZeroOrOne(sign), multiDigit, ePart);
Parser validNumberRule3 = new And(new ZeroOrOne(sign), multiDigit, dot, new ZeroOrOne(multiDigit), ePart);
Parser validNumberRule4 = new And(new ZeroOrOne(sign), dot, multiDigit, new ZeroOrOne(ePart));
Parser validNumberRule5 = new And(new ZeroOrOne(sign), multiDigit, new ZeroOrOne(dot));
完整的代码如下：
class Solution {
public boolean isNumber(String s) {
// write your code here
if (s == null || s.trim().length() == 0 || s.trim().equals(".")) {
return false;
}
Parser digit = new SAT(new IsDigit(), new Item());
Parser sign = new SAT(new IsSign(), new Item());
Parser dot = new Ch('.');
Parser letterE = new Ch('e');
Parser multiDigit = new Many(digit);
Parser ePart = new And(letterE, new ZeroOrOne(sign), multiDigit);
Parser validNumberRule1 = new And(new ZeroOrOne(sign), multiDigit, dot, multiDigit);
Parser validNumberRule2 = new And(new ZeroOrOne(sign), multiDigit, ePart);
Parser validNumberRule3 = new And(new ZeroOrOne(sign), multiDigit, dot, new ZeroOrOne(multiDigit), ePart);
Parser validNumberRule4 = new And(new ZeroOrOne(sign), dot, multiDigit, new ZeroOrOne(ePart));
Parser validNumberRule5 = new And(new ZeroOrOne(sign), multiDigit, new ZeroOrOne(dot));
Parser validNumber = new Or(validNumberRule5, validNumberRule1, validNumberRule2, validNumberRule3, validNumberRule4);
try {
Result result = validNumber.parse(s.trim());
return true;
} catch(Exception e) {
return false;
}
}
interface Predicate {
boolean satisfy(String target);
}
interface Parser {
Result parse(String target);
}
static class ZeroOrOne implements Parser {
private Parser parser;
public ZeroOrOne(Parser parser) {
this.parser = parser;
}
@Override
public Result parse(String target) {
try {
return parser.parse(target);
} catch (Exception e) {
//do nothing
}
return Result.buildResult("", target);
}
}
static class Or implements Parser {
private Parser[] parsers;
public Or(Parser... parsers) {
this.parsers = parsers;
}
@Override
public Result parse(String target) {
for (Parser parser : parsers) {
try {
Result result = parser.parse(target);
if (result.remain.length() == 0) {
return result;
}
} catch (Exception e) {
//do nothing
}
}
throw new RuntimeException("OR Ignore Expect " + parsers + " parse " + target);
}
}
static class Many implements Parser {
private Parser parser;
public Many(Parser parser) {
this.parser = parser;
}
@Override
public Result parse(String target) {
Result result = parser.parse(target);
try {
while (result.remain.length() > 0) {
result = Result.concat(result, parser.parse(result.remain));
}
} catch (Exception e) {
//do nothing
}
return result;
}
}
static class Item implements Parser {
@Override
public Result parse(String target) {
return Result.buildResult(target.substring(0, 1),
target.substring(1, target.length()));
}
}
static class And implements Parser {
private Parser[] parsers;
public And(Parser... parsers) {
this.parsers = parsers;
}
@Override
public Result parse(String target) {
Result result = Result.buildResult("", target);
for (Parser parser : parsers) {
result = Result.concat(result, parser.parse(result.remain));
}
return result;
}
}
static class SAT implements Parser {
private Predicate predicate;
private Parser parser;
public SAT(Predicate predicate, Parser parser) {
this.predicate = predicate;
this.parser = parser;
}
@Override
public Result parse(String target) {
Result result = parser.parse(target);
if (predicate.satisfy(result.recognized))
return result;
throw new RuntimeException("parse error: " + parser + " " + predicate + " parse " + target + " fail");
}
}
static class Result {
private String recognized;
private String remain;
static Result buildResult(String recognized, String remain) {
Result result = new Result();
result.recognized = recognized;
result.remain = remain;
return result;
}
static Result concat(Result result1, Result result2) {
return Result.buildResult(result1.recognized + result2.recognized, result2.remain);
}
@Override
public String toString() {
return "recognized: " + recognized + " remain: " + remain;
}
}
static class IsSign implements Predicate {
@Override
public boolean satisfy(String target) {
return target.charAt(0) == '+' || target.charAt(0) == '-';
}
}
static class Ch implements Parser {
private char c;
public Ch(char c) {
this.c = c;
}
@Override
public Result parse(String target) {
Item item = new Item();
Result result = item.parse(target);
if (String.valueOf(c).equals(result.recognized)) {
return result;
}
throw new RuntimeException("parser error: Ch parser " + c + " parse error");
}
}
static class IsDigit implements Predicate {
@Override
public boolean satisfy(String target) {
return target.charAt(0) >= '0' && target.charAt(0) <= '9';
}
}
}
