Divide and Conquer Algorithm: Operator Precedence

In A Step-by-Step Guide to Binary Trees (Overview), I mentioned that there are two main approaches to recursive algorithms: the "traversal" approach and the "problem decomposition" approach. I noted that the typical example of the "traversal" approach is backtracking, while the "problem decomposition" approach is best represented by dynamic programming.

The reason dynamic programming is considered the typical example of the "problem decomposition" approach is mainly because it is more familiar to most people. However, many algorithmic problems do not have the overlapping subproblems and optimal substructure characteristics of dynamic programming problems, but can still be solved using the "problem decomposition" approach. We can give these algorithms a sophisticated name and collectively refer to them as "divide and conquer algorithms."

The most typical divide and conquer algorithm is Merge Sort, with the core logic as follows:

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    // ***** Divide *****
    // Recursively sort the two halves of the array
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);
    // ***** Conquer *****
    // Merge the two sorted subarrays
    merge(nums, lo, mid, hi);
}

"Sorting an Array" is an algorithmic problem that can be approached using the divide-and-conquer strategy. As long as I first sort the left half of the array, then sort the right half, and finally merge the two parts, isn't that sorting the entire array?

Let's look at a specific algorithmic problem.

All Ways to Add Parentheses

I'll use LeetCode problem #241 "Different Ways to Add Parentheses" to explain what a divide-and-conquer algorithm is. First, let's look at the problem:

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(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

Simply put, you are given an arithmetic expression, and you can add parentheses to it in any way you like. Your task is to enumerate all possible ways to add parentheses and calculate the corresponding results.

The function signature is as follows:

// Calculate all the results with parentheses added
List<Integer> diffWaysToCompute(String input);

// Calculate all results with parentheses added
std::vector<int> diffWaysToCompute(std::string input);

# Calculate all the results with parentheses added
def diffWaysToCompute(input: str) -> List[int]:

// Calculate all results with parentheses added
func diffWaysToCompute(input string) []int {
    // your code here
}

// Calculate all results with parentheses added
var diffWaysToCompute = function(input) {

};