Go?Java算法之為運(yùn)算表達(dá)式設(shè)計(jì)優(yōu)先級(jí)實(shí)例

更新時(shí)間：2022年08月17日 09:01:14 作者：黃丫丫

這篇文章主要為大家介紹了Go?Java算法之為運(yùn)算表達(dá)式設(shè)計(jì)優(yōu)先級(jí)實(shí)例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

為運(yùn)算表達(dá)式設(shè)計(jì)優(yōu)先級(jí)

給你一個(gè)由數(shù)字和運(yùn)算符組成的字符串 expression ，按不同優(yōu)先級(jí)組合數(shù)字和運(yùn)算符，計(jì)算并返回所有可能組合的結(jié)果。你可以按任意順序返回答案。

生成的測(cè)試用例滿足其對(duì)應(yīng)輸出值符合 32 位整數(shù)范圍，不同結(jié)果的數(shù)量不超過 104 。

示例 1：

輸入：expression = "2-1-1"

輸出：[0,2]

解釋：

((2-1)-1) = 0

(2-(1-1)) = 2

示例 2：
輸入：expression = "23-45"
輸出：[-34,-14,-10,-10,10]

解釋：

(2*(3-(4*5))) = -34

((23)-(45)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

提示：

1 <= expression.length <= 20

expression 由數(shù)字和算符 '+'、'-' 和 '*' 組成。

輸入表達(dá)式中的所有整數(shù)值在范圍 [0, 99]

方法一：動(dòng)態(tài)規(guī)劃（Java）

因?yàn)樽罱K的答案是由一個(gè)個(gè)子問題（子表達(dá)式）的答案所構(gòu)成，所以我們可以采用動(dòng)態(tài)規(guī)劃，將問題劃分為一個(gè)個(gè)子問題來求解。

做出此題最關(guān)鍵的一步是要寫出合理的動(dòng)態(tài)規(guī)劃遞歸式。第一想法是定義dp[i]表示前i個(gè)數(shù)計(jì)算的結(jié)果，這樣定義我們很快會(huì)發(fā)現(xiàn)我們無法寫出dp[i+1]，因?yàn)樗鼈兿嗷グ瑳]有明確的界限。

比較好的遞歸式是定義dp[i][j]表示從第i個(gè)數(shù)開始到第j個(gè)數(shù)的表達(dá)式計(jì)算的結(jié)果，最終結(jié)果就是要求dp[0][N-1]。

首先我們將字符串分成digit、op、digit、op、digit、op、digit.....這樣的序列,并且可知序列的長(zhǎng)度是奇數(shù)個(gè),所以子問題的最小長(zhǎng)度為3（長(zhǎng)度為1的digit不需要計(jì)算）,也就是一個(gè)op運(yùn)算需要至少三個(gè)元素（兩個(gè)digit和一個(gè)op），下一個(gè)子問題的長(zhǎng)度為當(dāng)前子問題+2（加一個(gè)op和一個(gè)digit）,所以我們可以從最小長(zhǎng)度為3的子問題一步步求解最大長(zhǎng)度的解。

class Solution {
    static final int ADDITION = -1;
    static final int SUBTRACTION = -2;
    static final int MULTIPLICATION = -3;
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> ops = new ArrayList<Integer>();
        for (int i = 0; i < expression.length();) {
            if (!Character.isDigit(expression.charAt(i))) {
                if (expression.charAt(i) == '+') {
                    ops.add(ADDITION);
                } else if (expression.charAt(i) == '-') {
                    ops.add(SUBTRACTION);
                } else {
                    ops.add(MULTIPLICATION);
                }
                i++;
            } else {
                int t = 0;
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    t = t * 10 + expression.charAt(i) - '0';
                    i++;
                }
                ops.add(t);
            }
        }
        List<Integer>[][] dp = new List[ops.size()][ops.size()];
        for (int i = 0; i < ops.size(); i++) {
            for (int j = 0; j < ops.size(); j++) {
                dp[i][j] = new ArrayList<Integer>();
            }
        }
        for (int i = 0; i < ops.size(); i += 2) {
            dp[i][i].add(ops.get(i));
        }
        for (int i = 3; i <= ops.size(); i++) {
            for (int j = 0; j + i <= ops.size(); j += 2) {
                int l = j;
                int r = j + i - 1;
                for (int k = j + 1; k < r; k += 2) {
                    List<Integer> left = dp[l][k - 1];
                    List<Integer> right = dp[k + 1][r];
                    for (int num1 : left) {
                        for (int num2 : right) {
                            if (ops.get(k) == ADDITION) {
                                dp[l][r].add(num1 + num2);
                            } else if (ops.get(k) == SUBTRACTION) {
                                dp[l][r].add(num1 - num2);
                            } else if (ops.get(k) == MULTIPLICATION) {
                                dp[l][r].add(num1 * num2);
                            }
                        }
                    }
                }
            }
        }
        return dp[0][ops.size() - 1];
    }
};

時(shí)間復(fù)雜度：O（2^n）

空間復(fù)雜度：O（2^n）

方法二：分治（Go）

分治：定義最后一個(gè)生效的符號(hào)位置。比如 a+b+c+d,我們定義第二個(gè)加號(hào)，為最后的計(jì)算位置，則可以得到【a+b】+【c+d】，類似這樣的格式。然后此時(shí)可以發(fā)現(xiàn) A=a+b 是一個(gè)表達(dá)式，B=c+d也是一個(gè)表達(dá)式，他們可以分別計(jì)算出各自的結(jié)果，然后再通過這個(gè)加號(hào)計(jì)算 A+B，每組兩部分的和就對(duì)應(yīng)所有可能的結(jié)果

對(duì)于一個(gè)形如 x op y（op 為運(yùn)算符，x 和 y 為數(shù)）的算式而言，它的結(jié)果組合取決于 x 和 y 的結(jié)果組合數(shù)，而 x 和 y 又可以寫成形如 x op y 的算式。

因此，該問題的子問題就是 x op y 中的 x 和 y：以運(yùn)算符分隔的左右兩側(cè)算式解。

分治算法三步走：

分解：按運(yùn)算符分成左右兩部分，分別求解
解決：實(shí)現(xiàn)一個(gè)遞歸函數(shù)，輸入算式，返回算式解
合并：根據(jù)運(yùn)算符合并左右兩部分的解，得出最終解

import (
    "fmt"
    "strconv"
)
func diffWaysToCompute(input string) []int {
    // 如果是數(shù)字，直接返回
    if isDigit(input) {
        tmp, _ := strconv.Atoi(input)
        return []int{tmp}
    }
    // 空切片
    var res []int 
    // 遍歷字符串
    for index, c := range input {
        tmpC := string(c)
        if tmpC == "+" || tmpC == "-" || tmpC == "*" {
            // 如果是運(yùn)算符，則計(jì)算左右兩邊的算式
            left := diffWaysToCompute(input[:index])
            right := diffWaysToCompute(input[index+1:])
            for _, leftNum := range left {
                for _, rightNum := range right {
                    var addNum int
                    if tmpC == "+" {
                        addNum = leftNum + rightNum
                    } else if tmpC == "-" {
                        addNum = leftNum - rightNum
                    } else {
                        addNum = leftNum * rightNum
                    }
                    res = append(res, addNum)
                }
            }
        }
    }
    return res
}
// 判斷是否為全數(shù)字
func isDigit(input string) bool {
    _, err := strconv.Atoi(input)
    if err != nil {
        return false
    }
    return true
}

時(shí)間復(fù)雜度：O（2^n）

空間復(fù)雜度：O（2^n）

以上就是Go Java算法之為運(yùn)算表達(dá)式設(shè)計(jì)優(yōu)先級(jí)實(shí)例的詳細(xì)內(nèi)容，更多關(guān)于Go Java算法運(yùn)算表達(dá)式優(yōu)先級(jí)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: