Different Ways to Add Parentheses

Problem

You are given a string expression made of non-negative integers joined by the binary operators +, - and * (no spaces, no parentheses, no unary minus). Consider every distinct way to fully parenthesize the expression, meaning every distinct binary evaluation tree over its operands in their original order. Evaluate each one and return all the results. Return the values in **any order**. If two different groupings produce the same number, that number appears once per grouping (duplicates are kept).

Examples

Constraints

• 1 <= expression.length <= 20
• Operands are integers in [0, 99] with no leading zeros
• expression contains only digits and '+', '-', '*'
• Every result fits in a 32-bit signed integer

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More interval dp problems

• Minimum Insertion Steps to Make a String PalindromeHard
• Longest Palindromic SubsequenceMedium
• Minimum Cost to Cut a StickHard
• Scramble StringHard
• Minimum Cost to Merge StonesHard
• Strange PrinterHard