思路
状态机或递归下降的语法分析。时间复杂度 $O(n)$,空间复杂度 $O(1)$。
CPP
class Solution {
public:
enum State {
Empty, // 空字符
Sign, // 正负号(前面无数字)
Int, // 整数内部
Dot, // 小数点(前面无数字)
DotAfterInt, // 小数点(前面有数字)
Fraction, // 小数内部
ExpSymbol, // 指数符号
ExpSign, // 指数正负号
ExpInt, // 指数内部
SyntaxError, // 格式错误
Finish // 解析成功
};
#define isSign(c) (c == '+' || c == '-')
#define isExpSym(c) (c == 'e' || c == 'E')
#define isDigit(c) (c >= '0' && c <= '9')
bool isNumber(string s) {
if (s.size() == 0) return false;
auto t = Empty;
int i = 0;
while (t != SyntaxError && t != Finish) {
char c = s[i];
switch (t) {
case Empty:
if (isSign(c)) t = Sign;
else if (isDigit(c)) t = Int;
else if (c == '.') t = Dot;
else t = SyntaxError;
break;
case Sign:
if (isDigit(c)) t = Int;
else if (c == '.') t = Dot;
else t = SyntaxError;
break;
case Int:
if (isDigit(c)) break;
else if (c == '.') t = DotAfterInt;
else if (isExpSym(c)) t = ExpSymbol;
else t = SyntaxError;
break;
case Dot:
case DotAfterInt:
if (isDigit(c)) t = Fraction;
else t = SyntaxError;
break;
case Fraction:
if (isDigit(c)) break;
else if (isExpSym(c)) t = ExpSymbol;
else t = SyntaxError;
break;
case ExpSymbol:
if (isSign(c)) t = ExpSign;
else if (isDigit(c)) t = ExpInt;
else t = SyntaxError;
break;
case ExpSign:
if (isDigit(c)) t = ExpInt;
else t = SyntaxError;
break;
case ExpInt:
if (!isDigit(c)) t = SyntaxError;
break;
}
if (++i == s.size()) {
switch (t) {
case Sign:
case Dot:
case ExpSymbol:
case ExpSign:
t = SyntaxError;
break;
default:
t = Finish;
}
}
}
return t == Finish;
}
};
JAVA
class Solution {
enum State {
Empty, // 空字符
Sign, // 正负号(前面无数字)
Int, // 整数内部
Dot, // 小数点(前面无数字)
DotAfterInt, // 小数点(前面有数字)
Fraction, // 小数内部
ExpSymbol, // 指数符号
ExpSign, // 指数正负号
ExpInt, // 指数内部
SyntaxError, // 格式错误
Finish // 解析成功
}
boolean isDigit(char c) { return c >= '0' && c <= '9'; }
public boolean isNumber(String s) {
if (s.length() == 0) return false;
State st = State.Empty;
int i = 0;
while (st != State.SyntaxError && st != State.Finish) {
char c = s.charAt(i);
switch (st) {
case Empty:
if (c == '+' || c == '-') st = State.Sign;
else if (isDigit(c)) st = State.Int;
else if (c == '.') st = State.Dot;
else st = State.SyntaxError;
break;
case Sign:
if (isDigit(c)) st = State.Int;
else if (c == '.') st = State.Dot;
else st = State.SyntaxError;
break;
case Int:
if (isDigit(c)) break;
else if (c == '.') st = State.DotAfterInt;
else if (c == 'e' || c == 'E') st = State.ExpSymbol;
else st = State.SyntaxError;
break;
case Dot:
case DotAfterInt:
if (isDigit(c)) st = State.Fraction;
else st = State.SyntaxError;
break;
case Fraction:
if (isDigit(c)) break;
if (c == 'e' || c == 'E') st = State.ExpSymbol;
else st = State.SyntaxError;
break;
case ExpSymbol:
if (c == '+' || c == '-') st = State.ExpSign;
else if (isDigit(c)) st = State.ExpInt;
else st = State.SyntaxError;
break;
case ExpSign:
if (isDigit(c)) st = State.ExpInt;
else st = State.SyntaxError;
break;
case ExpInt:
if (!isDigit(c)) st = State.SyntaxError;
break;
}
if (++i == s.length()) {
if (st == State.Sign
|| st == State.Dot
|| st == State.ExpSymbol
|| st == State.ExpSign) st = State.SyntaxError;
else st = State.Finish;
}
}
return st == State.Finish;
}
}
PYTHON3
"""
decimal: unsigned-decimal
| sign unsigned-decimal
unsigned-decimal: unsigned-integer . (special case)
| unsigned-exp-prefix
| unsigned-exp-prefix exp-sym exp-integer
unsigned-integer: digit | digit unsigned-integer
unsigned-exp-prefix: unsigned-integer
| . unsigned-integer
| unsigned-integer . unsigned-integer
exp-integer: unsigned-integer
| sign unsigned-integer
sign: + | -
digit: 0-9
exp-sym: e | E
"""
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
self.s = s
self.i = 0
return self.decimal() and self.i == len(s)
def decimal(self):
self.sign();
return self.unsigned_decimal()
def unsigned_decimal(self):
return self.unsigned_exp_prefix()
def unsigned_exp_prefix(self):
dot_before_digit = self.dot()
t = self.unsigned_integer()
if not dot_before_digit and self.dot():
is_exp_prefix = self.unsigned_integer()
else:
is_exp_prefix = t
if is_exp_prefix and self.exp_sym():
return self.exp_integer()
return t
def unsigned_integer(self):
if self.digit():
self.unsigned_integer()
return True
return False
def exp_integer(self):
self.sign();
return self.unsigned_integer()
def peek(self):
if self.i >= len(self.s):
return "x"
return self.s[self.i]
def valid(self, checker):
if checker(self.peek()):
self.i += 1
return True
return False
def dot(self):
return self.valid(lambda c: c == '.')
def sign(self):
return self.valid(lambda c: c in '+-')
def digit(self):
return self.valid(lambda c: c in '0123456789')
def exp_sym(self):
return self.valid(lambda c: c in 'eE')