Different Ways To Add Parentheses

                                            
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        for (int i = 0; i < expression.size(); i++) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));
                for (int l : left) {
                    for (int r : right) {
                        if (c == '+') {
                            res.push_back(l + r);
                        } else if (c == '-') {
                            res.push_back(l - r);
                        } else {
                            res.push_back(l * r);
                        }
                    }
                }
            }
        }
        if (res.empty()) {
            res.push_back(stoi(expression));
        }
        return res;
    }
};

                                            
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    Map<String, List<Integer>> memo = new HashMap<>();

    public List<Integer> diffWaysToCompute(String input) {
        if (memo.containsKey(input)) {
            return memo.get(input);
        }

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> leftPart = diffWaysToCompute(input.substring(0, i));
                List<Integer> rightPart = diffWaysToCompute(input.substring(i + 1));

                for (int left : leftPart) {
                    for (int right : rightPart) {
                        if (c == '+') {
                            result.add(left + right);
                        } else if (c == '-') {
                            result.add(left - right);
                        } else if (c == '*') {
                            result.add(left * right);
                        }
                    }
                }
            }
        }

        if (result.isEmpty()) {
            result.add(Integer.parseInt(input));
        }

        memo.put(input, result);
        return result;
    }
}

                                            
class Solution(object):
    def diffWaysToCompute(self, expression):
        """
        :type expression: str
        :rtype: List[int]
        """
        def compute(left, right, op):
            results = []
            for l in left:
                for r in right:
                    if op == '+':
                        results.append(l + r)
                    elif op == '-':
                        results.append(l - r)
                    elif op == '*':
                        results.append(l * r)
            return results
        
        if expression.isdigit():
            return [int(expression)]
        
        results = []
        for i in range(len(expression)):
            if expression[i] in ['+', '-', '*']:
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i+1:])
                
                results.extend(compute(left, right, expression[i]))
        
        return results

                                            
public class Solution {
    public IList<int> DiffWaysToCompute(string expression) {
        var result = new List<int>();
        for (int i = 0; i < expression.Length; i++) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
                string part1 = expression.Substring(0, i);
                string part2 = expression.Substring(i + 1);
                var part1Res = DiffWaysToCompute(part1);
                var part2Res = DiffWaysToCompute(part2);
                foreach (var p1 in part1Res) {
                    foreach (var p2 in part2Res) {
                        switch (c) {
                            case '+':
                                result.Add(p1 + p2);
                                break;
                            case '-':
                                result.Add(p1 - p2);
                                break;
                            case '*':
                                result.Add(p1 * p2);
                                break;
                        }
                    }
                }
            }
        }
        if (result.Count == 0) {
            result.Add(int.Parse(expression));
        }
        return result;
    }
}

                                            
/**
 * @param {string} expression
 * @return {number[]}
 */
var diffWaysToCompute = function(expression) {
    const memo = new Map();
    
    const compute = (expression) => {
        if (memo.has(expression)) return memo.get(expression);
        
        const result = [];
        
        for (let i = 0; i < expression.length; i++) {
            const char = expression[i];
            if (char === '+' || char === '-' || char === '*') {
                const left = compute(expression.substring(0, i));
                const right = compute(expression.substring(i + 1));
                
                for (const l of left) {
                    for (const r of right) {
                        if (char === '+') {
                            result.push(l + r);
                        } else if (char === '-') {
                            result.push(l - r);
                        } else if (char === '*') {
                            result.push(l * r);
                        }
                    }
                }
            }
        }
        
        if (result.length === 0) {
            result.push(parseInt(expression));
        }
        
        memo.set(expression, result);
        return result;
    }
    
    return compute(expression);
};

                                            
function diffWaysToCompute(expression: string): number[] {
    const memo: Map<string, number[]> = new Map();

    const compute = (exp: string): number[] => {
      if (memo.has(exp)) return memo.get(exp)!;
  
      const result: number[] = [];
      for (let i = 0; i < exp.length; i++) {
        const char = exp[i];
        if (char === '+' || char === '-' || char === '*') {
          const left = compute(exp.slice(0, i));
          const right = compute(exp.slice(i + 1));
          for (const num1 of left) {
            for (const num2 of right) {
              if (char === '+') {
                result.push(num1 + num2);
              } else if (char === '-') {
                result.push(num1 - num2);
              } else if (char === '*') {
                result.push(num1 * num2);
              }
            }
          }
        }
      }
  
      if (result.length === 0) {
        result.push(parseInt(exp));
      }
  
      memo.set(exp, result);
      return result;
    };
  
    return compute(expression);
};

                                            
class Solution {
    /**
     * @param String $expression
     * @return Integer[]
     */
    function diffWaysToCompute($expression) {
        $output = [];
        
        if (is_numeric($expression)) {
            return [$expression];
        }
        
        for ($i = 0; $i < strlen($expression); $i++) {
            $char = $expression[$i];
            
            if ($char == '+' || $char == '-' || $char == '*') {
                $leftPart = $this->diffWaysToCompute(substr($expression, 0, $i));
                $rightPart = $this->diffWaysToCompute(substr($expression, $i + 1));
                
                foreach ($leftPart as $left) {
                    foreach ($rightPart as $right) {
                        switch ($char) {
                            case '+': $output[] = $left + $right; break;
                            case '-': $output[] = $left - $right; break;
                            case '*': $output[] = $left * $right; break;
                        }
                    }
                }
            }
        }
        
        return empty($output) ? [(int)$expression] : $output;
    }
}

                                            
class Solution {
    func diffWaysToCompute(_ expression: String) -> [Int] {
        var memo = [String: [Int]]()
        
        func compute(_ expr: String) -> [Int] {
            if let cached = memo[expr] {
                return cached
            }
            
            var result = [Int]()
            for (index, char) in expr.enumerated() {
                if char == "+" || char == "-" || char == "*" {
                    let leftPart = compute(String(expr[..<expr.index(expr.startIndex, offsetBy: index)]))
                    let rightPart = compute(String(expr[expr.index(expr.startIndex, offsetBy: index + 1)...]))
                    
                    for left in leftPart {
                        for right in rightPart {
                            if char == "+" {
                                result.append(left + right)
                            } else if char == "-" {
                                result.append(left - right)
                            } else if char == "*" {
                                result.append(left * right)
                            }
                        }
                    }
                }
            }
            
            if result.isEmpty {
                result.append(Int(expr)!)
            }
            
            memo[expr] = result
            return result
        }
        
        return compute(expression)
    }
}

                                            
import java.util.*

class Solution {
    fun diffWaysToCompute(expression: String): List<Int> {
        val result = mutableListOf<Int>()

        for (i in expression.indices) {
            val c = expression[i]
            if (c == '+' || c == '-' || c == '*') {
                val leftPart = diffWaysToCompute(expression.substring(0, i))
                val rightPart = diffWaysToCompute(expression.substring(i + 1))

                for (left in leftPart) {
                    for (right in rightPart) {
                        when (c) {
                            '+' -> result.add(left + right)
                            '-' -> result.add(left - right)
                            '*' -> result.add(left * right)
                        }
                    }
                }
            }
        }

        if (result.isEmpty()) {
            result.add(expression.toInt())
        }

        return result
    }
}

                                            
class Solution {
  List<int> diffWaysToCompute(String expression) {
    List<int> res = [];
    for (int i = 0; i < expression.length; i++) {
      if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
        List<int> leftPart = diffWaysToCompute(expression.substring(0, i));
        List<int> rightPart = diffWaysToCompute(expression.substring(i + 1));
        for (int left in leftPart) {
          for (int right in rightPart) {
            if (expression[i] == '+') {
              res.add(left + right);
            } else if (expression[i] == '-') {
              res.add(left - right);
            } else {
              res.add(left * right);
            }
          }
        }
      }
    }
    if (res.isEmpty) {
      res.add(int.parse(expression));
    }
    return res;
  }
}

                                            
import "strconv"

func diffWaysToCompute(expression string) []int {
    var res []int
    for i := 0; i < len(expression); i++ {
        if expression[i] == '+' || expression[i] == '-' || expression[i] == '*' {
            left := diffWaysToCompute(expression[:i])
            right := diffWaysToCompute(expression[i+1:])
            for _, l := range left {
                for _, r := range right {
                    var val int
                    switch expression[i] {
                    case '+':
                        val = l + r
                    case '-':
                        val = l - r
                    case '*':
                        val = l * r
                    }
                    res = append(res, val)
                }
            }
        }
    }
    if len(res) == 0 {
        num, _ := strconv.Atoi(expression)
        res = append(res, num)
    }
    return res
}

                                            
# @param {String} expression
# @return {Integer[]}
def diff_ways_to_compute(expression)
    def compute(left, right, op)
        case op
        when '+'
            return left + right
        when '-'
            return left - right
        when '*'
            return left * right
        end
    end
    
    if expression.match(/\D/).nil?
        return [expression.to_i]
    end
    
    result = []
    
    (0...expression.length).each do |i|
        if ['+', '-', '*'].include?(expression[i])
            left_parts = diff_ways_to_compute(expression[0...i])
            right_parts = diff_ways_to_compute(expression[(i+1)..-1])
            
            left_parts.each do |left|
                right_parts.each do |right|
                    result << compute(left, right, expression[i])
                end
            end
        end
    end
    
    return result
end

                                            
object Solution {
    def diffWaysToCompute(expression: String): List[Int] = {
        def compute(left: List[Int], right: List[Int], op: Char): List[Int] = {
            for {
                x <- left
                y <- right
            } yield {
                op match {
                    case '+' => x + y
                    case '-' => x - y
                    case '*' => x * y
                }
            }
        }
        
        if (expression.forall(_.isDigit)) List(expression.toInt)
        else {
            (for {
                (c, i) <- expression.zipWithIndex if !c.isDigit
            } yield {
                val leftPart = diffWaysToCompute(expression.substring(0, i))
                val rightPart = diffWaysToCompute(expression.substring(i + 1))
                compute(leftPart, rightPart, c)
            }).flatten.toList
        }
    }
}

                                            
impl Solution {
    pub fn diff_ways_to_compute(expression: String) -> Vec<i32> {
        
        fn helper(input: &str, memo: &mut std::collections::HashMap<String, Vec<i32>>) -> Vec<i32> {
            if let Some(result) = memo.get(input) {
                return result.clone();
            }
            
            let mut result = Vec::new();
            let chars: Vec<char> = input.chars().collect();
            
            for (i, &c) in chars.iter().enumerate() {
                if c == '+' || c == '-' || c == '*' {
                    let left = helper(&input[..i], memo);
                    let right = helper(&input[i+1..], memo);
                    
                    for &l in &left {
                        for &r in &right {
                            if c == '+' {
                                result.push(l + r);
                            } else if c == '-' {
                                result.push(l - r);
                            } else if c == '*' {
                                result.push(l * r);
                            }
                        }
                    }
                }
            }
            
            if result.is_empty() {
                result.push(input.parse().unwrap());
            }
            
            memo.insert(input.to_string(), result.clone());
            
            result
        }
        
        let mut memo = std::collections::HashMap::new();
        helper(&expression, &mut memo)
    }
}

To solve this coding challenge, we need to develop an approach that evaluates all possible ways we can add parentheses to an expression involving numbers and operators (

+

-

*

). For each valid way to group the numbers and operators, we should compute the value of the resulting expression and return all the possible values. Here's how we can achieve that:

Explanation

Problem Analysis:

Given an expression with numbers and the operators

+

-

*

, there are multiple ways to add parentheses which changes the order of operations and hence the final result of the expression. We need to explore all possible parenthesizations of the expression, compute their values, and return all such possible values.

Recursive Approach:

The problem can be approached using recursion and the divide-and-conquer strategy:

Base Case : If the input expression contains only a number, return its integer value as the only possible result.
Recursive Case :

Iterate through the expression.
Whenever an operator (
+

,
-

,
*

) is found:

Divide the expression into two parts: left and right around this operator.
Recursively compute all possible results for the left and right parts.
Combine the results of the left and right parts based on the current operator and store these combined results.

Merge all combined results from the current division point and move to the next operator in the expression.

This recursion ensures that we evaluate all possible ways to add parentheses and group the sub-expressions.

Step-by-Step Explanation

Initial Setup :

Create a function
diffWaysToCompute

that processes the expression.
If the expression consists only of digits, convert it to an integer and return as the only result.

Dividing the expression :

For each character in the expression, check if it is an operator (
+

,
-

,
*

).
If yes, split the expression into left and right sub-expressions around this operator.

Recursive Calls :

Recursively call
diffWaysToCompute

for both left and right sub-expressions.
This breaks down the problem into smaller subproblems.

Combining Results :

Use a helper function
compute

that takes results from left and right sub-expressions along with the current operator.
Depending on the operator, compute the result for each pair of left and right results and store these results.

Return Results :

After processing all operators in the expression, return the collected results.

Detailed Steps in Pseudocode

Base Case and Initial Setup

                                            
FUNCTION diffWaysToCompute(expression):
    IF expression is a digit:
        RETURN [integer value of expression]
    END IF

Recursive Case: Iterate over the expression and check for operators

                                            
    results = []
    FOR i FROM 0 TO length of expression - 1:
        IF expression[i] is '+', '-', or '*':
            left_results = diffWaysToCompute(expression from start to i-1)
            right_results = diffWaysToCompute(expression from i+1 to end)
            
            # Compute results for current split
            combined_results = compute(left_results, right_results, expression[i])
            results.extend(combined_results)
        END IF
    END FOR
    
    RETURN results
END FUNCTION

Compute function to handle combinations based on operator

                                            
FUNCTION compute(left_list, right_list, operator):
    combined_results = []
    
    FOR each left_value in left_list:
        FOR each right_value in right_list:
            IF operator is '+':
                combined_results.append(left_value + right_value)
            ELSE IF operator is '-':
                combined_results.append(left_value - right_value)
            ELSE IF operator is '*':
                combined_results.append(left_value * right_value)
            END IF
        END FOR
    END FOR
    
    RETURN combined_results
END FUNCTION

This pseudocode provides a structured approach to solve the given problem by exploring all possible ways to parenthesize the expression and computing the respective outcomes for each. This ensures that every valid expression result is considered and returned.