Introduction

Given an expression string such as 2*3+5, the parenthesization problem asks whether some placement of parentheses makes the expression evaluate to a target value. This is a classic dynamic-programming problem because the same subexpressions appear repeatedly. The standard solution computes all possible values for every substring and then checks whether the target is among them.

Why Parentheses Change the Value

Without added parentheses, operator precedence fixes the evaluation order. When you are allowed to parenthesize freely, you can force different split points and therefore different results.

For example, with 2*3+5:

• '(2*3)+5 = 11'
• '2*(3+5) = 16'

So the same tokens can produce different values depending on how the expression tree is built.

Dynamic Programming Over Subexpressions

A natural state is:

values(i, j) = all possible results from the substring between token i and token j

If you split at an operator k, then every result from the left side can combine with every result from the right side.

For expressions made of single-digit numbers and operators +, -, and *, a memoized recursive solution is straightforward.

1from functools import lru_cache
2
3
4def compute_all_results(expr):
5    tokens = []
6    number = ""
7    for ch in expr:
8        if ch.isdigit():
9            number += ch
10        else:
11            tokens.append(int(number))
12            tokens.append(ch)
13            number = ""
14    tokens.append(int(number))
15
16    @lru_cache(None)
17    def solve(left, right):
18        if left == right:
19            return {tokens[left]}
20
21        results = set()
22        for mid in range(left + 1, right, 2):
23            op = tokens[mid]
24            left_values = solve(left, mid - 1)
25            right_values = solve(mid + 1, right)
26
27            for a in left_values:
28                for b in right_values:
29                    if op == "+":
30                        results.add(a + b)
31                    elif op == "-":
32                        results.add(a - b)
33                    elif op == "*":
34                        results.add(a * b)
35        return results
36
37    return solve(0, len(tokens) - 1)
38
39
40expr = "2*3+5"
41print(compute_all_results(expr))

This returns every value achievable through legal parenthesization.

Checking Whether a Target Is Reachable

Once you can compute all possible values, checking the target is easy:

1def can_make_target(expr, target):
2    return target in compute_all_results(expr)
3
4
5print(can_make_target("2*3+5", 11))
6print(can_make_target("2*3+5", 16))
7print(can_make_target("2*3+5", 7))

This is often the exact form of the interview or algorithm question: return a boolean instead of the full set.

Reconstructing One Valid Parenthesization

If you need not only the answer but also one parenthesized expression that reaches the target, store expressions along with values.

1from functools import lru_cache
2
3
4def build_one_expression(expr, target):
5    tokens = []
6    number = ""
7    for ch in expr:
8        if ch.isdigit():
9            number += ch
10        else:
11            tokens.append(number)
12            tokens.append(ch)
13            number = ""
14    tokens.append(number)
15
16    @lru_cache(None)
17    def solve(left, right):
18        if left == right:
19            value = int(tokens[left])
20            return {value: tokens[left]}
21
22        results = {}
23        for mid in range(left + 1, right, 2):
24            op = tokens[mid]
25            left_map = solve(left, mid - 1)
26            right_map = solve(mid + 1, right)
27
28            for a, expr_a in left_map.items():
29                for b, expr_b in right_map.items():
30                    if op == "+":
31                        value = a + b
32                    elif op == "-":
33                        value = a - b
34                    else:
35                        value = a * b
36                    results.setdefault(value, f"({expr_a}{op}{expr_b})")
37        return results
38
39    return solve(0, len(tokens) - 1).get(target)
40
41
42print(build_one_expression("2*3+5", 11))

This is more expensive, but it is useful if the problem asks for an actual parenthesization instead of only a yes-or-no answer.

Complexity Discussion

The number of possible parenthesizations grows quickly, so the set of achievable values can also grow quickly. Dynamic programming helps because every substring is solved once and memoized, but the problem is still inherently combinatorial.

That means the DP solution is practical for moderate expression sizes, not arbitrarily large ones.

Common Pitfalls

The biggest mistake is trying to solve the problem with only normal precedence rules. The whole point is that parenthesization creates alternative parse trees.

Another mistake is recomputing the same substring repeatedly without memoization. That turns a manageable dynamic-programming problem into a much slower recursive search.

People also forget that the set of possible values may contain duplicates from different parenthesizations. A set is usually the right data structure when you only care about reachable values.

Finally, define the allowed operator set clearly. Supporting +, -, and * is straightforward, but adding division or unary operators changes the edge cases significantly.

Summary

• Parenthesization changes the expression tree and therefore can change the final value.
• A standard solution uses dynamic programming over subexpressions.
• Memoization avoids recomputing the same substring many times.
• You can compute all reachable values, then test whether the target is present.
• If needed, store one expression per value to reconstruct a valid parenthesization.