How to print all possible balanced parentheses for an expression?

by

Here is actual code in Python, using generators to avoid using too much memory.

#! /usr/bin/python

def parenthesized (exprs):
    if len(exprs) == 1:
        yield exprs[0]
    else:
        first_exprs = []
        last_exprs = list(exprs)
        while 1 < len(last_exprs):
            first_exprs.append(last_exprs.pop(0))
            for x in parenthesized(first_exprs):
                if 1 < len(first_exprs):
                    x = '(%s)' % x
                for y in parenthesized(last_exprs):
                    if 1 < len(last_exprs):
                        y = '(%s)' % y
                    yield '%s%s' % (x, y)

for x in parenthesized(['a', 'b', 'c', 'd']):
    print x

More Related Contents:

  1. Expand a random range from 1–5 to 1–7
  2. How to find list of possible words from a letter matrix [Boggle Solver]
  3. How to find all combinations of coins when given some dollar value [closed]
  4. Finding a single number in a list [duplicate]
  5. Algorithm to generate anagrams
  6. How to generate Sudoku boards with unique solutions
  7. Efficiently reverse the order of the words (not characters) in an array of characters
  8. Programming Riddle: How might you translate an Excel column name to a number?
  9. Fastest algorithm for circle shift N sized array for M position
  10. Complexity of absolute difference and sum
  11. What is tail recursion?
  12. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  13. Getting the closest string match
  14. How to compute Discrete Fourier Transform?
  15. How does finding a cycle start node in a cycle linked list work?
  16. Efficient list intersection algorithm
  17. How to efficiently build a tree from a flat structure?
  18. What would cause an algorithm to have O(log log n) complexity?
  19. search for interval overlap in list of intervals?
  20. robust algorithm for surface reconstruction from 3D point cloud?
  21. 3D Least Squares Plane
  22. Is there ever a good reason to use Insertion Sort?
  23. Shortest distance between points algorithm
  24. Amortized complexity in layman’s terms?
  25. In Order Successor in Binary Search Tree
  26. What is the advantage to using Bloom filters?
  27. algorithm for index numbers of triangular matrix coefficients
  28. Search a sorted 2D matrix [duplicate]
  29. Is it possible to find two numbers whose difference is minimum in O(n) time
  30. Creating combinations that have no more one intersecting element

Leave a Comment