未分類

Different Ways to Add Parentheses

DivideAndConquer, Go, LeetCode

Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: “2-1-1”.

1
2
((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2:

Input: “2*3-4*5”

1
2
3
4
5
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Default:

1
2
3
func diffWaysToCompute(input string) []int {
}

解答思路:

這題剛開始容易因為該如何分配兩個運算元及運算子為一組而陷入錯誤的思考方向，如果只從運算子的角度來看，兩邊的運算元可能分別是一個數字或是一個式子出來的結果(而且有多組可能)，但不論如何要列出所有輸出結果的話，只需要針對兩邊運算元的多組可能進行排列組合，再透過運算子運算便能獲得所有輸出結果，所以一開始就要將算式拆成多個小式子，以每個運算子為中心，運算子之前的當作一個小式子，運算子之後的再當作另一個小式子，接著分別將兩個小子式再次帶入同一個函數做遞回，待兩邊分別所有可能的值回傳，便進行排列組合並透過運算子運算，最後透過遞回不斷重覆上述動作就可以得到該式子所有可能的結果。

程式碼解說:

一開始便直接遍歷整個式子，因為每次都要以運算子為中心來將式子拆成兩個小式子，所以如果碰上”+”,”-“,”*”,”/“的話，將運算子之前的當作一個小式子，運算子之後的再當作另一個小式子，接著分別將兩個小子式再次帶入同一個函數做遞回，待兩邊分別所有可能的值回傳，便以巢狀迴圈分別取出進行排列組合，並透過對應的運算子做運算後放入輸出的陣列之中，最後如果輸出的結果為空，表示最初進來的式子只有數字字串而已(也可能因為將原式子分割成小式子做遞回帶入時就只有運算元而已)，便將該數字字串轉成數字型別放入陣列向上回傳，否則才回傳整個輸出結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var str string
var front []int
var back []int
var output []int
for i, v := range input {
	str = string(v)
	if str == "+" || str == "-" || str == "*" || str == "/" {
		front = diffWaysToCompute(input[:i])
		back = diffWaysToCompute(input[i+1:])
		for _, fv := range front {
			for _, bv := range back {
				switch str {
				case "+":
					output = append(output, fv+bv)
				case "-":
					output = append(output, fv-bv)
				case "*":
					output = append(output, fv*bv)
				case "/":
					output = append(output, fv/bv)
				}
			}
		}
	}
}
if len(output) == 0 {
	num, _ := strconv.Atoi(input)
	return []int{num}
}
return output

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func diffWaysToCompute(input string) []int {
	var str string
	var front []int
	var back []int
	var output []int
	for i, v := range input {
		str = string(v)
		if str == "+" || str == "-" || str == "*" || str == "/" {
			front = diffWaysToCompute(input[:i])
			back = diffWaysToCompute(input[i+1:])
			for _, fv := range front {
				for _, bv := range back {
					switch str {
					case "+":
						output = append(output, fv+bv)
					case "-":
						output = append(output, fv-bv)
					case "*":
						output = append(output, fv*bv)
					case "/":
						output = append(output, fv/bv)
					}
				}
			}
		}
	}
	if len(output) == 0 {
		num, _ := strconv.Atoi(input)
		return []int{num}
	}
	return output
}

總結:

給一四則運算式要列出所有可能運算出的結果(在該式子其中隨意新增小括弧來改變運算的優先順序)，其做法是以每個運算子為中心，運算子之前的當作一個小式子，運算子之後的再當作另一個小式子，接著分別將兩個小子式再次帶入同一個函數做遞回，待兩邊分別所有可能的值回傳，便進行排列組合並透過運算子運算，最後透過遞回不斷重覆上述動作就可以得到該式子所有可能的結果。

分享到