Java 應用：自制高精度計算器（1）

Muninn 發布于2019-08-16 10:42 / 744人閱讀

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

一直以來，我的計算器都是 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 中函數類的定義，與簡寫的 Num 對應，將函數類別的 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; // 參數

    public Func(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();
                
                // 如果需要參數也能是表達式，修改這個地方
                // 先計算出表達式的值（Num），然后將其作為參數
                params[i] = new Num(paramStr); 
            }
        }
    }

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

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

        throw new UnknownFunctionException(name);
    }
}

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

public interface Function {

    public Num apply(Num[] params);
    
}

然后通過 FunctionFactory 的 getFunction 方法返回不同的 Function 的實現：

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

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

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

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

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

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

現在，我們需要一個方法，這個方法可以將字符串形式的表達式，解析為多個 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) {
        // 設定正則的查找范圍在 [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("Expression.getToken: Unbelievable"); // 正則無誤的情況下不會發生
}

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）。

云服務器 GPU云服務器高精度計算 js計算高精度數據 java 高精度取余計算精度

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70274.html

Java 應用：自制高精度計算器（2）

摘要：而對于前綴表達式和后綴表達式的計算，則十分的簡單。由上一篇文章可知，我們目前的類所表示的，就是中綴表達式，所以我們需要提供算法，將中綴表達式轉換為前綴表達式或者后綴表達式，從而方便我們計算表達式的值。上一篇文章講了如何通過正則來將輸入的表達式解析為多個 Token，而這篇文章的核心在于如何對表達式求值。我們輸入的表達式，即我們通常見到的表達式，都是中綴表達式 —— 中綴的含義是，...

yy736044583 2019-08-16 10:41 評論0 收藏0
私有云部署-UCloudStack私有云部署之虛擬機

摘要：虛擬網卡與虛擬機的生命周期一致，無法進行分離，虛擬機被銷毀時，虛擬網卡即被銷毀。每塊虛擬網卡支持綁定一個安全組，提供網卡級別安全控制。平臺默認提供塊虛擬網卡，若業務有塊以上網卡需求可通過綁定彈性網卡，為虛擬機提供多網絡服務。虛擬機是 UCloudStack 云平臺的核心服務，提供可隨時擴展的計算能力服務，包括 CPU 、內存、操作系統等最基礎的計算組件，并與網絡、磁盤等服務結合提供完整的計算...

ernest.wang 2022-06-28 15:56 評論0 收藏0
Java爬蟲之利用Jsoup自制簡單的搜索引擎

摘要：的官方網址為，其使用手冊網址為本次分享將實現的功能為利用爬取某個搜索詞語暫僅限英文的百度百科的介紹部分，具體的功能介紹可以參考博客爬蟲自制簡單的搜索引擎。 ??Jsoup 是一款Java 的HTML解析器，可直接解析某個URL地址、HTML文本內容。它提供了一套非常省力的API，可通過DOM，CSS以及類似于jQuery的操作方法來取出和操作數據。Jsoup的官方網址為： https:...

GHOST_349178 2019-08-15 15:11 評論0 收藏0
Java跨平臺？慎用這些有平臺差異性的方法

摘要：坑一慎用方法在類中，有一個方法是，返回的是一個數組，該數組包含了所包含的方法。坑二慎用線程優先級做并發處理線程中有屬性，表示線程的優先級，默認值為，取值區間為。顯然，運行時環境是因操作系統而異的。本文為作者原創，轉載請注明出處。我們都知道Java是跨平臺的，一次編譯，到處運行，本質上依賴于不同操作系統下有不同的JVM。到處運行是做到了，但運行結果呢？一樣的程序，在不同的JVM上跑的...

hidogs 2019-08-19 10:33 評論0 收藏0
基于ShineBlink物聯網開發板和機智云平臺開發的“針對短期內寵物無人照顧的智能寵物屋”系統

摘要：為了解決人們因工作出差旅游等短期時間內家中寵物無人照顧的問題，我們基于物聯網開發板機智云平臺和各類傳感器模塊研究設計了一套針對短期內寵物無人照顧的智能寵物屋系統。正式介紹作品前先說明一下，我是湖南文理學院計算機與電氣工程學院的一名大三學生，我叫陳海濤。作品全部內容均為個人創意、個人設計并手...

jerryloveemily 2021-09-29 09:34 評論0 收藏0