Every Way To Bracket
Problem
A string holds non-negative integers joined by the operators +, - and *, with no spaces. Add brackets in every way that fully decides the order in which the operators are applied, evaluate each version, and return all the results in sorted order. Two different bracketings that give the same value both appear.
Examples
Input: expr = "2-1-1"
Output: [0, 2]
Why: (2-1)-1 is 0 and 2-(1-1) is 2Input: expr = "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Why: five bracketings, two of which happen to agreeInput: expr = "7"
Output: [7]
Why: edge case, a lone number has exactly one way to be readHints
0 / 3
Instead of deciding which operator goes first, think about which operator is applied last. Everything to its left and everything to its right is then evaluated on its own.
Splitting at an operator leaves two smaller expressions of exactly the same kind. Each of them has its own list of possible values, and the same piece of the string can come up through many different splits.
For each operator position, get every value of the left part and every value of the right part recursively, and combine each pair with that operator. A piece with no operator is just its number. Cache results by the piece of string so repeated pieces are solved once, then sort the final list.
Solution
Every full bracketing has one operator that is applied last, and choosing it splits the expression into a left and a right part that are bracketed independently, so the set of results is the union over all split points of every left value combined with every right value. The recursion bottoms out at a piece with no operator, which is just its number. The same substring is reached through many different split sequences, so caching by substring stops that work from being repeated. The number of results grows like the Catalan numbers, which dominates both time and space.
from functools import lru_cache
import operator
OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul}
def all_results(expr):
@lru_cache(maxsize=None)
def solve(s): # every value s can take
out = []
for i, ch in enumerate(s):
if ch in OPS: # this operator is applied last
for a in solve(s[:i]):
for b in solve(s[i + 1:]):
out.append(OPS[ch](a, b))
return tuple(out) if out else (int(s),) # no operator: a plain number
return sorted(solve(expr))
print(all_results("2-1-1")) # -> [0, 2]
print(all_results("2*3-4*5")) # -> [-34, -14, -10, -10, 10]
print(all_results("7")) # -> [7]Stuck on the idea rather than the code? Memoization covers it.