Python prefix to infix notation using a stack data structure

I have an assignment problem on using a stack data structure to solve problems. I am prompted to make the following stack function.

Task: Using the stack you created, write the function prefix_infix that takes in a prefix expression (represented as a list) and returns the expression in fully parenthesized infix notation. Consider expressions involving only binary operators(+,-,*,/) You may find information regarding prefix here: http://en.wikipedia.org/wiki/Polish_notation

def make_stack(): 
    stack=[]
    def helper(*args): 
        if args[0]=='push': 
            stack.append(args[1])
        elif args[0]=='peek': 
            return (stack[-1]) 
        elif args[0]=="pop": 
            return (stack.pop())
        elif args[0]=="size": 
            return (len(stack))
    return helper 



def prefix_infix(lst): 
    stk=make_stack() 
    def helper(lst):
        if type(lst)==int: 
            stk('push',str(lst))
        elif lst in ('+','-','*','/'): 
            left=stk('pop')
            right=stk('pop')
            element="("+left+" "+lst+" "+right+")"
            stk('push',element)
        else:
            return helper(lst[2]),helper(lst[1]),helper(lst[0]) 
    helper(lst)
    return stk('pop')

prefix_infix(['+',['*',5,4],['-',2,1]])
#Output: "((5 * 4) + (2 - 1))"

prefix_infix(['-',['*',5,4],['-',['/',1,45],['+',1,1]]])
#Output:((5 * 4) - ((1 / 45) - (1 + 1)))

I somehow got my code to produce the correct output, but I’m not very confident on my approach as I did it with a recursion but I do not know what’s the right way to do it with a recursion (my recursive call with , seems haphazard). Can someone suggest some other versions of code that I can write to make it easier to comprehend? I can’t really visualise the stack, most of the time I’m just lucky with my recursive functions.

Answer

If you use recursion, you don’t have to manage your stack manually (recursion manages the stack for you). For instance:

def prefix_infix(expression):
    if isinstance(expression, list):
        op, left, right = expression
        return '(' + prefix_infix(left) + op + prefix_infix(right) + ')'
    else:
        return str(expression)

print(prefix_infix(['+',['*',5,4],['-',2,1]]))
print(prefix_infix(['-',['*',5,4],['-',['/',1,45],['+',1,1]]]))

Output:

((5 * 4) + (2 - 1))
((5 * 4) - ((1 / 45) - (1 + 1)))

EDIT (after comment): Here is the version that adds numerical evaluation of the expression:

def eval_prefix(expression):
  return eval(prefix_infix(expression))

Output:

eval_prefix(['+',['*',5,4],['-',2,1]])) # --> 21
eval_prefix(['-',['*',5,4],['-',['//',9,3],['+',1,1]]])) # --> 19