确定一个给定的字符串是否为有效数字的算法

Question

最近遇到了一个有趣的面试问题，类似于LeetCode上的“Valid Number”题目，但有着不同的约束条件。我正面临困难，难以设计出一个能够覆盖所有边缘情况和要求的算法。

问题是这样的：给定一个字符串，编写一个方法，如果该字符串是一个有效的数字则返回true，否则返回false。
只有整数和小数应被视为有效。换句话说，只允许出现的字符是数字、"-" 和 "."。
字符串可能非常长（想象成百万个字符），且不允许使用任何内置函数/类来处理它，以避免溢出或精度丢失。

以下是一些示例字符串及其预期输出：

"13" ---> true
"3.0" ---> true
"-7.4" ---> true
"-13.5" ---> true
"abc" ---> false
"123a" ---> false
"-." ---> false
"1.0.0.1" ---> false
"001" ---> false
".0" ---> false
false
"00.0" ---> false
"0." ---> false

这是我目前的代码实现：

public static boolean isValidNumber(String s) {
    boolean seenDigit = false;
    boolean seenDot = false;

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        if (Character.isDigit(c)) {
            seenDigit = true;
        } else if (c == '.') {
            if (seenDot)
                return false;
            seenDot = true;
        } else if (c == '+' || c == '-') {
            if (i != 0) {
                return false;
            }
        } else {
            return false;
        }
    }

    return seenDigit;
}

然而，我还未能额外覆盖这些边缘情况：

isValidNumber("007") 应为 false
isValidNumber(".0") 应为 false
isValidNumber("000.0") 应为 false
isValidNumber("0.") 应为 false

似乎很难在不将代码变成意大利面条式代码的情况下，设计出一个能覆盖所有这样情况的清晰方法，除非我忽略了某个解决这个问题的优雅思路。

jalf · Answer

错误的是提到没有内置函数或类能够在不溢出或不失精度的情况下处理数百万字符的字符串。实际上，Java中的BigDecimal类就是内置的，并且能够处理数百万字符的数值，不会溢出也不会丢失精度。

因此，一个简单的解决方案可以是：

public static boolean isValidNumber(String s) {
    try {
        new BigDecimal(s);
        return true;
    } catch (NumberFormatException e) {
        return false;
    }
}

不幸的是，这个方法并不完全符合你的规则集。例如，BigDecimal对于前导零（如"007"）没有问题，它等同于7。它还支持科学记数法（如new BigDecimal("1.23456e4")），并且允许有无意义的正号，这并不会产生影响。

你说想要一个“干净”的方法来覆盖所有案例，而又不至于让代码变得复杂。这里的“干净”定义比较主观。题目所给的规则集其实相当随意且不一致，导致问题变得异常复杂。

问题看似简单，是因为这些随意的规则恰巧贴近人类书写十进制数的一般方式，但这让你误以为一定存在一个简单的解决方案。实际上，人类在处理这类事情时是非常随意且复杂的机器。

例如：

为什么禁止前导零？它们同样是十进制数的一部分，代表其所在位置的值为0，这是合理的。
但是当非小数部分不存在时，前导零不仅不禁用，反而强制要求必须有一个0，不多也不少，正好一个。
为什么小数点在没有小数部分时是可选的？
为什么全部由零组成的小数部分被认为是无效的？像"5.00"这样的表示，所有人都明白它的意思，在某些上下文中（比如货币金额），这种表示方式还相当常见！

解决方案

我猜测提问者可能是想引导你构建一个状态机（state machine）解决方案。

状态机逐个遍历输入字符，并根据当前所处的状态以及发现的字符，映射到一个新的状态，用于处理下一个字符。到达末尾时，某些状态被定义为“合法”，其余的则为“非法”。系统必须处于合法状态，才能验证通过输入。

这个过程很复杂，比如：

初始状态为START。
START作为结束状态是非法的。
-意味着进入START2状态。
1-9意味着进入WHOLES状态。
0意味着进入WHOLE_ZERO状态。
其他字符都导向INVALID状态。

START2与START相似，只是再遇到-也是非法的。

然后每个状态根据接收的字符有不同的转移逻辑，直到最终判断是否为合法的结束状态。你还可以进一步细化，比如考虑-0是非法的，但-0.5是合法的情况。

如果你对状态机感兴趣，可以尝试在纸上画出状态图，每个状态用圆圈表示，每种转换用箭头连接，并在边上标注触发转换的字符。

另一种途径

除了状态机，还可以考虑使用正则表达式（Regular Expressions）。Java内置了对正则的支持。虽然这种方法代码量会更少，但可能更难阅读和维护，特别是考虑到边缘情况时。正则表达式的教程在网络上很容易找到。相较于状态机，使用正则表达式更容易遗漏边界情况，且测试失败边缘情况也更为困难。如果你追求逻辑清晰和易于测试，我建议采用状态机方案。

gimel · Answer

在注意到我对问题的评论不够清晰后，我“改进”了你的算法以通过所有测试案例，并简单实现了自动化测试。

代码可能不是最优美，但已满足需求。

更新：

我已经清理了代码：

在循环开始前增加了对+ -仅在首字符出现的检查，因此在循环中不必再做此检查（提高可读性，加速算法）。
移除了重复的1检查，并将其保存为isDigit，用条件赋值(x == y ? : z)替换了if语句，提高了可读性。


添加了关于“接受字符”的注释。
扩展了对第二个算法的测试。



代码如下：

package stackoverflow;

import java.util.ArrayList;

public class NumberChecker {

    static private class Pair {
        public final String     stringToParse;
        public final boolean    expectedResult;
        public Pair(final String pStringToParse, final boolean pExpectedResult) {
            stringToParse = pStringToParse;
            expectedResult = pExpectedResult;
        }
    }

    @FunctionalInterface
    private interface TestCaller {
        boolean run(String pCheckString);
    }

    public static void main(final String... args) {
        final ArrayList tests = new ArrayList<>();
        tests.add(new Pair("13", true));
        tests.add(new Pair("3.0", true));
        tests.add(new Pair("-7.4", true));
        tests.add(new Pair("-13.5", true));
        tests.add(new Pair("abc", false));
        tests.add(new Pair("123a", false));
        tests.add(new Pair("-.", false));
        tests.add(new Pair("1.0.0.1", false));
        tests.add(new Pair("001", false));
        tests.add(new Pair(".0", false));
        tests.add(new Pair("00.0", false));
        tests.add(new Pair("0.", false));
        tests.add(new Pair("10", true));
        tests.add(new Pair("1", true));
        tests.add(new Pair("0.1", true));
        tests.add(new Pair("0.01", true));

        testAlgorithm("Original Algorithm", tests, s -> isValidNumber(s));
        testAlgorithm("Cleaner Algorithm", tests, s -> isValidNumber_cleaner(s));
    }

    static private void testAlgorithm(final String pTestName, final ArrayList pTests, final TestCaller pTestCaller) {
        System.out.println("
Running test: " + pTestName);
        int errors = 0;
        for (final Pair p : pTests) {
            final boolean algResult = pTestCaller.run(p.stringToParse);
            if (algResult != p.expectedResult) {
                System.out.println("WARNING: mismatch to test string [" + p.stringToParse + "]: expected " + p.expectedResult + " but encountered " + algResult);
                ++errors;
            }
        }
        if (errors < 1) System.out.println("All OK!");
        else System.out.println("Still contains errors!");
    }

    public static boolean isValidNumber(final String s) {
        boolean seenDigit = false;
        boolean seenRealDigit = false;
        boolean seenDot = false;

        for (int i = 0; i < s.length(); i++) {
            final char c = s.charAt(i);

            if ((c < '0' || '9' < c) && c != '+' && c != '-' && c != '.') return false;

            if ('1' <= c && c <= '9') seenRealDigit = true;
            if (Character.isDigit(c)) seenDigit = true;
            if (c == '0' && !seenRealDigit && !seenDot && (i < s.length() - 1 && s.charAt(i + 1) != '.')) return false;

            if (c == '.') {
                if (seenDot) return false;
                if (!seenDigit) return false;
                seenDot = true;

            } else if (c == '+' || c == '-') {
                if (i != 0) return false;
            }
        }

        if (!seenRealDigit) return false;
        return seenDigit;
    }

    public static boolean isValidNumber_cleaner(final String s) {
        if (s == null || s.trim().length() < 1) return false;

boolean seenDigit = false;
boolean seenRealDigit = false;
boolean seenDot = false;

int startIndex = 0;
{ // check if string starts with + or -
    final char c = s.charAt(0);
    if (c == '+' || c == '-') startIndex = 1;
}

for (int i = startIndex; i < s.length(); i++) {
    final char c = s.charAt(i);

    final boolean isRealDigit = '1' <= c && c <= '9';
    seenRealDigit |= isRealDigit;

    final boolean isDigit = isRealDigit || c == '0';
    seenDigit |= isDigit;

    // check for invalid char. only accept 0-9 and '.'; Hint: '+' and '-' are now also invalid, because we jumped over them already
    if (!isDigit && c != '.') return false;

    if (c == '0' && !seenRealDigit && !seenDot && (i < s.length() - 1 && s.charAt(i + 1) != '.')) return false;
    else if (c == '.') {
        if (seenDot) return false;
        if (!seenDigit) return false;
        seenDot = true;
    } // else accept(ignore) c, because it MUST be a digit here [ if (!isDigit && c != '.') return; vs NOT (c == '.') ]
}

if (!seenRealDigit) return false;
return seenDigit;
    }
}

Adam Rackis · Answer

手动编写解析代码的两种清晰、常用的方法是实现一个确定性有限自动机(DFA) 或者一个堆栈自动机(PDA)，又或者是采用递归下降解析的方法。

对于像这样的简单任务，使用状态机是一个不错的选择。基于实际工作经验，我有很多次做类似事情的经历，可以提供一些建议：为了让手动编写的状态机代码易于阅读和维护，关键在于定义有意义的状态，这样通过观察就能明白每个状态中应该发生什么。

利用Myhill-Nerode定理来决定你的状态应该是什么，这样每个状态都可以根据它所匹配的内容来命名——易于阅读——并且你会得到尽可能少的状态数。

综合起来，你的代码可能会像下面这样：

// 解析状态。名称即其所匹配的内容（依据Myhill-Nerode）
// 名称为MAYBE_*的状态是有效的终点，且编号为负数
static final int ST_NUMBER = 0;
static final int ST_POSITIVE_NUMBER = 1;
static final int ST_MAYBE_FRACTION = -2;
static final int ST_MAYBE_POSITIVE_OR_FRACTION = -3;
static final int ST_FRACTION_DIGITS = 4;
static final int ST_MAYBE_FRACTION_DIGITS = -5;

public static boolean isValidNumber(final String s) {
    int state = ST_NUMBER;

    for (int i = 0; i < s.length(); i++) {
        final char c = s.charAt(i);
        switch (state) {
            default:
                // 不可能发生的情况
                return false;

            case ST_NUMBER:
                if (c != '-') {
                    --i; // 再次处理这个字符
                }
                state = ST_POSITIVE_NUMBER;
                break;

            // ... 省略了其他case分支以保持简洁 ...

            case ST_FRACTION_DIGITS:
            case ST_MAYBE_FRACTION_DIGITS:
                // 只允许数字
                if (c < '0' || c > '9') {
                    return false;
                }
                state = ST_MAYBE_FRACTION_DIGITS;
                break;
        }
    }
    // 到达字符串末尾。如果我们在一个MAYBE_状态，则为有效
    return state < 0;
}

另外，如评论中所述，递归下降同样也是解决此问题的一个合理方法。那样的话，代码看起来会是这样：

    public static boolean isValidNumber(final String s) {
        return matchNumber(s, 0) == s.length();
    }
    
    private static int matchNumber(String s, int pos) {
        int subPos = matchChar(s, pos, '-');
        if (subPos > pos) {
            pos = subPos;
        }
        pos = matchPositiveInt(s, pos);
        if (pos < 0) {
            return -1;
        }
        subPos = matchChar(s, pos, '.');
        if (subPos > pos) {
            pos = matchDigits(s, subPos);
            if (pos < 0) {
                return -1;
            }
        }
        return pos;
    }
    
    private static int matchPositiveInt(String s, int pos) {
        int subPos = matchChar(s, pos, '0');
        if (subPos > pos) {
            return subPos;
        }
        return matchDigits(s,pos);
    }
    
    private static int matchDigits(String s, int pos) {
        int ret = -1;
        for(;pos < s.length(); ++pos) {
            char c = s.charAt(pos);
            if (c < '0' || c > '9') {
                break;
            }
            ret = pos+1;
        }
        return ret;
    }
    
    private static int matchChar(String s, int pos, char c) {
        if (pos < s.length() && s.charAt(pos) == c) {
            return pos + 1;
        }
        return -1;
    }

jldupont · Answer

在我看来，这是使用Java正则表达式(Patterns)的一个典型场景。通过正则表达式，代码变得简洁且易于阅读，编写和维护起来比手动实现状态机要简便得多。

很可能这个问题的目的在于检验你是否了解正则表达式。虽然使用状态机也可能达到目的，但完全依靠“手动”检查则是最易出错且繁琐的方式。

以下是使用Java正则表达式的示例代码：

private static final Pattern NUMBER_PATTERN = Pattern.compile("-?(?:0|[1-9]\d*)(?:\.\d+)?");
public static boolean isValidNumber(String s) {
    return NUMBER_PATTERN.matcher(s).matches();
}

解释如下：

-?：可选的负号
(?:0|[1-9]\d*)：整数部分。(?:...)是非捕获组，表示“要么是0，要么是一个从1到9的数字后跟任意数量的数字”。这样就不允许前导零。
(?:\.\d+)?：可选的小数部分：一个点后跟一个或多个数字。

关键在于，正则表达式应专注于包含有效输入，而非排除无效输入。

然而，利用诸如否定前瞻（negative lookaheads）这样的特性，你可以更方便地表达对无效输入的排除（尽管这类前瞻操作的性能可能更难分析；在这个特定情况下应该是没问题的）：

private static final Pattern NUMBER_PATTERN = Pattern.compile("-?(?:0|(?!0)\d+)(?:\.\d+)?");

这段代码对于熟悉前瞻语法的读者来说可能更易读：(?!0)有效地表示“整数部分不能以0开头”。仍然需要使用(?:0|...)来明确允许单个零的存在。

这就是全部内容了，仅需几行代码。

性能

一个适当的正则表达式实现会在编译正则表达式时，将其转换为有限状态机，确保线性时间执行。

然而，许多“正则表达式”引擎实际上并未采用这种方法，而是采用了“回溯”机制（部分原因是这支持了更多功能，如反向引用），这可能会导致效率大大降低。由于Java的Pattern类提供了这些功能，我们不得不假设它使用的是回溯型的正则引擎。

但在本例中，这并不构成问题；即使在简单的回溯型正则引擎上，这个模式仍将在线性时间内完成匹配，因为直观来说，引擎遍历字符串时总有一个唯一正确的“选择”。（对于贪婪量词，之后可能需要回溯，尝试匹配更少的项，但这同样在常数步之后停止。）

如ruakh所指出的，你可以使用“占有型”量词（如[1-9]\d*+代替[1-9]\d*），这会避免\d*量词的回溯，虽然不影响整体渐进运行时间（回溯几乎立即失败，因为下一个字符将是数字而不是点），但应该可以略微改善常数因子。对于小数点后的部分，如果你想使用“占有型”量词，则可能需要使用回顾后发（lookbehind），不过这对渐进时间复杂度并无影响。

Karoly Horvath · Answer

一个相当简单的正则表达式就能实现这个需求：

return s.matches("-?((0|[1-9]\d*)(\.\d+)?)");

参见在线演示（注意在线演示中的^和$是为了限定字符串的开始和结束，而在Java中使用matches()方法时，这些是隐含的，因为matches()要求整个字符串都必须匹配正则表达式）。

该正则表达式的含义是：“可选的负号-，接着是一个0或者一个非0数字后可跟任意数量的数字，再接着是可选的小数点.以及一些数字”。