Java 應(yīng)用：自制高精度計算器（1）

Muninn 發(fā)布于2019-08-16 10:42 / 785人閱讀

摘要：一直以來，我的計算器都是的之后偶爾也用。因為我們要使用高精度數(shù)來代替浮點數(shù)，所以的真正實現(xiàn)，交給了。我們通常使用計算器的函數(shù)都是形如這樣的形式，所以我們定義函數(shù)的正則為表示參數(shù)可以有也可以沒有，即存在這樣的函數(shù)。

一直以來，我的計算器都是 Python 的 REPL（Java8 之后偶爾也用 jjs (Nashorn)）。但是這些 REPL 的問題在于，在涉及到小數(shù)時，它們使用的是浮點數(shù)進(jìn)行運算，于是不可避免的出現(xiàn)了浮點數(shù)精度缺失的問題：

這個問題，忍得太久，今天又遇到了 —— 所以才會有這樣一個想法：自己做一個命令行下的計算器，使用高精度數(shù)來代替浮點數(shù)進(jìn)行運算，從而解決掉浮點數(shù)精度缺失的問題。

要做一個計算器，首先需要能對一個輸入的表達(dá)式進(jìn)行解析，獲得這個表達(dá)式中包含的所有標(biāo)識（Token）：比如 數(shù)，運算符，括號等，當(dāng)然最好還能夠自定義函數(shù)，比如 log，pow，sin 等。（在編譯原理中，這個過程叫詞法分析）

所以，我們先來定義表示這些 Token 的類。首先定義 數(shù)、運算符、括號、函數(shù) 這些 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 {

    /**
     * 數(shù)
     */
    NUMBER,
    /**
     * 運算符
     */
    OPERATOR,
    /**
     * 括號
     */
    BRACKET,
    /**
     * 函數(shù)
     */
    FUNCTION
}

為了避免 Token 的每個實現(xiàn)類都需要實現(xiàn) Token 的每一個方法，我們先定義一個 AbstractToken 類，對每個 isXXX 方法都進(jìn)行實現(xiàn) —— 通過 getType 方法來判斷是否是該 Token 對應(yīng)的 TokenType。然后讓 Token 的真正實現(xiàn)類去覆寫 getType 方法，并返回其對應(yīng)的 TokenType。比如對于 數(shù)，那么 getType 返回 TokenType.NUMBER，那么在該類上調(diào)用 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 的需求挨個實現(xiàn) Token 接口。因為 Java 中已經(jīng)存在了一個 Number 類，而且位于 java.lang 包下，所以為了避免混淆，我將 數(shù) 類的名稱定義為 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);
    }

}

因為我們要使用高精度數(shù)來代替浮點數(shù)，所以 Num 的真正實現(xiàn)，交給了 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));
        }
    }

    /**
     * 獲得運算符的優(yōu)先級
     *
     * @return 運算符的優(yōu)先級
     */
    public int property() {
        switch (value) {
            case "*":
            case "/":
                return 1;
            default:
                return 0;
        }
    }

    /**
     * 該運算符的優(yōu)先級是否大于所給的運算符的優(yōu)先級
     *
     * @param other 所給的運算符
     * @return 如果該運算符的優(yōu)先級是否大于所給的運算符的優(yōu)先級，返回 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);
    }

}

運算符 應(yīng)該具有優(yōu)先級，所以我們定義了 isHigherThan(Operator other) 方法來判斷當(dāng)前運算符對象（this）的優(yōu)先級是否大于給定運算符對象（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 方法，分別用來判斷該括號是左括號還是右括號。

而函數(shù)類的定義比上面這些更加復(fù)雜一些，我們稍后再給出。

Token 的類都定義完畢之后，我們便可以開始實現(xiàn)表達(dá)式的解析了 —— 即將一個表達(dá)式轉(zhuǎn)換為多個 Token。此時，我們需要定義能夠匹配各種 Token 的正則表達(dá)式。

我們先來看 數(shù) 對應(yīng)的正則。數(shù) 包括整數(shù)和小數(shù)，整數(shù)的正則：d+，d 表示匹配數(shù)字，+ 表示至少需要一位數(shù)字；小數(shù)的正則：d*.d+，d* 表示小數(shù)點前面可以有 0 個或者或多個數(shù)字，即 12.3 和 .3 都表示一個小數(shù)，而 .3 在一般的編程語言中都默認(rèn)為 0.3。所以匹配數(shù)字的正則為 d*.d+|d+（請大家思考下為什么要將小數(shù)的正則放到前面）。

然后，操作符 對應(yīng)的正則。我們的操作符包括了 +、-、*、/，所以對應(yīng)的正則為 +|-|*|/ （ + 和 * 需要轉(zhuǎn)義）。

括號的正則：(|) —— 括號也需要轉(zhuǎn)義。

最后是 函數(shù) 的正則。我們通常使用計算器的函數(shù)都是形如 function_name(param1, param2) 這樣的形式，所以我們定義函數(shù)的正則為 [A-Za-z]+(.*) —— .* 表示參數(shù)可以有也可以沒有，即存在 function_name() 這樣的函數(shù)。

所以給出匹配 Token 的正則表達(dá)式為：(d*.d+|d+)|(+|-|*|/)|((|))|[A-Za-z]+(.*) —— 為了解析時將 Token 進(jìn)行區(qū)分，我們將每種 Token 的正則都用括號包括，這樣的話每種 Token 在正則做提取時就會作為不同的 group，從而在提取時每種 Token 可以被區(qū)分。
因為輸入表達(dá)式的時候， Token 之間難免會存在空格，所以我們需要加入對空格的處理 —— s* 表示匹配一個或者多個空格 —— 加入空格處理后的正則表達(dá)式變?yōu)椋?b>s*((d*.d+|d+)|(+|-|*|/)|((|))|[A-Za-z]+(.*))s*，即 s*(Token 的正則)s*。

此時我們可以給出 Token 中 函數(shù) 類的定義，與簡寫的 Num 對應(yīng)，將函數(shù)類別的 Token 命名為 Func：

public class Func extends AbstractToken implements Token {

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

    private final String name;  // 名字
    private final Num[] params; // 參數(shù)

    public Func(String content) {
        int indexOfLeftBracket = content.indexOf("(");
        int indexOfRightBracket = content.lastIndexOf(")");

        name = content.substring(0, indexOfLeftBracket);

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

        // 提取出各個參數(shù)
        String[] paramStrs = paramsContent.split(",");
        if (paramStrs.length == 1 && paramStrs[0].isEmpty()) { // 沒有參數(shù)
            params = PARAMS_NONE;

        } else { // 有參數(shù)
            params = new Num[paramStrs.length];

            for (int i = 0; i < params.length; i++) {
                String paramStr = paramStrs[i].trim();
                
                // 如果需要參數(shù)也能是表達(dá)式，修改這個地方
                // 先計算出表達(dá)式的值（Num），然后將其作為參數(shù)
                params[i] = new Num(paramStr); 
            }
        }
    }

    /**
     * 獲得函數(shù)的結(jié)果
     *
     * @return 函數(shù)的結(jié)果
     */
    public Num getResult() {
        Function function = FunctionFactory.getFunction(name);

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

        throw new UnknownFunctionException(name);
    }
}

可以看到 Func 類中定義了 getResult 方法 —— 用來獲得函數(shù)的結(jié)果。該方法首先調(diào)用 FunctionFactory 的 getFunction 方法，通過函數(shù)名獲得一個具體的 Function，然后 Function 的 apply 方法可以根據(jù)參數(shù)求得函數(shù)的值。具體代碼就是我將 Function 定義為接口：

public interface Function {

    public Num apply(Num[] params);
    
}

然后通過 FunctionFactory 的 getFunction 方法返回不同的 Function 的實現(xiàn)：

public final class FunctionFactory {

    public static Function getFunction(String name) {
        Objects.requireNonNull(name);

        name = name.toLowerCase();
        switch (name) {
            case "pi":
                return new PIFunction();
                
            case "log":
                return new LogFunction();
                
            case "pow":
                return new PowFunction();
        }

        return null;
    }
}

這樣一來，每次添加一個 函數(shù)，只需要寫一個對應(yīng)的 Function 接口的實現(xiàn)，然后將其名稱加入到FunctionFactory 中就行 —— 使用的是 簡單工廠模式。

正則定義完畢之后，便可以使用該正則來解析表達(dá)式，我們定義一個表達(dá)式類 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 tokens; // 該表達(dá)式中的所有 Token

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

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

（因為在 Java 中，在字符串中需要用表示，所以 REG_EXPR 代表的正則都使用了來表示）

現(xiàn)在，我們需要一個方法，這個方法可以將字符串形式的表達(dá)式，解析為多個 Token，我們定義這個方法為 parseTokens：

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

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

    while (start < end) {
        // 設(shè)定正則的查找范圍在 [start, end)，不包括 end
        matcher.region(start, end);

        // lookingAt() 方法會從 start 位置開始匹配下一個滿足正則的子串
        // 我也不知道當(dāng)年 Java 的開發(fā)人員為什么會取 lookingAt 這么鬼畜的名字
        if (matcher.lookingAt()) { //  如果找到了一個匹配正則的子串
            Token token = getToken(matcher);
            ts.add(token);

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

        } else { // 沒有找到匹配正則的子串，說明表達(dá)式包含了非正則中定義的文本
            String errorExpr = expr.substring(start);
            throw new RuntimeException("錯誤的表達(dá)式：" + 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) { // 數(shù)
            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 { // 函數(shù)
            Function function = new Function(matcher.group(5));
            Num num = function.getResult();

            return num;
        }
    }

    throw new RuntimeException("Expression.getToken: Unbelievable"); // 正則無誤的情況下不會發(fā)生
}

parseTokens 方法的過程就是使用 Matcher 類掃描表達(dá)式（輸入的字符串），每次提取出一個 Token，并加入到集合中，直到掃描完畢。getToken 方法中，對于函數(shù)，我們先求出函數(shù)的結(jié)果（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 函數(shù)：

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");
}

運行結(jié)果：

可見我們已經(jīng)能夠成功的解析表達(dá)式，并將其轉(zhuǎn)化為多個 Token —— 下一篇文章將講解如何計算表達(dá)式的值（完整的源碼在 GitHub）。