Java 应用：自制高精度计算器（1）

作者: MiZhou | 来源:发表于2017-08-29 20:08 被阅读59次

一直以来，我的计算器都是 Python 的 REPL（Java8 之后偶尔也用 jjs (Nashorn)）。但是这些 REPL 的问题在于，在涉及到小数时，它们使用的是浮点数进行运算，于是不可避免的出现了浮点数精度缺失的问题：

浮点数精度缺失问题

这个问题，忍得太久，今天又遇到了 —— 所以才会有这样一个想法：自己做一个命令行下的计算器，使用高精度数来代替浮点数进行运算，从而解决掉浮点数精度缺失的问题。

要做一个计算器，首先需要能对一个输入的表达式进行解析，获得这个表达式中包含的所有标识（Token）：比如数，运算符，括号等，当然最好还能够自定义函数，比如 log，pow，sin 等。（在编译原理中，这个过程叫词法分析）

所以，我们先来定义表示这些 Token 的类。首先定义数、运算符、括号、函数这些 Token 的接口，就命名为 Token：

public interface Token {

    public TokenType getType();

    public String text();

    public boolean isNumber();

    public boolean isOperator();

    public boolean isBracket();

    public boolean isFunction();
    
}

getType() 方法用来返回一个 TokenType 类型，TokenType 是一个枚举，它包括了以下四个种类：

public enum TokenType {

    /**
     * 数
     */
    NUMBER,
    /**
     * 运算符
     */
    OPERATOR,
    /**
     * 括号
     */
    BRACKET,
    /**
     * 函数
     */
    FUNCTION
}

为了避免 Token 的每个实现类都需要实现 Token 的每一个方法，我们先定义一个 AbstractToken 类，对每个 isXXX 方法都进行实现 —— 通过 getType 方法来判断是否是该 Token 对应的 TokenType。然后让 Token 的真正实现类去覆写 getType 方法，并返回其对应的 TokenType。比如对于数，那么 getType 返回 TokenType.NUMBER，那么在该类上调用 isNumber 方法，便会返回 true，而其他 isXXX 方法都会返回 false。

public abstract class AbstractToken implements Token {

    @Override
    public boolean isNumber() {
        return getType() == TokenType.NUMBER;
    }

    @Override
    public boolean isOperator() {
        return getType() == TokenType.OPERATOR;
    }

    @Override
    public boolean isBracket() {
        return getType() == TokenType.BRACKET;
    }

    @Override
    public boolean isFunction() {
        return getType() == TokenType.FUNCTION;
    }

}

然后按照每种 Token 的需求挨个实现 Token 接口。因为 Java 中已经存在了一个 Number 类，而且位于 java.lang 包下，所以为了避免混淆，我将数类的名称定义为 Num。

public class Num extends AbstractToken implements Token {

    private final BigDecimal value;

    public Num(BigDecimal value) {
        this.value = value;
    }

    public Num(String value) {
        this.value = new BigDecimal(value);
    }

    public BigDecimal value() {
        return value;
    }

    @Override
    public TokenType getType() {
        return TokenType.NUMBER;
    }

    @Override
    public String text() {
        return String.valueOf(value);
    }

}

因为我们要使用高精度数来代替浮点数，所以 Num 的真正实现，交给了 BigDecimal。

运算符 类：

public class Operator extends AbstractToken implements Token {

    private final char value;

    public Operator(char value) {
        if (value == '+' || value == '-' || value == '*' || value == '/') {
            this.value = value;
        } else {
            throw new RuntimeException(String.format("未知的运算符：%c", value));
        }
    }

    /**
     * 获得运算符的优先级
     *
     * @return 运算符的优先级
     */
    public int property() {
        switch (value) {
            case '*':
            case '/':
                return 1;
            default:
                return 0;
        }
    }

    /**
     * 该运算符的优先级是否大于所给的运算符的优先级
     *
     * @param other 所给的运算符
     * @return 如果该运算符的优先级是否大于所给的运算符的优先级，返回 true，否则返回 false
     */
    public boolean isHigherThan(Operator other) {
        return this.property() > other.property();
    }

    @Override
    public TokenType getType() {
        return TokenType.OPERATOR;
    }

    @Override
    public String text() {
        return String.valueOf(value);
    }

}

运算符 应该具有优先级，所以我们定义了 isHigherThan(Operator other) 方法来判断当前运算符对象（this）的优先级是否大于给定运算符对象（other）。

括号类：

public class Bracket extends AbstractToken implements Token {

    public static final char CHAR_LEFT_BRACKET = '(';
    public static final char CHAR_RIGHT_BRACKET = ')';

    private final char value;

    public Bracket(char value) {
        if (value == CHAR_LEFT_BRACKET || value == CHAR_RIGHT_BRACKET) {
            this.value = value;
        } else {
            throw new RuntimeException("未知的括号字符：" + value);
        }
    }

    public boolean isLeft() {
        return value == CHAR_LEFT_BRACKET;
    }

    public boolean isRight() {
        return value == CHAR_RIGHT_BRACKET;
    }

    @Override
    public TokenType getType() {
        return TokenType.BRACKET;
    }

    @Override
    public String text() {
        return String.valueOf(value);
    }

}

括号类定义了 isLeft 和 isRight 方法，分别用来判断该括号是左括号还是右括号。

而函数类的定义比上面这些更加复杂一些，我们稍后再给出。

Token 的类都定义完毕之后，我们便可以开始实现表达式的解析了 —— 即将一个表达式转换为多个 Token。此时，我们需要定义能够匹配各种 Token 的正则表达式。

我们先来看数对应的正则。数包括整数和小数，整数的正则：\d+，\d 表示匹配数字，+ 表示至少需要一位数字；小数的正则：\d*\.\d+，\d* 表示小数点前面可以有 0 个或者或多个数字，即 12.3 和 .3 都表示一个小数，而 .3 在一般的编程语言中都默认为 0.3。所以匹配数字的正则为 \d*\.\d+|\d+（请大家思考下为什么要将小数的正则放到前面）。
然后，操作符 对应的正则。我们的操作符包括了 +、-、*、/，所以对应的正则为 \+|-|\*|/ （ + 和 * 需要转义）。
括号的正则：\(|\) —— 括号也需要转义。
最后是函数的正则。我们通常使用计算器的函数都是形如 function_name(param1, param2) 这样的形式，所以我们定义函数的正则为 [A-Za-z]+\(.*\) —— .* 表示参数可以有也可以没有，即存在 function_name() 这样的函数。

所以给出匹配 Token 的正则表达式为：(\d*\.\d+|\d+)|(\+|-|\*|/)|(\(|\))|[A-Za-z]+\(.*\) —— 为了解析时将 Token 进行区分，我们将每种 Token 的正则都用括号包括，这样的话每种 Token 在正则做提取时就会作为不同的 group，从而在提取时每种 Token 可以被区分。
因为输入表达式的时候， Token 之间难免会存在空格，所以我们需要加入对空格的处理 —— \s* 表示匹配一个或者多个空格 —— 加入空格处理后的正则表达式变为：\s*((\d*\.\d+|\d+)|(\+|-|\*|/)|(\(|\))|[A-Za-z]+\(.*\))\s*，即 \s*(Token 的正则)\s*。

此时我们可以给出 Token 中函数类的定义：

public class Function extends AbstractToken implements Token {

    private static final Num[] PARAMS_NONE = new Num[0];

    private final String name;  // 名字
    private final Num[] params; // 参数

    public Function(String content) {
        int indexOfLeftBracket = content.indexOf('(');
        int indexOfRightBracket = content.lastIndexOf(')');

        name = content.substring(0, indexOfLeftBracket);

        String paramsContent = content.substring(
                indexOfLeftBracket + 1, indexOfRightBracket);

        // 提取出各个参数
        String[] paramStrs = paramsContent.split(",");
        if (paramStrs.length == 1 && paramStrs[0].isEmpty()) { // 没有参数
            params = PARAMS_NONE;
            
        } else { // 有参数
            params = new Num[paramStrs.length];

            for (int i = 0; i < params.length; i++) {
                String paramStr = paramStrs[i].trim();
                params[i] = new Num(paramStr);
            }
        }
    }

    /**
     * 获得函数的结果
     *
     * @return 函数的结果
     */
    public Num getResult() {
        Func function = FuncFactory.getFunc(name);

        if (function != null) {
            return function.apply(params);
        }

        throw new RuntimeException("未知的函数：" + name);
    }

    @Override
    public TokenType getType() {
        return TokenType.FUNCTION;
    }

    @Override
    public String text() {
        StringBuilder function = new StringBuilder();

        function.append(name).append('(');
        for (Num param : params) {
            function.append(param.text()).append(", ");
        }
        function.delete(function.length() - 2, function.length());
        function.append(')');

        return function.toString();
    }

}

可以看到 Function 类中定义了 getResult 方法 —— 用来获得函数的结果。该方法首先调用 FuncFactory 的 getFunc 方法，通过函数名获得一个 Func，然后 Func 的 apply 方法可以根据参数求得函数的值。具体代码就是我将 Func 定义为接口：

public interface Func {

    public Num apply(Num[] params);
    
}

然后通过 FuncFactory 的 getFunc 方法返回不同的 Func 的实现：

public class FuncFactory {

    public static Func getFunc(String name) {
        switch (name.toLowerCase()) {
            case "log":
                return new LogFunc();
            case "pow":
                return new PowFunc();
            case "pi":
                return new PIFunc();
        }

        return null;
    }
}

这样一来，每次添加一个函数，只需要写一个对应的 Func 接口的实现，然后将其名称加入到FuncFactory 中就行 —— 使用的是 简单工厂模式。

正则定义完毕之后，便可以使用该正则来解析表达式，我们定义一个表达式类 Expression：

public class Expression {

    private static final String REG_EXPR = "\\s*((\\d*\\.\\d+|\\d+)|(\\+|-|\\*|/)|(\\(|\\))|([A-Za-z]+\\(.*\\)))\\s*";
    private static final Pattern PATTERN = Pattern.compile(REG_EXPR);

    private final List<Token> tokens; // 该表达式中的所有 Token

    public Expression(List<Token> tokens) {
        this.tokens = tokens;
    }

    public Expression(String expr) {
        this.tokens = parseTokens(expr);
    }
    
    ...
}

（因为在 Java 中，\ 在字符串中需要用 \\ 表示，所以 REG_EXPR 代表的正则都使用了 \\ 来表示 \）

现在，我们需要一个方法，这个方法可以将字符串形式的表达式，解析为多个 Token，我们定义这个方法为 parseTokens：

private List<Token> parseTokens(String expr) {
    List<Token> ts = new ArrayList<>();

    Matcher matcher = PATTERN.matcher(expr);
    int start = 0, end = expr.length();

    while (start < end) {
        // 设定正则的查找范围在 [start, end)，不包括 end
        matcher.region(start, end);

        // lookingAt() 方法会从 start 位置开始匹配下一个满足正则的子串
        // 我也不知道当年 Java 的开发人员为什么会取 lookingAt 这么鬼畜的名字
        if (matcher.lookingAt()) { //  如果找到了一个匹配正则的子串
            Token token = getToken(matcher);
            ts.add(token);

            start = matcher.end(); // end() 方法会返回上一次匹配的子串的末尾的位置

        } else { // 没有找到匹配正则的子串，说明表达式包含了非正则中定义的文本
            String errorExpr = expr.substring(start);
            throw new RuntimeException("错误的表达式：" + errorExpr);
        }
    }

    return ts;
}

private Token getToken(Matcher matcher) {
    // matcher.group(1) 匹配最外层的括号（matcher.group(0) 是匹配整个正则）
    String m = matcher.group(1);

    if (m != null) { 
        if (matcher.group(2) != null) { // 数
            return new Num(matcher.group(2));

        } else if (matcher.group(3) != null) { // 运算符
            char operatorValue = matcher.group(3).charAt(0);
            return new Operator(operatorValue);

        } else if (matcher.group(4) != null) { // 括号
            char bracketValue = matcher.group(4).charAt(0);
            return new Bracket(bracketValue);

        } else { // 函数
            Function function = new Function(matcher.group(5));
            Num num = function.getResult();

            return num;
        }
    }

    throw new RuntimeException("getToken"); // 正则无误的情况下不会发生
}

parseTokens 方法的过程就是使用 Matcher 类扫描表达式（输入的字符串），每次提取出一个 Token，并加入到集合中，直到扫描完毕。getToken 方法中，对于函数，我们先求出函数的结果（Num），然后便可以直接将其作为一个 Token。

我们顺便覆写下 Expression 的 toString 方法，然后对 Expression 写几个示例测试一下。为了方便展示此处直接使用 main 方法，不使用 JUnit 这样的工具：

@Override
public String toString() {
    StringBuilder expr = new StringBuilder();

    for (Token token : tokens) {
        expr.append(token.text()).append(' ');
    }
    expr.deleteCharAt(expr.length() - 1);

    return expr.toString();
}

main 函数：

public static void main(String[] args) throws Exception {
    Expression expr = new Expression("1+2*3");
    System.out.println(expr);

    expr = new Expression("(1+2) * 3");
    System.out.println(expr);

    expr = new Expression("0.65- 0.56");
    System.out.println(expr);

    expr = new Expression("6 # 8");
}

运行结果：

解析表达式的运行结果

可见我们已经能够成功的解析表达式，并将其转化为多个 Token —— 下一篇文章将讲解如何计算表达式的值（完整的源码在 GitHub）。

Java 应用：自制高精度计算器（1）

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读