跳至主要內容

20-表示数值的字符串

daipeng大约 11 分钟

在《剑指offer-纪念版》中，该题的题目是:

请实现一个函数用来判断字符串是否表示数值（包括小数和整数）。

部分数值列举如下：

["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"] 部分非数值列举如下：

["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

但这个题目说的很不清楚，leetcode上的题干则很详细。

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

  1. 若干空格

  2. 一个 小数 或者 整数

  3. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

  4. 若干空格

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 下述格式之一：
    1. 至少一位数字，后面跟着一个点 '.'
    2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
    3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 至少一位数字

部分数值列举如下： ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"] 部分非数值列举如下： ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

该题有几种解法。

比较笨的方法

第一版

我首先想到的就是比较笨的方法，因为这道题看着不用回溯啥的，我努努力应该可以写出来。大概写了半小时，反复的debug了几次，终于ac了。

思路就是大量的if-else，根据上面的顺序进行探测。

  1. 首先对字符串进行trim操作，去掉前后的空格，如果操作完后字符串为空了，说明是空串，不是数值。
  2. 继续探测是不是小数，如果是小数，需要继续探测是不是指数。如果不是小数，则探测是不是整数。
  3. 探测指数时要继续探测是否是整数。

探测整数的方法：

  1. 如果第一个字符是符号，则跳过。
  2. 跳过所有的数字
  3. 最后返回是否是数字以及探索的索引位置。

探测小数的方法：

  1. 如果第一个字符是符号，则跳过
  2. 如果当前字符是小数点，则跳过后面的所有的数字；如果当前字符是数字，那么需要在后续探测中判断是否有小数点。
  3. 除了上面两种情况，都不是小数。

代码非常长，如下。

 public boolean isNumber(String s) {
        if (s == null) {
            return false;
        }
        char[] chs = s.toCharArray();
        int[] range = trim(chs); //这里也可以直接使用string自带的trim方法。
        if (range[0] > range[1]) {//空串说明不是数值
            return false;
        }
        int begin = range[0];
        int end = range[1];
        int[] result = composeDecimal(chs, begin, end);//判断是否可以组成小数
        if (result[0] == 0) {
            result = composeInt(chs, begin, end); //如果不能组成小数，尝试组成整数
        }
        if (result[0] == 0) {
            return false;
        }
        int next = result[1] + 1;
        if (next > end) {
            return true;
        }
        if (chs[next] == 'E' || chs[next] == 'e') {
            next += 1;
            if (next > end) {
                return false;
            }
            result = composeInt(chs, next, end);
            if (result[1] < end) {
                return false;
            }
            return result[0] == 1;

        }else{
            return false;
        }
    }

    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }



    private int[] composeInt(char[] chs,int begin,int end) {
        int[] result = new int[]{0,-2};
        if(chs[begin] == '+' || chs[begin] == '-'){
            begin = begin + 1;
        }
        for (int i = begin; i <= end ; i++) {
            char ch = chs[i];
            if (!isDigit(ch)) {
                result[1] = i - 1;
                break;
            }
        }
        if (result[1] == -2) {
            result[1] = end;
        }
        if (result[1] < begin) {
            result[0] = 0;
        }else{
            result[0] = 1;
        }
        return result;

    }

    private int[] composeDecimal(char[] chs,int begin,int end) {
        int[] result = new int[]{0,-2};
        if(chs[begin] == '+' || chs[begin] == '-'){
            begin = begin + 1;
        }
        char beginChar = chs[begin];
        if(beginChar == '.'){
            begin = begin + 1;
            for (int i = begin; i <= end ; i++) {
                char ch = chs[i];
                if (!isDigit(ch)) {
                    result[1] = i - 1;
                    break;
                }
            }
            if (result[1] == -2) {
                result[1] = end;
            }
            if (result[1] < begin) {
                result[0] = 0;
            }else{
                result[0] = 1;
            }
        } else if (isDigit(beginChar)) {
             boolean hasDot = false;
            for (int i = begin; i <= end; i++) {
                char ch = chs[i];
                if (isDigit(ch)) {

                }else if(ch == '.'){
                    if (hasDot == false) {
                        hasDot = true;

                    }else{
                        result[1] = i - 1;
                        break;
                    }
                }else{
                    result[1] = i - 1;
                    break;
                }
            }
            if (result[1] == -2) {
                result[1] = end;
            }
            if (result[1] < begin) {
                result[0] = 0;
            }else{
                result[0] = 1;
            }
        }else{
            result[0] = 0;
        }
        return result;
    }

    private int[] trim(char[] chs) {
        int[] range = new int[]{chs.length, -1};
        for (int i = 0; i < chs.length; i++) {
            char ch = chs[i];
            if (ch != ' ') {
                range[0] = i;
                break;
            }
        }
        for (int i = chs.length - 1; i >= 0 ; i--) {
            char ch = chs[i];
            if(ch != ' '){
                range[1] = i;
                break;
            }
        }
        return range;
    }

上面代码可优化的地方非常多。

  1. trim使用库函数
  2. 探测小数实际可以探测整数，这两个方法功能有点重复
  3. java对于int参数只有传值引用，可以将当前访问索引放到对象里，通过传递对象引用进而改变索引。

优化的时候，参考了书上的代码，发现纪念版本里的代码有问题。

#include <iostream>
#include <stdio.h>


void scanDigits(char** string){
    while (**string != '\0' && **string >= '0' && **string <= '9') {
        ++(*string);
    }
}
bool isExponential(char** string){
    if (**string != 'E' && **string != 'e') {
        return false;
    }
    ++(*string);
    if (**string == '+' || **string == '-') {
        ++(*string);
    }
    if (**string == '\0') {
        return false;
    }
    scanDigits(string);
    return (**string == '\0') ? true : false;
}

bool isNumeric(char* string)
{
    if(string == NULL) {
        return false;
    }
    if (*string == '+' || *string == '-') {
        ++string;
    }
    if(*string == '\0') {
        return false;
    }
    bool numeric = true;
    scanDigits(&string);
    if(*string != '\0'){
        if (*string == '.') {
            ++string;
            scanDigits(&string);
            if (*string == 'e' || *string == 'E') {
                numeric = isExponential(&string);
            }
        }else if(*string == 'e' || *string == 'E'){
            numeric = isExponential(&string);
        } else{
            numeric = false;
        }
    }
    return numeric && *string == '\0';

}

void Test( char* testName,  char* str, bool expected)
{
    if(testName != nullptr)
        printf("%s begins: ", testName);

    if(isNumeric(str) == expected)
        printf("Passed.\n");
    else
        printf("FAILED.\n");
}


int main(int argc, char* argv[])
{
    Test("Test1", "100", true);
    Test("Test2", "123.45e+6", true);
    Test("Test3", "+500", true);
    Test("Test4", "5e2", true);
    Test("Test5", "3.1416", true);
    Test("Test6", "600.", true);
    Test("Test7", "-.123", true);
    Test("Test8", "-1E-16", true);
    Test("Test9", "1.79769313486232E+308", true);

    printf("\n\n");

    Test("Test10", "12e", false);
    Test("Test11", "1a3.14", false);
    Test("Test12", "1+23", false);
    Test("Test13", "1.2.3", false);
    Test("Test14", "+-5", false);
    Test("Test15", "12e+5.4", false);
    Test("Test16", ".", false);
    Test("Test17", ".e1", false);
    Test("Test18", "e1", false);
    Test("Test19", "+.", false);
    Test("Test20", "", false);
    Test("Test21", nullptr, false);

    return 0;
}

对于 .e1 e1 +.这三种情况都会判断失败，于是找了下最新的代码如下。

#include <stdio.h>

bool scanUnsignedInteger(const char** str);
bool scanInteger(const char** str);

// 数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，其中A和C都是
// 整数（可以有正负号，也可以没有），而B是一个无符号整数
bool isNumeric(const char* str)
{
    if(str == nullptr)
        return false;

    bool numeric = scanInteger(&str);
    printf("main str %s \n", str);

    // 如果出现'.'，接下来是数字的小数部分
    if(*str == '.')
    {
        ++str;

        // 下面一行代码用||的原因：
        // 1. 小数可以没有整数部分，例如.123等于0.123；
        // 2. 小数点后面可以没有数字，例如233.等于233.0；
        // 3. 当然小数点前面和后面可以有数字，例如233.666
        numeric = scanUnsignedInteger(&str) || numeric;
    }

    // 如果出现'e'或者'E'，接下来跟着的是数字的指数部分
    if(*str == 'e' || *str == 'E')
    {
        ++str;

        // 下面一行代码用&&的原因：
        // 1. 当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
        // 2. 当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4
        numeric = numeric && scanInteger(&str);
    }

    return numeric && *str == '\0';
}

bool scanUnsignedInteger(const char** str)
{
    const char* before = *str;
    while(**str != '\0' && **str >= '0' && **str <= '9')
        ++(*str);

    // 当str中存在若干0-9的数字时，返回true
    printf("scanUnsignedInteger str %s \n", *str);
    return *str > before;
}

// 整数的格式可以用[+|-]B表示, 其中B为无符号整数
bool scanInteger(const char** str)
{
    if(**str == '+' || **str == '-')
        ++(*str);
    return scanUnsignedInteger(str);
}

// ====================测试代码====================
void Test(const char* testName, const char* str, bool expected)
{
    if(testName != nullptr)
        printf("%s begins: ", testName);

    if(isNumeric(str) == expected)
        printf("Passed.\n");
    else
        printf("FAILED.\n");
}


int main(int argc, char* argv[])
{
    Test("Test1", "100", true);
//    Test("Test2", "123.45e+6", true);
//    Test("Test3", "+500", true);
//    Test("Test4", "5e2", true);
//    Test("Test5", "3.1416", true);
//    Test("Test6", "600.", true);
//    Test("Test7", "-.123", true);
//    Test("Test8", "-1E-16", true);
//    Test("Test9", "1.79769313486232E+308", true);
//
//    printf("\n\n");
//
//    Test("Test10", "12e", false);
//    Test("Test11", "1a3.14", false);
//    Test("Test12", "1+23", false);
//    Test("Test13", "1.2.3", false);
//    Test("Test14", "+-5", false);
//    Test("Test15", "12e+5.4", false);
//    Test("Test16", ".", false);
//    Test("Test17", ".e1", false);
//    Test("Test18", "e1", false);
//    Test("Test19", "+.", false);
//    Test("Test20", "", false);
//    Test("Test21", nullptr, false);

    return 0;
}

这个代码是正确的。

因为c++字符串是以'\0'作为结束的，访问时不会越界，字符串的长度也不包括这个结束符，所以c++代码没问题，在java代码里，我增加了一个'?'作为哨兵，可以避免非常多的越界判断。

第二版本

 private static class IndexHolder{
        public int index;
    }
   private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }

    public boolean isNumber(String s) {
        if (s == null) {
            return false;
        }
        s = s.trim();
        if (s.length() == 0) {
            return false;
        }
        System.err.print(s + " ");
        s += "?"; //增加一个哨兵
        char[] chs = s.toCharArray();
        IndexHolder ih = new IndexHolder();
        boolean numeric = composeInt(chs, ih); //这里先尝试获取是否有整数，numeric表示截止到目前是否是数值
        if (chs[ih.index] == '.') { //假如当前索引是小数点，则探测小数。注意，这里ih.index最多指向哨兵?，所以不会越界
            ih.index++;
            //这里注意，下面三种情况都是合法的
            // 当composeUnsignedInt==true numeric==false时 代表 .1这种情况
            // 当composeUnsignedInt==false numeric==true时 代表 1.这种情况
          // 当composeUnsignedInt==true numeric==true时 代表 1.1这种情况
            numeric = composeUnsignedInt(chs, ih) || numeric;
        }
        //执行到这里后，ih.index最多指向?，依然不会越界
        if(chs[ih.index] == 'E' || chs[ih.index] == 'e') {
            ih.index++;
            //这里，E/e后必须有整数(带符号或者不带符号均可)
            numeric = numeric && composeInt(chs, ih);
        }
        return numeric && ih.index == chs.length - 1;//最后，注意ih.index到达?处说明字符串匹配完成

    }
    private boolean composeInt(char[] chs,IndexHolder ih) {
        char beginChar = chs[ih.index];
        if(beginChar == '+' || beginChar == '-'){
            ih.index++;
        }
        return composeUnsignedInt(chs, ih);
    }

    private boolean composeUnsignedInt(char[] chs,IndexHolder ih) {
        int startPos = ih.index;
        while(ih.index != chs.length && isDigit(chs[ih.index])){
            ih.index++;
        }
        return ih.index > startPos;
    }

有限状态机

详细的题解见这里open in new window。

有限状态自动机，是指包含多种状态，状态之间通过动作进行转换，有一个特殊的状态为初始状态，还有一些接受状态，还可能会有一些中间状态等等。

刚开始，自动机处于初始状态，随后开始读取输入序列中的字符，根据当前状态和输入字符以及转移规则从当前状态转移到下一个状态。

一般动作是一个输入序列中的元素，元素可以根据情况进行分类。

如何找到合适的状态是关键。我的经验是状态是整个合法输入序列中的一个可重复使用的组件，比如整数、小数等，同时不要当前状态和输入动作在同一个转移规则下可以到达两个状态。

代码如下。

private Map[] transfer = new Map[]{
            new HashMap(){{put('s', 0);put('p', 4);put('a', 1);put('d', 2);}},//0 开头空格
            new HashMap(){{put('d', 2);put('p', 4);}},//1 E前符号位
            new HashMap(){{put('d', 2);put('s', 9);put('e', 6);put('p', 3);}},//2 E前整数
            new HashMap(){{put('s', 9);put('d', 5);put('e', 6);}},//3 小数点(左侧有数字)
            new HashMap(){{put('d', 5);}},//4 小数点(左侧无数字)
            new HashMap(){{put('e', 6);put('s', 9);put('d', 5);}},//5 小数点后的整数
            new HashMap(){{put('a', 7);put('d', 8);}},//6 e/E
            new HashMap(){{put('d', 8);}},//7 E后符号位
            new HashMap(){{put('d', 8);put('s', 9);}},//8 E后整数
            new HashMap(){{put('s', 9);}}//9 结束空格
            };


    private char charType(char ch) {
        if (ch == ' ') {
            return 's';
        } else if (ch == 'E' || ch == 'e') {
            return 'e';
        } else if (ch >= '0' && ch <= '9') {
            return 'd';
        } else if (ch == '+' || ch == '-') {
            return 'a';
        } else if (ch == '.') {
            return 'p';
        }else{
            return '?';
        }
    }

    public boolean isNumber(String s) {
        if (s == null) {
            return false;
        }
        System.err.print(s + " ");
        char[] chs = s.toCharArray();
        int state = 0;
        for (char ch : chs) {
            char charType = charType(ch);
            Object nextState = transfer[state].get(charType);
            if (nextState == null) {
                return false;
            }
            state = (Integer) nextState;
        }
        return state == 2 || state == 3 || state == 5 || state == 8 || state == 9;
    }

小试牛刀

正则表达式(a|bb)*，表示字符可以是空串，可以有一个a，可以有成对的b，除此之外都不匹配。

匹配的如

"" abb aabb aaa

不匹配的

ab aba baa

这里的动作就是a b，状态可以分为

  1. 0态 合法的状态 ，也是唯一可接受的状态
  2. 1态 临时的状态，一个b这种情况，ab
  3. 2态 可以判断一定为非法状态，aba这种的

对上图的解释如下：

  1. 0态时，输入a，则依然是态；输入b，则进入一个临时状态，比如ab、b这种情况
  2. 1态时，输入a，则进入2态，表示字符串非法了，一定是aba、ba这种状态；输入b，则进入0态，是abb、bb这种情况。
  3. 2态时，无论输入a或者b都一定是非法的。

代码如下。

 public boolean simpleState(String s) {
        char[] chs = s.toCharArray();
        Map[] transfer = new Map[]{
            new HashMap(){{put('a',0);put('b',1);}}, //0 合法的状态，输入a，则进入0态，输入b则进入1态。
            new HashMap(){{put('a',2);put('b',0);}}, //1 临时状态
            new HashMap(){{put('a',2);put('b',2);}}, //2 非法状态
        };
        System.err.print(s + " ");
        int state = 0;
        for (char ch : chs) {
            Object o = transfer[state].get(ch);
            if (o == null) {
                return false;
            }
            state = (Integer) o;
        }
        return state == 0;
    }