面试题20：表示数值的字符串

从“600. 为什么合法”开始

先预测：600.、-.123、12e、12e+5.4 四个输入中，哪些是表示数值的字符串？作者答案依次是合法、合法、非法、非法。小数点后可以没有数字，但前面必须已经有整数；小数点前也可以没有数字，但后面必须至少有一位。指数后则只能是完整整数，不能再出现小数点。

这不是把字符逐个加入“允许集合”就能解决的问题。同一个正负号出现在开头或指数后合法，出现在整数中间非法；同一个点号只能出现在指数之前，且点两侧至少一侧有数字。必须同时记录当前位于哪一段文法，以及扫描到了哪里。

作者把合法形式概括为两类：A 后面可接点号和可选 B，再可接指数；或者直接由点号和 B 开始，再可接指数。A 和指数中的 C 是，B 是。

这套规则准确区分整数部分与小数部分：A 已经提供数字时，点后的 B 可以为空，所以 600. 合法；A 为空时，B 必须非空，所以 .123 合法而单独的点非法。指数e或E若出现，前面的基数必须已经有效，后面的 C 必须完整。

两个扫描器共享同一个游标

scanUnsignedInteger 从当前位置连续消费数字，并返回是否至少消费一位。scanInteger 先消费可选符号，再调用无符号扫描器。二者不仅返回真假，还要推进调用者持有的位置，因此作者参数类型是指向指针的指针。

将“下一个尚未处理字符的位置”称为。每个阶段开始时，游标指向该语法单元入口；结束时，它停在第一个不属于该单元的字符。调用者根据这个字符决定是否进入小数或指数阶段。

例如 -123.45e+6 的整数扫描先越过负号和123，停在点号；小数扫描越过45，停在 e；指数扫描越过正号和6，停在字符串结尾。每个函数只负责一个局部文法，组合函数负责阶段顺序。

忠实实现作者的三阶段扫描

下面把作者的双指针参数改写成引用传递，但保留完全相同的游标副作用和布尔组合。输入为空指针立即失败，空字符串因为三个数字扫描器都没有消费而失败。

bool scanUnsignedInteger(const char*& cursor) {
    const char* before = cursor;
    while (*cursor != 0 &&
           *cursor >= '0' && *cursor <= '9') {
        ++cursor;
    }
    return cursor > before;
}
 
bool scanInteger(const char*& cursor) {
    if (*cursor == '+' || *cursor == '-') {
        ++cursor;
    }
    return scanUnsignedInteger(cursor);
}
 
bool isNumeric(const char* input) {
    if (input == nullptr) return false;
 
    const char* cursor = input;
    bool numeric = scanInteger(cursor);
 
    if (*cursor == '.') {
        ++cursor;
        numeric = scanUnsignedInteger(cursor) || numeric;
    }
 
    if (*cursor == 'e' || *cursor == 'E') {
        ++cursor;
        numeric = numeric && scanInteger(cursor);
    }
 
    return numeric && *cursor == 0;
}

整数阶段可能失败却仍推进一个符号。例如输入 -.123 时，scanInteger 消费负号，但因点号前没有数字返回 false；随后小数阶段消费123并返回 true，或运算让整个基数恢复为有效。这正是允许有符号的无整数部分小数。

点号阶段的写法必须让 scanUnsignedInteger 位于或运算左侧。C++ 的会跳过不必要的右操作数。若误写成 numeric || scanUnsignedInteger(cursor)，当点前已有数字时右侧不会执行，小数位没有被消费，最终完整消费检查会把 123.45 判为非法。

指数阶段则使用 numeric && scanInteger(cursor)。基数无效时，无论指数是什么都不可能变为有效，短路跳过指数扫描不影响最终 false；基数有效时必须执行指数扫描，确保 e 后至少有一位整数数字。

小数和指数不能任意调换

组合函数固定按“整数、可选小数、可选指数”前进。点号只检查一次，所以 1.2.3 在第二个点停住；指数阶段之后不再检查点号，所以 12e+5.4 在指数整数5后停住。最终残留检查将二者拒绝。

把这种最后要求游标恰好位于输入末尾的规则称为。它能用很少分支拒绝 1a3.14、1+23 等输入：扫描器不必认识所有非法形式，只需在首个不属于当前单元的字符处停止，最后发现残留即可。

“符号位与完整消费”必须一起测试。连续符号 +-5 的整数扫描消费第一个正号后，第二个负号不是数字，于是失败并残留；1+23 先把1识别为有效整数，但加号既不是点也不是指数，最终因未到末尾失败。局部扫描成功不代表整个输入成功。

为什么点号两侧使用或，指数两侧使用与

小数点前后只要求至少一侧有数字，因此基数有效条件是“点前数字存在，或点后数字存在”。这覆盖 233.、.666 和 233.666，同时拒绝单独的点与加点。

指数两侧则都必须有效：e 前要有合法基数，e 后要有有符号整数，所以使用与运算。12e 失败是因为 C 未消费数字；e1 和 .e1 失败是因为基数无效；12e+5.4 即使指数整数 +5 成功，点号残留仍使整体失败。

若把指数 C 错用无符号扫描器，-1E-16 会被拒绝；若把小数 B 错用有符号扫描器，1.+2 会被错误接受。复用函数前必须先对照语法职责，不能因为它们都“扫描数字”就互换。

用字符串视图显式返回消费量

裸指针版本依赖空字符哨兵，并把返回真假和修改位置绑在一起。工程代码可使用字符串视图与下标，把边界放在容器长度内。扫描器返回是否消费数字，位置仍由引用更新：

#include <string_view>
 
bool scanUnsigned(std::string_view text, std::size_t& pos) {
    const std::size_t begin = pos;
    while (pos < text.size() &&
           text[pos] >= '0' && text[pos] <= '9') {
        ++pos;
    }
    return pos > begin;
}
 
bool scanSigned(std::string_view text, std::size_t& pos) {
    if (pos < text.size() &&
        (text[pos] == '+' || text[pos] == '-')) {
        ++pos;
    }
    return scanUnsigned(text, pos);
}
 
bool isNumeric(std::string_view text) {
    std::size_t pos = 0;
    bool numeric = scanSigned(text, pos);
 
    if (pos < text.size() && text[pos] == '.') {
        ++pos;
        const bool fraction = scanUnsigned(text, pos);
        numeric = fraction || numeric;
    }
 
    if (pos < text.size() &&
        (text[pos] == 'e' || text[pos] == 'E')) {
        ++pos;
        const bool exponent = scanSigned(text, pos);
        numeric = numeric && exponent;
    }
 
    return numeric && pos == text.size();
}

这里把有副作用调用先保存到局部变量，再做布尔组合，可避免读者漏看短路顺序。每个字符最多被某个扫描器访问一次，时间 O(n)；只保存位置和少量布尔值，额外空间 O(1)。

不应直接用带区域设置的 isdigit 代替明确的 ASCII 判断，除非先把 char 转为 unsigned char 并确认需求允许本地化数字。原题只接受0到9；全角数字、阿拉伯文数字和下划线分隔符都不在契约内。

语法校验不是数值转换

本函数只判断字符形式，不计算数值，因此 1.79769313486232E+308 合法，即使目标浮点类型在某些平台上可能溢出。语法合法、可转换、转换不溢出是三个不同阶段。生产解析器应在校验后调用受控转换，并检查范围与舍入错误。

同理，前导零、负零、极大指数都按本题文法合法。若业务规则禁止 001、要求金额最多两位小数，或把指数范围限制在某区间，需要在本题语法之上增加语义约束，不能悄悄改变“数值字符串”的原书答案。

作者实现不接受前后空格，因为第一次扫描会在空格处失败，最后也不会跳过空格。很多平台的数值解析函数会自动忽略空白，但那是另一份契约。若需要允许空格，应在入口明确裁剪，或设计具有起始和结束空格状态的 DFA，并增加相应测试。

状态机确实能表达同一语言：把符号、整数、小数点、分数、指数标记、指数符号、指数数字设为状态即可。但原书核心是扫描器组合与指针推进。DFA 适合语法继续扩展时集中维护转移；分段扫描更直接对应 A、B、C 文法，二者不应混成不同边界的答案。

作者21组测试怎样分层

前九组合法输入覆盖整数、带符号整数、普通小数、尾点小数、无整数部分小数、正负指数和接近双精度上界的长数值。后十二组非法输入覆盖指数缺位、字母杂质、中间符号、重复点、连续符号、指数小数、单独点、无基数指数、加点、空串和空指针。

把全部官方输入写成表驱动测试，能让指针版与字符串视图版逐项交叉校验：

#include <cassert>
 
void testNumericStrings() {
    const struct { const char* text; bool expected; } cases[] = {
        {"100", true},
        {"123.45e+6", true},
        {"+500", true},
        {"5e2", true},
        {"3.1416", true},
        {"600.", true},
        {"-.123", true},
        {"-1E-16", true},
        {"1.79769313486232E+308", true},
        {"12e", false},
        {"1a3.14", false},
        {"1+23", false},
        {"1.2.3", false},
        {"+-5", false},
        {"12e+5.4", false},
        {".", false},
        {".e1", false},
        {"e1", false},
        {"+.", false},
        {"", false},
        {nullptr, false},
    };
 
    for (const auto& item : cases) {
        assert(isNumeric(item.text) == item.expected);
    }
}

字符串视图重载不能接收空指针，因此空指针应由外层 C 接口单独测试，再把非空内容交给安全核心。还应补充 +.5、46.e3、前后空格、全角数字和极长输入，明确它们在当前契约下的预期。

属性测试可以随机生成符合 A、B、C 文法的字符串并要求全部通过，再随机插入字母、第二个点或错误位置符号并要求失败。随机测试不能替代21组固定回归，但能发现组合边界遗漏。

正确性证明

scanUnsigned 恰好消费当前位置开始的最大数字前缀，并只在长度至少一时返回真；scanSigned 在此前最多消费一个符号，因此恰好识别有符号整数。它们离开时游标总停在该单元后的第一字符。

组合函数先识别 A。若有点号，再识别 B，并以或运算保证点两侧至少一侧有数字；因此基数恰好覆盖 A、A.、A.B 或 .B。若随后出现 e 或 E，再以与运算要求基数已经有效且 C 是有符号整数。

最后完整消费排除所有未被上述文法识别的后缀。由三个扫描器的局部正确性和固定阶段顺序可知，函数接受且仅接受原书两种数值形式，既不会漏掉600.与-.123，也不会误收12e和12e+5.4。

本章练习

本章回顾

1. 原书文法由有符号整数A、无符号小数尾B和有符号指数C组合。
2. A存在时B可空，A不存在时B必须非空，因此600.与-.123都合法。
3. 指数e或E前必须已有合法基数，后面必须是至少一位的有符号整数。
4. 扫描游标始终停在首个未消费字符，阶段按整数、小数、指数固定前进。
5. 小数两侧有效性使用或，指数两侧有效性使用与。
6. 短路求值顺序会影响带副作用扫描器是否执行，不能随意交换操作数。
7. 最终完整消费统一拒绝第二个点、中间符号、字母和指数小数。
8. 算法时间 O(n)、空间 O(1)，但只做语法验证，不处理转换范围。

名词解释