SWE / MLE · Coding

Meta Valid Number:小数与指数的明确语法

按ASCII十进制语法解析有效数字,分别验证尾数、符号、小数点和整数指数。

题目重点:按ASCII十进制语法解析有效数字,分别验证尾数、符号、小数点和整数指数。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练无前后空白,ASCII digits,允许±、小数点、e/E和带符号整数指数;不接受NaN/Infinity/hex/下划线。题面若允许trim需外层显式处理。
  • 尾数至少一位digit,允许1.和.1;指数存在时至少一位digit,不允许小数指数。返回bool,不实际转float,因此不会受溢出决定合法性。

解题路线

  1. 先消耗可选符号,再消耗整数digits;可选点后消耗小数digits,两部分总数至少1。只有点/只有符号不能通过。
  2. 如果遇e/E,再消耗可选指数符号和连续ASCII digits,要求至少1。最后必须正好到字符串末尾,不能忽略尾部垃圾。
  3. 各阶段最多前进不回退,状态等价于有限状态机。明确grammar比调用float更符合题面:float可能接受空白/特殊值、丢失精度或溢出,却不代表训练语法有效。
  4. ASCII判断使用0≤char≤9,Python isdigit会接受一些Unicode数字,不符合本合同。大写E与小写e都合法,但指数只能出现一次。
  5. 测试oracle用独立正则grammar fullmatch,不把另一个同样逐字符parser当对照;加入全角数字、末尾换行和长指数确保不是数值转换。

手动走一遍

+.8、46.e3、-90E-2合法;.、e3、1e、1e2.3、--1、1x非法。1e999999在语法上合法,即使机器float无法保持有限值;“3 ”本合同拒绝,若允许trim需先strip再调用。

Python 参考实现

下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。

代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。

def is_number(text):
    """ASCII decimal grammar, no whitespace/NaN/hex; e/E with integer exponent.

    mantissa: [+-]?(digits(.digits*)?|.digits+); exponent: [eE][+-]?digits+
    """
    n=len(text);i=0
    if i<n and text[i] in '+-':i+=1
    digits=0
    while i<n and '0'<=text[i]<='9':digits+=1;i+=1
    if i<n and text[i]=='.':
        i+=1
        while i<n and '0'<=text[i]<='9':digits+=1;i+=1
    if digits==0:return False
    if i<n and text[i] in 'eE':
        i+=1
        if i<n and text[i] in '+-':i+=1
        start=i
        while i<n and '0'<=text[i]<='9':i+=1
        if i==start:return False
    return i==n

复杂度

O(n)时间、O(1)辅助空间,不进行任意精度数值求值。字符串长度是主要规模,正则oracle仅供测试,不是用数值转换偷换语法验证。

易错点与追问

容易失分的边界

  • 指数复用小数尾数parser,会错误接受1e2.3。
  • 使用isdigit但合同只接受ASCII,会接受不应出现的字符。

继续深挖

  • 如果允许分隔符_,它只能出现在数字之间还是任意位置?先扩grammar再改状态。
  • 验证成功后还要转数值,溢出/精度应如何返回?这是另一个接口结果。
✓已复制微信号!