從一串數字產生有效表達式以獲取目標數字
1. 簡介
在本教程中，我們將探討如何透過在字串的數字之間插入二元運算子來解決產生所有有效表達式的問題。結果表達式必須與目標數字相符。這個問題結合了字串操作、遞歸和回溯概念，使其成為一個常見的面試問題。
我們將使用回溯演算法來開發解決方案。我們還將回顧該演算法如何遞歸工作並測試其功能。最後，我們將研究時間和空間複雜度，以確保我們的解決方案是有效的。
2. 理解問題
讓我們先分解問題及其要求。我們有一串數字和一個整數目標。我們需要在數字之間插入二元運算子（+、- 或 *），以便結果表達式計算為指定的目標值。
給定的字串長度在一到十位數字之間。此外，目標值在 32 位元有符號整數的範圍內。這意味著處理不同長度的數字。我們還需要確保我們的解決方案在這些範圍內有效運作。
此外，我們可以將字串拆分為多個表示運算元的子字串，除非運算元為0 ，否則子字串不能包含前導零。例如， 05或012無效，但零有效。
總之，任務是探索操作數的所有可能組合並插入允許的運算子以檢查哪些組合與目標相符。例如，如果字串是“123”且目標值是6 ，則有效表達式可以是1*2*3和1+2+3 ，這兩個表達式的計算結果都是6 。
讓我們來探索如何使用回溯有效地解決這個問題。
3.回溯演算法
簡而言之，回溯是一種解決問題的技術，它系統地探索所有潛在的組合來解決計算問題。該演算法透過嘗試部分解決方案並丟棄那些不滿足問題限制的解決方案來縮小可能性，直到找到有效的解決方案。
換句話說，它是一種增強的蠻力方法，可以遞歸地解決問題，並做出一系列決策。回溯的概念表明，如果目前的解決方案被證明不合適，演算法就會丟棄它並回溯以探索替代解決方案。
當一個問題有多個潛在的解決方案時，通常會採用回溯方法。它通常用於需要探索所有可能的組合或配置的場景，例如生成排列、解決填字遊戲或數獨謎題、解決N-Queens和迷宮導航等問題，或評估數學表達式。
讓我們實作一個遞歸回溯來示範所描述的方法。
4. 遞歸回溯實現
簡而言之，對於給定的問題，回溯演算法遞歸地探索在數字之間插入運算子（+、- 或 *）的所有可能方法。在每一步中，我們決定在兩個數字之間放置一個運算符，然後繼續探索字串的下一部分。如果結果表達式在任何時候與目標匹配，我們就認為該組合是有效的解決方案。
4.1.計算表達式
首先，我們必須定義一個入口點。 process()方法初始化一個結果列表，將輸入字串和目標值包裝到Equation物件中，並透過呼叫evaluateExpressions()函數啟動遞歸回溯過程：
List<String> process(String digits, int target) {
final List<String> validExpressions = new ArrayList<>();
evaluateExpressions(validExpressions, new Equation(digits, target), 0, new StringBuilder(), 0, 0);
return validExpressions;
}接下來，在evaluateExpressions()方法中，我們區分兩種情況——所有輸入字串數字都已處理完畢，或者處理仍在進行中。如果我們到達字串的末尾，我們會檢查評估值是否與目標相符。如果滿足以下條件，則當前表達式被視為有效，並添加到結果清單中：
void evaluateExpressions(List<String> validExpressions, Equation equation,
int index, StringBuilder currentExpression, long currentResult,
long lastOperand) {
if (allDigitsProcessed(equation.getDigits(), index)) {
if (currentResult == equation.getTarget()) {
validExpressions.add(currentExpression.toString());
}
return;
}
exploreExpressions(validExpressions, equation, index, currentExpression, currentResult, lastOperand);
}另一方面， exploreExpressions()方法遍歷剩餘的數字並逐步形成數字。它透過插入不同的運算符，遞歸地探索每個數字的三個可能分支，並在每一步更新表達式及其當前值：
void exploreExpressions(List<String> validExpressions, Equation equation,
int index, StringBuilder currentExpression, long currentResult,
long lastOperand) {
for (int endIndex = index; endIndex < equation.getDigits().length(); endIndex++) {
if (isWithLeadingZero(equation.getDigits(), index, endIndex)) {
break;
}
long currentOperandValue = Long.parseLong(equation.getDigits()
.substring(index, endIndex + 1));
if (isFirstOperand(index)) {
processFirstOperand(validExpressions, equation, endIndex,
currentExpression, currentOperandValue);
} else {
applyAddition(validExpressions, equation, endIndex,
currentExpression, currentResult, currentOperandValue);
applySubtraction(validExpressions, equation, endIndex,
currentExpression, currentResult, currentOperandValue);
applyMultiplication(validExpressions, equation, endIndex,
currentExpression, currentResult, currentOperandValue, lastOperand);
}
}
}讓我們看看如何處理不同的算術運算。
4.2.處理算術運算
根據操作，呼叫不同的方法。例如， applyAddition()將plus號和目前操作數值附加到目前表達式，透過新增目前運算元來更新結果，並遞歸地評估下一個潛在表達式：
void applyAddition(List<String> validExpressions, Equation equation,
int endIndex, StringBuilder currentExpression, long currentResult,
long currentOperandValue) {
appendToExpression(currentExpression, Operator.ADDITION, currentOperandValue);
evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
currentResult + currentOperandValue, currentOperandValue);
removeFromExpression(currentExpression, Operator.ADDITION, currentOperandValue);
}隨後，它會透過刪除最近新增的值來進行回溯並嘗試下一種可能性。
類似地， applySubtraction()方法將minus和操作數值加到目前表達式，並透過減去運算元來調整結果。然後繼續遞歸評估：
void applySubtraction(List<String> validExpressions, Equation equation,
int endIndex, StringBuilder currentExpression, long currentResult,
long currentOperandValue) {
appendToExpression(currentExpression, Operator.SUBTRACTION, currentOperandValue);
evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
currentResult - currentOperandValue, -currentOperandValue);
removeFromExpression(currentExpression, Operator.SUBTRACTION, currentOperandValue);
}最後， applyMultiplication()方法透過考慮先前使用的操作數來調整結果。這確保了操作的正確順序：
void applyMultiplication(List<String> validExpressions, Equation equation,
int endIndex, StringBuilder currentExpression, long currentResult,
long currentOperandValue, long lastOperand) {
appendToExpression(currentExpression, Operator.MULTIPLICATION, currentOperandValue);
evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
currentResult - lastOperand + (lastOperand * currentOperandValue),
lastOperand * currentOperandValue);
removeFromExpression(currentExpression, Operator.MULTIPLICATION, currentOperandValue);
}由於乘法的優先權高於加法或減法，因此它透過消除前一個運算元的影響並將乘法應用於最後一個運算元來重新計算結果。
5.測試實現
讓我們測試我們的實現，以確保演算法正確處理各種輸入並產生預期的結果。為了驗證無效方程式不傳回任何結果，我們將建立一個參數化測試並提供一組不正確的表達式：
private static Stream<Arguments> equationsWithNoSolutions() {
return Stream.of(Arguments.of("3456237490", 9191), Arguments.of("5", 0));
}
@ParameterizedTest
@MethodSource("equationsWithNoSolutions")
void givenEquationsWithNoSolutions_whenProcess_thenEmptyListIsReturned(String digits, int target) {
final List<String> result = Backtracking.process(digits, target);
assertTrue(result.isEmpty());
}測試通過，因為提供的值均未產生與目標匹配的有效方程式。
接下來，讓我們檢查一下當我們提供有效的方程式時演算法是否會傳回正確的結果：
Stream<Arguments> equationsWithValidSolutions() {
return Stream.of(Arguments.of("1", 1, Collections.singletonList("1")),
Arguments.of("00", 0, Arrays.asList("0+0", "0-0", "0*0")),
Arguments.of("123", 6, Arrays.asList("1+2+3", "1*2*3")),
Arguments.of("232", 8, Arrays.asList("2*3+2", "2+3*2")),
Arguments.of("534", -7, Collections.singletonList("5-3*4")),
Arguments.of("1010", 20, Collections.singletonList("10+10")),
Arguments.of("1234", 10, Arrays.asList("1+2+3+4", "1*2*3+4")),
Arguments.of("1234", -10, Collections.singletonList("1*2-3*4")),
Arguments.of("12345", 15, Arrays.asList("1+2+3+4+5", "1*2*3+4+5", "1-2*3+4*5", "1+23-4-5")));
}
@ParameterizedTest
@MethodSource("equationsWithValidSolutions")
void givenEquationsWithValidSolutions_whenProcess_thenValidResultsAreReturned(
String digits, int target, List<String> expectedSolutions) {
List<String> result = Backtracking.process(digits, target);
assertEquals(expectedSolutions.size(), result.size());
expectedSolutions.stream()
.map(result::contains)
.forEach(Assertions::assertTrue);
}首先，我們檢查結果數量是否與預期的解決方案數量相符。然後，我們確保每個預期的解決方案都在結果清單中。這驗證了演算法正確識別了所有有效的表達式。
6.複雜性分析
該演算法使用回溯來嘗試數字之間所有可能的運算子組合。由於我們可以組成多位數字，我們也可以選擇將目前數字與前一位數字合併。因此，我們可以在數字之間的每個位置插入不插入任何運算符或插入三個運算符（+、-、*）中的一個。如果有n位數字，則有n-1位置。每個位置有四種可能的選擇，因此大約有4^(n-1)種可能的組合。
此外，每次遞歸呼叫都會處理一個數字，更新表達式，並檢查它是否與目標匹配，每次呼叫花費O(n)時間。因此總時間複雜度為O(4^(n-1) * n) 。
另一方面，我們可以將空間複雜度分解為兩個關鍵因素。首先是遞歸堆疊。由於每次遞歸呼叫只處理一個數字，因此遞歸深度為O(n) 。其次，將表達式儲存在結果清單中。由於此演算法產生所有有效表達式，因此表達式的數量為O(4^(n-1)) ，每個表達式的長度為O(n).因此，儲存有效表達式所需的空間為O(4^(n-1) * n) ，使得總空間複雜度為O(n + 4^(n-1) * n) 。
7. 結論
在本文中，我們學習如何透過在數字之間插入二元運算子來匹配目標值，從而產生有效的表達式。回溯演算法有效地探索了所有可能的解決方案，使其成為解決類似組合問題的強大工具。
與往常一樣，完整的原始程式碼可在 GitHub 上取得。