Combinations of parentheses and operators

Combinations of adding operators and parentheses is to add operators such as +, -, *, / and parentheses () to numbers. In infix expression, the operator * and / have higher precedence than + and – . While parentheses can override the normal precedence of operators. Anything in parentheses will be calculated first.

When dealing with parentheses, we have to mention Catalan number. Catalan numbers are a sequence of natural numbers that occur in various counting problem. The first few Catalan numbers for n = 0, 1, 2, 3, 4, 5 … Cn = 1, 1, 2, 5, 14, 42, … There are many counting problems in combinatorics whose solution is given by the Catalan numbers. Adding parentheses are one of commonly seen example of Catalan numbers. In this post, we provides solutions to two questions that involving adding parentheses and Catalan numbers.


1. Generate all possible n pairs valid parentheses

Combinations of n-pairs parentheses is to print all possible expressions that containing n pairs of valid parentheses. When n=2, there are 2 possible expressions, (()), ()(). When n = 3, there are 5 possible expressions ((())), ()(()), ()()(), (())(), (()()). You can see the number of expressions containing n pairs of parentheses are matched with Catalan number Cn.


generate parentheses

Catalan numbers often involve recursively defined objects. The intuitive approach for this question is to use recursion. From empty string, we can build the expression by adding “(” to the left and “)” to the right. Meanwhile we track the number for adding actions. To add left, starting from n, each time we decrease n by 1 until 0. For the right, it is based on whether there are unmatched “(” left. When both are 0, we can return back from the recursion.

In following solution, the recursion method helper has parameters open and close to keep track the number of adding left parentheses and right parentheses. The open starts with input n. The close starts with 0. The helper calls itself twice, the first one is to add left parenthesis, decrease open and increases close by 1. The second call is to add right parenthesis. It uses the same open number and decreases close to match with the left parentheses. The time complexity is Catalan number Cn. n is input number.

Java

JavaScript

Python

Doodle

generate n pairs valid parentheses doodle

Output:
All possible of 3 pairs valid parentheses:
((()))
(()())
(())()
()(())
()()()

O Notation:
Time complexity:O(Cn), Cn is Catalan number, n is input number
Space complexity: Space O(Cn)


2. Evaluate all possible expressions with combinations of adding operators and parentheses

Combinations of adding operators and parentheses has something in common with the above question – adding valid parentheses to n numbers. Naturally we use recursion. For each number in the input, we split the input list into two sub lists. The recursion method helper calls itself twice, one for left side of current number; one for the right side of the list. They return the partial result from the further divided sub lists. This is the same technique as depth first search (DFS) in tree and graph. Then we use this partial results as operands and apply 4 operators +, – * and /.

With recursion, the time complexity is exponential. In order to avoid overlapping in recursion, we apply memoization. A HashMap<List, List> is used to store partial results. The keys of the map 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]. The values are the results after applying four operators (+ – * /).

At the beginning of the helper method, it checks whether the input list is in the HashMap’s key. If it is, it will return the result directly without going further. The calculation with 4 operators are constant, which will be ignored in the time complexity. The overall time complexity after memoization is (Cn)^2, n is numbers in the input array. Please note due to the variations of how much memoization can be applied for different input numbers, the time complexity Cn^2 indicates the level of the complexity not exact number. Based on the formula of Catalan number, the time complexity can grow very fast, which cause overflow.

Once we have all the possible results from the expressions, we can find the max possible one and return.

Google Interview Question (CareerCup):
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
Java Coding Interview Pocket Book (2nd Edition)

Comments are closed