python - How do I generate all possible words of a regular expression with the following rules and syntax? -

how generate possible words of regular expression following rules , syntax:

• the user inputs alphabet;
• the user inputs expression;
• any character that's not ()*+ or space can part of alphabet;
• the + character chooses between character or sequence on left or 1 on right;
• the * character allows 1 or more repetitions of character or sequence on left;
• two alphabetic characters in sequence concatenated;
• parentheses may change precedence.

i'm getting alphabet , expression strings user, , casting python lists. proceed simple validation tests on both, based on rules above.

after that, currently, algorithm generates correctly words of expressions without parentheses. , here's problem: haven't found yet way manage parentheses correctly generate words. see, have 2 options:

1) find way calculate possible words directly original expression, or

2) somehow eliminate parentheses , have current algorithm solve it.

i wonder if can first option done using kind of recursive function, although still don't know how. thoughts?

here's code far (sorry comments in portuguese, brazilian here):

alphabetinput = input(     "informe os caracteres alfabeto (obs.: os símbolos '(', ')', '+' e '*' são caracteres reservados):\n") alphabetinput = alphabetinput.strip()  # remove os espaços em branco da string alphabetinput = list(alphabetinput)  # transforma string numa lista  # remove duplicidades alfabeto alphabet = [] c in alphabetinput:     if c not in alphabet:         alphabet.append(c)  c in alphabet:     if c in "()*+":         print("alfabeto inválido (obs.: os símbolos '(', ')', '+' e '*' são caracteres reservados).")         exit()  expression = input("informe expressão regular:\n") expression = expression.strip()  # remove os espaços em branco da string expression = list(expression)  # converte string numa lista  counter = 0  # controle dos parênteses abertos e fechados no loop seguir  c in (expression):     if c == "(":         counter = counter + 1  # +1 significa que um parêntese foi aberto     elif c == ")":         counter = counter - 1  # -1 significa que um parêntese foi fechado     else:         pass     if counter < 0:         print("expressão inválida. um parêntese foi fechado sem ter sido aberto antes.")         exit()  # se o contador maior que zero, significa que há mais parênteses abertos que fechados # se menor que zero, terá caído no 'if' dentro loop acima # se igual zero, estará ok if counter > 0:     print("expressão inválida: existem parênteses em aberto.")     exit()  # testa validade da expressão com base na existência sequências inválidas de caracteres if (expression[0] == "+" or expression[len(expression) - 1] == "+"):  # testa existência de "+" no começo e no fim da expressão     print("expressão inválida: existem adições lógicas (+) sem um dos operandos.")     exit() else:     in range(0, len(expression)):         if (expression[i] == "+"):             if (expression[i + 1] == "+" or expression[i + 1] == "*" or expression[i + 1] == ""):                 print("expressão inválida: existem adições lógicas (+) sem um dos operandos.")                 exit()  #### fim da seÇÃo 1 ####  #### seÇÃo 2: teste de pertinÊncia dos sÍmbolos informados ao alfabeto informado ####  # obs.: 'expression' já é uma lista, o casting é feito para que o conteúdo modificado em uma não o seja na outra testexpression = list(expression)  # os loops seguintes marcam e removem os espaços em branco e caracteres especiais da expressão, # e em seguida testam se os símbolos usados pertencem ao dicionário informado in range(len(testexpression)):     if testexpression[i] in " ()+*":         testexpression[i] = "marked"  while "marked" in testexpression:     testexpression.remove("marked")  # testa se os símbolos usados fazem parte alfabeto informado c in testexpression:     counter = 0     cc in alphabet:         if c == cc:             counter += 1;     if counter == 0:     # se esse contador igual zero, significa que não há correspondência entre o símbolo da expressão e o alfabeto         print("expressão informada possui símbolos que não pertencem ao alfabeto.")         exit()  #### fim da seÇÃo 2 ####  #### seÇÃo 3: geraÇÃo das palavras ####  possibilities = [[]]  # vetor que receberá os subvetores com cada possiblilidade possibilitiescounter = 0  # contador de possibilidades, toda vez que ele é incrementado um novo subvetor é criado  # monta e arranja palavras geradas no vetor 'possibilities' in range(0, len(expression)):     if expression[i] in alphabet:         possibilities[possibilitiescounter].append(expression[i])     if expression[i] == "+":         possibilities.append([])         possibilitiescounter += 1  # imprime todas palavras geradas na tela yetanothercounter = 0 words = []  # lista final das palavras l in possibilities:     words.append("".join(str(x) x in l))     print("palavra ", yetanothercounter + 1, ":", words[yetanothercounter])     yetanothercounter += 1 

so, came solution using library called exrex: https://github.com/asciimoo/exrex

it has function generate wanted.