Given a set of numbers, there are many different 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? 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | import java.util.*; public class EvaluateAllPossibleExpressions { //Wrapper, Time O(Cn^2), Space O(Cn^2), Cn is Catalan number, n is array length public static int evaluateExpressions(List<Integer> tokens) { List<Integer> res = helper(tokens, new HashMap<>()); Collections.sort(res, Collections.reverseOrder()); return res.get(0); } //DFS + memoziation, Time average O(Cn^2) when memoization takes places, Space O(Cn^2) private static List<Integer> helper(List<Integer> t, Map<List<Integer>, List<Integer>> map) { if (t.size() <= 1) return t; if (map.containsKey(t)) return map.get(t); List<Integer> res = new ArrayList<>(); for (int i = 1; i < t.size(); i++) { List<Integer> left = helper(t.subList(0, i), map); List<Integer> right = helper(t.subList(i, t.size()), map); for (int a : left) { for (int b : right) { res.add(a + b); res.add(a - b); res.add(a * b); if (b != 0) res.add(a / b); } } } map.put(t, res); //map stores (token, partial result) pair return res; } public static void main(String[] args) { List<Integer> list = Arrays.asList(3,4, 5,1); System.out.println("Input: " + list); System.out.print("Max possible value is: "); System.out.println(evaluateExpressions(list)); } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | //Recursion wrapper, Time O(Cn^2), Space O(Cn^2), Cn is Catalan number, n is array length function evaluateExpressions(tokens) { var map = new Map(); var res = helper(tokens, map); res.sort((a, b) => b- a) ; return res[0]; } //DFS + memoziation, Time average O(Cn^2) when memoization takes places, Space O(Cn^2) function helper(t, map) { if (t.length <= 1) return t; if (map.has(t)) return map.get(t); var res = new Array(); for (let i = 1; i < t.length; i++) { let left = helper(t.slice(0, i), map); let right = helper(t.slice(i, t.length), map); for (let a of left) { for (let b of right) { res.push(a + b); res.push(a - b); res.push(a * b); if (b != 0) res.push(a / b); } } } map.set(t, res); //map stores (token, partial result) pair return res; } let list = [3,4,5,1]; console.log(list); console.log("Max possible value is: "); console.log(evaluateExpressions(list)); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #Recursion wrapper, Time O(Cn^2), Space O(Cn^2), Cn is Catalan number, n is array length def evaluateExpressions(tokens) : map = {} res = helper(tokens, map) res.sort(reverse=True) return res[0] #DFS + memoziation, Time average O(Cn^2) when memoization takes places, Space O(Cn^2) def helper(t, map) : if len(t) <= 1 : return t if tuple(t) in map.keys(): return map[tuple(t)] res = [] for i in range(1, len(t)) : left = helper(t[:i], map) right = helper(t[i:len(t)], map) for a in left: for b in right: res.append(a + b) res.append(a - b) res.append(a * b) if (b != 0) : res.append(a / b) map[tuple(t)]= res #map stores (token, partial result) pair return res list = [3,4,5,1] print(list) print("Max possible value is: ") print(evaluateExpressions(list)) |
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
Combinations of adding parentheses
It is backtracking.
