0065. Valid Number ================== 题目信息 -------- :题号: 0065. 有效数字 :难度: Hard :主题: 字符串、语法解析、有限状态机 :原题: `LeetCode 0065 `_ :重点: 从分段匹配数字语法,推导到用有限见证变量完成一次扫描 题目重述 -------- 给定字符串 ``s``,判断它是否完整表示一个合法十进制数。 底数可以是整数或小数,并允许一个可选的前导 ``+`` 或 ``-``。合法小数必须至少包含一个数字,因此 ``"2."``、``".8"`` 和 ``"2.8"`` 都合法,单独的 ``"."`` 不合法。 底数后可以出现一个可选的指数部分。指数以 ``e`` 或 ``E`` 开始,后面可以有一个符号,并且必须包含至少 一个数字。指数只能是整数,不能包含小数点。 整个字符串都必须被上述语法消费,不能出现额外字符。约束为 ``1 <= s.length <= 20``,字符只可能是 英文字母、数字、加号、减号或小数点。 自建示例 -------- .. code-block:: text 输入:s = "-.9e-2" 输出:true 底数 ``-.9`` 至少包含一个数字,指数 ``-2`` 是带符号整数。 .. code-block:: text 输入:s = "46.e3" 输出:true 小数点前已有数字,所以 ``46.`` 是合法底数;指数 ``3`` 也完整。 .. code-block:: text 输入:s = "1e+" 输出:false 指数符号后没有数字,指数部分未完成。 .. code-block:: text 输入:s = "1.2.3" 输出:false 底数中只能出现一个小数点。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: enum class State { Start, Sign, Integer, PointWithoutInteger, PointAfterInteger, Fraction, Exponent, ExponentSign, ExponentInteger, Invalid }; bool isDigit(char ch) { return ch >= '0' && ch <= '9'; } bool isSign(char ch) { return ch == '+' || ch == '-'; } bool isExponent(char ch) { return ch == 'e' || ch == 'E'; } bool parseDigits(const std::string& s, int& index) { const int start = index; while (index < static_cast(s.size()) && isDigit(s[index])) { ++index; } return index > start; } bool grammarParser(const std::string& s) { int index = 0; const int length = static_cast(s.size()); if (index < length && isSign(s[index])) { ++index; } const bool integerDigits = parseDigits(s, index); bool fractionDigits = false; if (index < length && s[index] == '.') { ++index; fractionDigits = parseDigits(s, index); } if (!integerDigits && !fractionDigits) { return false; } if (index < length && isExponent(s[index])) { ++index; if (index < length && isSign(s[index])) { ++index; } if (!parseDigits(s, index)) { return false; } } return index == length; } bool finiteStateMachine(const std::string& s) { State state = State::Start; for (char ch : s) { const bool digit = isDigit(ch); switch (state) { case State::Start: if (digit) { state = State::Integer; } else if (isSign(ch)) { state = State::Sign; } else if (ch == '.') { state = State::PointWithoutInteger; } else { state = State::Invalid; } break; case State::Sign: if (digit) { state = State::Integer; } else if (ch == '.') { state = State::PointWithoutInteger; } else { state = State::Invalid; } break; case State::Integer: if (digit) { state = State::Integer; } else if (ch == '.') { state = State::PointAfterInteger; } else if (isExponent(ch)) { state = State::Exponent; } else { state = State::Invalid; } break; case State::PointWithoutInteger: state = digit ? State::Fraction : State::Invalid; break; case State::PointAfterInteger: case State::Fraction: if (digit) { state = State::Fraction; } else if (isExponent(ch)) { state = State::Exponent; } else { state = State::Invalid; } break; case State::Exponent: if (digit) { state = State::ExponentInteger; } else if (isSign(ch)) { state = State::ExponentSign; } else { state = State::Invalid; } break; case State::ExponentSign: case State::ExponentInteger: state = digit ? State::ExponentInteger : State::Invalid; break; case State::Invalid: return false; } if (state == State::Invalid) { return false; } } return state == State::Integer || state == State::PointAfterInteger || state == State::Fraction || state == State::ExponentInteger; } bool witnessScan(const std::string& s) { bool seenDigit = false; bool seenDot = false; bool seenExponent = false; bool digitAfterExponent = true; for (int index = 0; index < static_cast(s.size()); ++index) { const char ch = s[index]; if (isDigit(ch)) { seenDigit = true; if (seenExponent) { digitAfterExponent = true; } } else if (isSign(ch)) { const bool atStart = index == 0; const bool afterExponent = index > 0 && isExponent(s[index - 1]); if (!atStart && !afterExponent) { return false; } } else if (ch == '.') { if (seenDot || seenExponent) { return false; } seenDot = true; } else if (isExponent(ch)) { if (seenExponent || !seenDigit) { return false; } seenExponent = true; digitAfterExponent = false; } else { return false; } } return seenDigit && digitAfterExponent; } public: bool isNumber(std::string s) { return witnessScan(s); } }; 题解 ---- 语法边界 ~~~~~~~~ 直接调用浮点解析库并不能稳定表达题目语法。通用库可能接受空格、特殊值、十六进制格式或区域化写法,而本题 只允许十进制底数和可选指数。任务也只要求验证字符结构,不需要生成实际浮点值。 合法形式可以压缩为: .. code-block:: text [sign] (digits [.] [digits] | . digits) [e/E [sign] digits] 底数必须至少出现一个数字。指数部分若存在,指数标记前必须已经形成合法底数,标记后必须形成一个完整整数。 分段解析 ~~~~~~~~ ``grammarParser`` 直接按照语法顺序消费字符串: #. 读取可选的底数符号; #. 读取小数点前的数字; #. 若出现小数点,再读取小数点后的数字; #. 确认小数点两侧至少一侧包含数字; #. 若出现指数标记,读取可选符号和至少一个指数数字; #. 确认索引最终恰好到达字符串末尾。 ``parseDigits`` 返回本次是否至少消费了一个数字。底数把点前和点后的两个结果合并,因此同时覆盖整数、普通 小数、前导点小数和尾随点小数。指数只接受 ``parseDigits`` 成功的结果,所以 ``"1e"`` 和 ``"1e+"`` 都会失败。 状态机展开 ~~~~~~~~~~ 有限状态机把上述语法阶段显式列出。``PointWithoutInteger`` 表示小数点前没有数字,此状态必须读取数字才能 继续;``PointAfterInteger`` 表示小数点前已有数字,它本身已经是合法终态。 指数标记进入 ``Exponent`` 后,只能读取符号或数字。符号进入 ``ExponentSign``,随后又必须读取数字才能 到达接受状态 ``ExponentInteger``。因此未完成的符号和指数不会在字符串结束时被误判为合法。 接受状态只有四类: .. code-block:: text Integer PointAfterInteger Fraction ExponentInteger 它们分别对应整数、尾随点小数、含小数位的小数和带完整指数的数字。 见证变量压缩 ~~~~~~~~~~~~ 状态机中的多个阶段可以压缩为四个布尔见证: * ``seenDigit``:扫描前缀中已经出现数字; * ``seenDot``:底数已经出现小数点; * ``seenExponent``:已经进入指数部分; * ``digitAfterExponent``:指数出现后已经读到至少一个数字。 数字为底数或指数建立数字见证。小数点要求此前没有点且尚未进入指数。指数要求此前已有数字且尚未出现指数, 随后把 ``digitAfterExponent`` 重置为假。符号只允许位于字符串开头或紧跟指数标记。 扫描不变量 ~~~~~~~~~~ 处理每个字符后,已扫描前缀若仍合法,就满足以下条件: * 小数点至多一个,并且只属于底数; * 指数标记至多一个,并且它之前已经出现数字; * 每个符号都位于当前数字部分的起始位置; * 若已经进入指数,``digitAfterExponent`` 精确表示指数是否已经完整。 这些条件只依赖当前字符、前一个字符和四个累计见证,所以无需回溯。任一字符违反条件时可以立即返回 ``false``。 状态演化 ~~~~~~~~ 以 ``"-3.5E+2"`` 为例: .. list-table:: :header-rows: 1 * - 字符 - 状态变化 - 含义 * - ``-`` - 位于下标 0 - 合法底数符号 * - ``3`` - ``seenDigit = true`` - 底数已有数字 * - ``.`` - ``seenDot = true`` - 进入小数部分 * - ``5`` - 数字见证保持 - 底数为 ``-3.5`` * - ``E`` - ``seenExponent = true`` - ``digitAfterExponent = false`` * - ``+`` - 紧跟指数标记 - 合法指数符号 * - ``2`` - ``digitAfterExponent = true`` - 指数完整,最终接受 若字符串停在 ``E`` 或 ``E+``,``digitAfterExponent`` 会保持为假,最终检查便会拒绝这个未完成前缀。 方法关系 ~~~~~~~~ 分段解析最接近文法定义,状态机最适合完整展示所有合法阶段,见证扫描则把等价阶段合并成最少状态。三种方法 都检查完整字符串,公开入口调用 ``witnessScan``,因为它在保持语义清晰的同时只需一次线性扫描。 边界处理 ~~~~~~~~ * ``"."`` 和 ``"+."`` 没有任何数字,最终由 ``seenDigit`` 拒绝; * ``".8"`` 在点后建立数字见证,合法; * ``"7."`` 在点前已有数字,合法; * ``"e9"`` 在指数前没有数字,立即失败; * ``"1e-"`` 缺少指数数字,最终由 ``digitAfterExponent`` 拒绝; * ``"1e2.3"`` 在指数中出现小数点,由 ``seenExponent`` 拒绝; * ``"--6"`` 的第二个符号既不在开头也不跟随指数,立即失败。 复杂度分析 ~~~~~~~~~~ 三种方法都只对长度为 ``n`` 的字符串进行常数遍扫描,时间复杂度为 ``O(n)``。它们只维护固定数量的索引、 状态或布尔变量,额外空间复杂度为 ``O(1)``。