欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer--字符串--表示数值的字符串

程序员文章站 2022-07-02 16:05:11
...

                                    表示数值的字符串

题目

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

思路

这道题还是比较简单的。表示数值的字符串遵循如下模式:

[sign]integral-digits[.[fractional-digits]][e|E[sign]exponential-digits]

其中,('['和']'之间的为可有可无的部分)。

在数值之前可能有一个表示正负的'+'或者'-'。接下来是若干个0到9的数位表示数值的整数部分(在某些小数里可能没有数值的整数部分)。如果数值是一个小数,那么在小数后面可能会有若干个0到9的数位表示数值的小数部分。如果数值用科学记数法表示,接下来是一个'e'或者'E',以及紧跟着的一个整数(可以有正负号)表示指数。

判断一个字符串是否符合上述模式时,首先看第一个字符是不是正负号。如果是,在字符串上移动一个字符,继续扫描剩余的字符串中0到9的数位。如果是一个小数,则将遇到小数点。另外,如果是用科学记数法表示的数值,在整数或者小数的后面还有可能遇到'e'或者'E'。

LeetCode

有效数字

验证给定的字符串是否可以解释为十进制数字。

例如:

"0" => true

" 0.1 " => true

"abc" => false

"1 a" => false

"2e10" => true

" -90e3   " => true

" 1e" => false

"e3" => false

" 6e-1" => true

" 99e2.5 " => false

"53.5e93" => true

" --6 " => false

"-+3" => false

"95a54e53" => false

说明: 我们有意将问题陈述地比较模糊。在实现代码之前,你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表:

 

数字 0-9

指数 - "e"

正/负号 - "+"/"-"

小数点 - "."

当然,在输入中,这些字符的上下文也很重要。

代码

1 正则

class Solution {
    public boolean isNumber(String s) {
        boolean flag1=s.matches("(\\s)*[+-]?[0-9]+(\\.[0-9]*)?([eE][+-]?[0-9]+)?(\\s)*");//存在整数部分时,可以没有小数部分
        boolean flag2=s.matches("(\\s)*[+-]?[0-9]*(\\.[0-9]+)([eE][+-]?[0-9]+)?(\\s)*");//可以没有整数部分,此时必须有小数部分
        return flag1 || flag2;
    }
}

2 有限状态机(DFA)1

本题可以采用《编译原理》里面的确定的有限状态机(DFA)解决。构造一个DFA并实现,构造方法可以先写正则表达式,然后转为 DFA,也可以直接写,我就是直接写的,虽然大概率不会是最简结构(具体请参考《编译器原理》图灵出版社),不过不影响解题。DFA 作为确定的有限状态机,比 NFA 更加实用,因为对于每一个状态接收的下一个字符,DFA 能确定唯一一条转换路径,所以使用简单的表驱动的一些方法就可以实现,并且只需要读一遍输入流,比起 NFA 需要回读在速度上会有所提升。

构建出来的状态机如封面图片所示(红色为 终止状态,蓝色为 中间状态)。根据《编译原理》的解释,DFA 从状态 0 接受串 s 作为输入。当s耗尽的时候如果当前状态处于中间状态,则拒绝;如果到达终止状态,则接受。

然后,根据 DFA 列出如下的状态跳转表,之后我们就可以采用 表驱动法 进行编程实现了。需要注意的是,这里面多了一个状态 8,是用于处理串后面的若干个多余空格的。所以,所有的终止态都要跟上一个状态 8。其中,有一些状态标识为-1,是表示遇到了一些意外的字符,可以直接停止后续的计算。状态跳转表如下:

剑指offer--字符串--表示数值的字符串 剑指offer--字符串--表示数值的字符串

class Solution {
    public int make(char c) {
        switch(c) {
            case ' ': return 0;
            case '+':
            case '-': return 1;
            case '.': return 3;
            case 'e': return 4;
            default:
                if(c >= 48 && c <= 57) return 2;
        }
        return -1;
    }
    
    public boolean isNumber(String s) {
        int state = 0;
        int finals = 0b101101000;
        int[][] transfer = new int[][]{{ 0, 1, 6, 2,-1},
                                       {-1,-1, 6, 2,-1},
                                       {-1,-1, 3,-1,-1},
                                       { 8,-1, 3,-1, 4},
                                       {-1, 7, 5,-1,-1},
                                       { 8,-1, 5,-1,-1},
                                       { 8,-1, 6, 3, 4},
                                       {-1,-1, 5,-1,-1},
                                       { 8,-1,-1,-1,-1}};
        char[] ss = s.toCharArray();
        for(int i=0; i < ss.length; ++i) {
            int id = make(ss[i]);
            if (id < 0) return false;
            state = transfer[state][id];
            if (state < 0) return false;
        }
        return (finals & (1 << state)) > 0;
    }
}

3 有限状态机(DFA)2

这种题目,采用的都是有限自动机的方法,要是依靠蛮力直接去写if语句,可能要写的吐血
注意:leetcode这道题有些特殊的case不太容易想到。比如:"3.e10"这个是合法的,但是".e10"是不合法的。另外"3."是合法的。此外,还要最出现在首尾的空格进行剔除。
状态机状态转移图

剑指offer--字符串--表示数值的字符串

剑指offer--字符串--表示数值的字符串

4 直接法

public boolean isNumber(String s) {
        s = s.trim();

        boolean pointSeen = false;
        //前面有没有 .
        boolean eSeen = false;
        //前面有没有E e
        boolean numberSeen = false;
        //前面是否数字
        boolean numberAfterE = true;
        //e不能结尾
        for(int i=0; i<s.length(); i++) {
            if('0' <= s.charAt(i) && s.charAt(i) <= '9') {
                numberSeen = true;
                numberAfterE = true;
            } else if(s.charAt(i) == '.') {
                if(eSeen || pointSeen) {
                    //如果前面存在e或者已经有 .了  ---  报错
                    return false;
                }
                pointSeen = true;
            } else if(s.charAt(i) == 'e') {
                if(eSeen || !numberSeen) {
                    //如果前面已经有e E或者是前面没有数字  ---  报错
                    return false;
                }
                numberAfterE = false;
                eSeen = true;
            } else if(s.charAt(i) == '-' || s.charAt(i) == '+') {
                //如果是 + 或者是 - 的话 它不是第一个或者不是在e 的后面  ---  报错
                if(i != 0 && s.charAt(i-1) != 'e') {
                    return false;
                }
            } else {
                //以上全不是报错
                return false;
            }
        }

        return numberSeen && numberAfterE;
        //*俩是必须的
    }

 5 责任链模式

这里作者提出来,利用责任链的设计模式,会使得写出的算法扩展性以及维护性更高。这里用到的思想就是,每个类只判断一种类型。比如判断是否是正数的类,判断是否是小数的类,判断是否是科学计数法的类,这样每个类只关心自己的部分,出了问题很好排查,而且互不影响。

//每个类都实现这个接口
interface NumberValidate { 
    boolean validate(String s);
}
//定义一个抽象类,用来检查一些基础的操作,是否为空,去掉首尾空格,去掉 +/-
//doValidate 交给子类自己去实现
abstract class  NumberValidateTemplate implements NumberValidate{

    public boolean validate(String s)
    {
        if (checkStringEmpty(s))
        {
            return false;
        }

        s = checkAndProcessHeader(s);

        if (s.length() == 0)
        {
            return false;
        }

        return doValidate(s);
    }

    private boolean checkStringEmpty(String s)
    {
        if (s.equals(""))
        {
            return true;
        }

        return false;
    }

    private String checkAndProcessHeader(String value)
    {
        value = value.trim();

        if (value.startsWith("+") || value.startsWith("-"))
        {
            value = value.substring(1);
        }


        return value;
    }



    protected abstract boolean doValidate(String s);
}

//实现 doValidate 判断是否是整数
class IntegerValidate extends NumberValidateTemplate{

    protected boolean doValidate(String integer)
    {
        for (int i = 0; i < integer.length(); i++)
        {
            if(Character.isDigit(integer.charAt(i)) == false)
            {
                return false;
            }
        }

        return true;
    }
}
 
//实现 doValidate 判断是否是科学计数法
class SienceFormatValidate extends NumberValidateTemplate{

    protected boolean doValidate(String s)
    {
        s = s.toLowerCase();
        int pos = s.indexOf("e");
        if (pos == -1)
        {
            return false;
        }

        if (s.length() == 1)
        {
            return false;
        }

        String first = s.substring(0, pos);
        String second = s.substring(pos+1, s.length());

        if (validatePartBeforeE(first) == false || validatePartAfterE(second) == false)
        {
            return false;
        }


        return true;
    }

    private boolean validatePartBeforeE(String first)
    {
        if (first.equals("") == true)
        {
            return false;
        }

        if (checkHeadAndEndForSpace(first) == false)
        {
            return false;
        }

        NumberValidate integerValidate = new IntegerValidate();
        NumberValidate floatValidate = new FloatValidate();
        if (integerValidate.validate(first) == false && floatValidate.validate(first) == false)
        {
            return false;
        }

        return true;
    }

    private boolean checkHeadAndEndForSpace(String part)
    {

        if (part.startsWith(" ") ||
            part.endsWith(" "))
        {
            return false;
        }

        return true;
    }

    private boolean validatePartAfterE(String second)
    {
        if (second.equals("") == true)
        {
            return false;
        }

        if (checkHeadAndEndForSpace(second) == false)
        {
            return false;
        }

        NumberValidate integerValidate = new IntegerValidate();
        if (integerValidate.validate(second) == false)
        {
            return false;
        }

        return true;
    }
}
//实现 doValidate 判断是否是小数
class FloatValidate extends NumberValidateTemplate{

    protected boolean doValidate(String floatVal)
    {
        int pos = floatVal.indexOf(".");
        if (pos == -1)
        {
            return false;
        }

        if (floatVal.length() == 1)
        {
            return false;
        }

        NumberValidate nv = new IntegerValidate();
        String first = floatVal.substring(0, pos);
        String second = floatVal.substring(pos + 1, floatVal.length());

        if (checkFirstPart(first) == true && checkFirstPart(second) == true)
        {
            return true;
        }

        return false;
    }

    private boolean checkFirstPart(String first)
    {
        if (first.equals("") == false && checkPart(first) == false)
        {
            return false;
        }

        return true;
    }

    private boolean checkPart(String part)
    {
        if (Character.isDigit(part.charAt(0)) == false ||
            Character.isDigit(part.charAt(part.length() - 1)) == false)
        {
            return false;
        }

        NumberValidate nv = new IntegerValidate();
        if (nv.validate(part) == false)
        {
            return false;
        }

        return true;
    }
}
//定义一个执行者,我们把之前实现的各个类加到一个数组里,然后依次调用
class NumberValidator implements NumberValidate {

    private ArrayList<NumberValidate> validators = new ArrayList<NumberValidate>();

    public NumberValidator()
    {
        addValidators();
    }

    private  void addValidators()
    {
        NumberValidate nv = new IntegerValidate();
        validators.add(nv);

        nv = new FloatValidate();
        validators.add(nv);

        nv = new HexValidate();
        validators.add(nv);

        nv = new SienceFormatValidate();
        validators.add(nv);
    }

    @Override
    public boolean validate(String s)
    {
        for (NumberValidate nv : validators)
        {
            if (nv.validate(s) == true)
            {
                return true;
            }
        }

        return false;
    }


}
public boolean isNumber(String s) {
    NumberValidate nv = new NumberValidator(); 
    return nv.validate(s);
}