Generating all possible "unique" RPN (Reverse Polish notation) expressions

I want to generate in Python all possible RPN (Reverse Polish notation) expressions, that use letters from an input list (such as ['a', 'b', 'c']) and contain operators ['+', '-', '*', '/'].

My idea was that we can add elements to the current expression until one of the following happens: either we've used all letters or expression is complete (i.e. we can't add more operators).

So I wrote the following functions:

1)

'''
The function returns True if we can add operator to current expression:
we scan the list and add +1 to counter when we meet a letter
and we add -1 when we meet an operator (it reduces
last two letters into 1 (say ab+ <--> a + b)
''' 
def can_add_operator(string_):
    n = 0
    for letter in string_:
        if letter not in ['+', '-', '*', '/']:
            n += 1
        else:
            n -= 1
    result = n > 1
    return result


    can_add_operator('ab*c+')) #False
    can_add_operator('ab*c')  #True

2)

'''
The function returns a list, that contains operators and
letters, one of which we can add to the current expression.
'''

def possible_elements(items, string_):
    #list of all letters that we have not used yet
    result =  [x for x in items if x not in string_]
    if can_add_operator(string_):
        result = ["+", "-", "*", "/"] + result
    return result

letters = ['a', 'b', 'c', 'd']
possible_elements(letters, 'ab*c') #['+', '-', '*', '/', 'd']
possible_elements(letters, '') #['a', 'b', 'c', 'd']
possible_elements(letters, 'ab*c+d+') #[]

3) Next I wrap it into recursion:

#exp -- current expression, base of recursion is exp = ''
def rec(exp, Final_sol = []):
    elements_to_try = possible_elements(letters, exp)
    for i in elements_to_try:
        if len(possible_elements(letters, exp + i)) == 0:
            Final_sol.append(exp + i)
        else:
            rec(exp+i, Final_sol)
    return Final_sol

#we start with an empty string
Final_sol = rec('')
print(len(Final_sol)) #7680

There are two difficulties with that function:

1. The first one is that if there are repeated letters in list of letters, it won't return all possible results.

   For example if letters = ['a', 'b', 'a']:

   Final_sol = rec('')
   print(len(Final_sol)) #32
   str(Final_sol)
   >> "['ab+', 'ab-', 'ab*', 'ab/', 'ba+', 'ba-', 'ba*', 'ba/', 'ba+', 'ba-', 
   'ba*', 'ba/', 'ab+', 'ab-', 'ab*', 'ab/', 'ab+', 'ab-', 'ab*', 'ab/', 'ba+', 
   'ba-', 'ba*', 'ba/', 'ba+', 'ba-', 'ba*', 'ba/', 'ab+', 'ab-', 'ab*', 
    'ab/']"
   
   

   So the output missing 'ab+a+' and so on. But I do want to return all possible combinations in that case too.

2. The second problem is that there are many "equivalent" strings in the output. Since we have the commutative and associative properties in prefix form, expressions like ab+c+/abc++/ca+b+ should be considered as equivalent: I want only one of each group in the output of the function rec().

How could we change the functions above to overcome such difficulties? What is the most elegant solution to problem?

from Generating all possible "unique" RPN (Reverse Polish notation) expressions