Python: Iterate through balanced parentheses on an expression

Question

I found some code to iterate through arithmetic operators across a static, excecutable formula in Python:

from itertools import product
import numpy as np

operands = np.array(['a', 'b', 'c', 'd', 'e'])
operators = np.array([ '&', '|'])

for opers in product(operators, repeat=len(operands)-1):

    formula = [ str(operands[0]) ]

    for op, operand in zip(opers, operands[1:]):
        formula.extend([op, str(operand)])

    formula = ' '.join(formula)    
    print(formula)

I modified the code from the link slightly, my code (above) outputs:

a & b & c & d & e
a & b & c & d | e
a & b & c | d & e
a & b & c | d | e
a & b | c & d & e
a & b | c & d | e
a & b | c | d & e
a & b | c | d | e
a | b & c & d & e
a | b & c & d | e
a | b & c | d & e
a | b & c | d | e
a | b | c & d & e
a | b | c & d | e
a | b | c | d & e
a | b | c | d | e

For each expression in this output, I would like to iterate through and print every possible combination of balanced parentheses.

For example, for the first expression we would get:

(a & b) & c & d & e
((a & b) & c) & d & e
(a & (b & c)) & d & e
((a & b) & c & d) & e
((a & b) & (c & d)) & e
((a & b & c) & d) & e
(((a & b) & c) & d) & e
((a & (b & c)) & d) & e
...

How might I go about doing this (while keeping execution time to a minimum)?

Bonus: Remove/prevent any duplicates

I see there was a similar question here, but the question/answers do not include operators in the output expressions.

That's going to generate quite a lot of options... what are you actually trying to accomplish? There's a decent chance this is [an XY problem](https://meta.stackexchange.com/q/66377/248627). — ChrisGPT was on strike, Apr 18 '21 at 16:51
Once it's complete, I intend on removing expressions with duplicate truth table valuations. I would like a list of every possible combination of expressions given a set of operators and operands (in my application, these will be replaced with comparison statements) — Craig Nathan, Apr 18 '21 at 16:55
For operations like this, stick with lists. Iteration on arrays is slower; and `numpy` does not provide any added string functionality. — hpaulj, Apr 18 '21 at 17:07
Boolean SAT is the original NP-Complete problem https://en.wikipedia.org/wiki/Boolean_satisfiability_problem — user1462442, Apr 18 '21 at 17:36

score 0 · Accepted Answer · answered May 31 '21 at 21:26

I ended up using the answer here:

https://stackoverflow.com/a/6447533/12814841

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

Python: Iterate through balanced parentheses on an expression

1 Answers1