Algorithm for Generating Well-Formed Formulas in Polish Notation

Question

I am trying to write an algorithm that constructs only well-formed formulas in PN. I have some list of symbols for binary connectives, unary connectives, and propositional variables (trying to make program robust for any length).

Here Polish Notation mentions an algorithm to test whether or not it is well-formed. It is much easier to make it so it is well-formed and not to have to test it later for computational purposes. It isn't difficult to make all possible permutations and then test. When looking EKKCprCqrKCpsCqsCApqKrs on the provide link, it seemed that I could "smoosh" the words EKKCCKCCCAK and prqrpsqspqrs at all possible places by creating a bunch of insertion sights, but not sure if this is always correct or can get every possible combination. I am teaching myself these things and having a difficult time thinking how to approach this. I am judging the answer based on explanation and also efficiency to generating wff's.

Answer 1

Here's one solution in Python that generates formulae up to a certain depth. To keep clutter to a minimum, no arguments are passed to the script, but adding such parameters and passing in signature and depth should be easy. This version seems to work with both Python 2.7 and 3.5.

""" Enumerates wffs in Polish notation up to prescribed depth."""
from __future__ import print_function
from itertools import product

def generate(depth):
    if depth == 1:
        return variables
    else:
        wfflist = []
        for letter, arity in symbols:
            extensions = [[letter]]
            if arity > 0:
                extensions.extend([generate(depth-1)] * arity)
                wfflist.extend([list(w) for w in product(*extensions)])
            else:
                wfflist.extend(extensions)
        return wfflist

functions = ['C', 'K', 'A', 'E', 'D', 'N']
arities   = [ 2,   2,   2,   2,   2,   1 ]
variables = ['p', 'q', 'r'];
symbols = list(zip(functions + variables, arities + [0] * len(variables)));

for wff in generate(3): print(wff)