Possible ways to add operators and parentheses

Given a set of numbers, there are many possible ways to add operators and parentheses to form an valid expression. The operations are +, -, *, /. The operator * and / have higher precedence than + and – . In infix expressions, we add parentheses to override the normal precedence of operators. Anything in parentheses will be calculated first.

For a given an array of numbers, what’s the number of ways to add operators and parentheses, and what are the values of the expressions? This problem is similar to generating valid parentheses. It can be solved using backtracking. In the recursive method, we iterator through the index of the input list. Each time, split the input list into two sub-lists by the index. Then call itself with the left and right sub-lists. They will return the partial result from the further divided sub-lists. Then calculate the result with operators of +,-,* and /.

A HashMap<List, List> is used to store partial results. The keys are the combinations of operands in the array. For example, with input [5,1,3], the keys can be [5,1] [1,3] or [5,1,3] etc. The values are the results after applying four operators (ie +, -, *, /). At the beginning of the recursive method, the method checks whether the input list is in the HashMap’s key. If it is, it will return the result directly without going further. This technique is memoization. At the end of method, new result is saved in the map.

The overall time complexity after memoization is O(Cn^2), n is numbers in the input array. O( Cn^2) indicates the level of complexity, not the exact number. It might vary depending on how much memoization can apply. The time complexity can grow very fast when n increases.

Once we have all the possible combinations and results, we can answer the questions such as number of ways to add parentheses and operators, and what is the max possible value of expressions.

Google Interview Question:
Your input is an array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.
Ex: input is {3,4,5,1} –> output: 72
input is {1,1,1,5} –> output: 15

Java

JavaScript

Python

Doodle

evaulate all possible expressions doodle

Output:
Input: [3, 4, 5, 1]
Max possible value is: 72

O Notation:
Time complexity:O(Cn^2), Cn is Catalan number, n is array length
Space complexity: Space O(Cn^2)


Download EvaluateAllPossibleExpressions.java
Download EvaluateAllPossibleExpressions.js
Download EvaluateAllPossibleExpressions.py

Comments are closed