Every Bracketing Result

Medium

You get an arithmetic expression expr made of non-negative integers and the operators +, - and *, with no brackets and no spaces. Brackets can be placed in many ways, and each full bracketing fixes the order in which the operations run. Evaluate the expression under **every** distinct full bracketing and return all the values you get. If several bracketings give the same number, it appears in the answer once per bracketing. The values may be returned in any order.

Example 1

expr="6-2+1" → [3, 5]

(6-2)+1 = 5 and 6-(2+1) = 3.

Example 2

expr="3*4-2*2" → [0, 12, 8, 12, 20]

Five ways to bracket: 3*(4-(2*2)) = 0, 3*((4-2)*2) = 12, (3*4)-(2*2) = 8, (3*(4-2))*2 = 12, ((3*4)-2)*2 = 20. Equal values from different bracketings are repeated.

Example 3

expr="42" → [42]

Constraints

1 ≤ len(expr) ≤ 20
expr consists of digits and the characters +, -, *
every number in the expression is between 0 and 99 and has no sign
the expression starts and ends with a number and never has two operators in a row

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Recursion Memoization Math String Dynamic Programming

Similar problems

Sum of the Two Before Easy Grading the Arithmetic Quiz Hard Split Into Dictionary Words Medium Shared Pool Race to a Goal Medium Duel for the End Cards Medium

Input

expr="6-2+1"

Expected

[3, 5]

Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.