280. Different Ways to Add Parentheses (Count)

Given a string expression of numbers and operators (+, -, *), return the number of results you can get from computing all the different ways to group numbers and operators (each distinct full parenthesization counts as one result, including duplicate values).

Input: A quoted expression string.

Output: Integer — number of grouping results.

Examples

Input: "2-1-1"
Output: 2
Explanation: Two parenthesizations.

Input: "2*3-4*5"
Output: 5
Explanation: Five groupings.

Input: "11"
Output: 1
Explanation: Single number.

Constraints

• 1<=expression.length<=20
• valid expression

Asked by