#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/different-ways-to-add-parentheses-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/different-ways-to-add-parentheses-implementation

Repovive

Different Ways to Add Parentheses - Implementation - Divide and Conquer | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Different Ways to Add Parentheses - Implementation

Here is the implementation:

function diffWaysToCompute(expression):
    results = []

    for i from 0 to expression.length - 1:
        c = expression[i]
        if c in ['+', '-', '*']:
            left = diffWaysToCompute(expression[0..i-1])
            right = diffWaysToCompute(expression[i+1..])

            for l in left:
                for r in right:
                    if c == '+': results.append(l + r)
                    if c == '-': results.append(l - r)
                    if c == '*': results.append(l * r)

    if results is empty:
        results.append(parseInt(expression))

    return results

Add memoization for repeated subexpressions to optimize. Time complexity is Catalan-like.