CODEWITHSUNDEEP
pythonstack
Prashin Jeevaganth
Prashin Jeevaganth

Reputation: 1363

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.

Upvotes: 1

Views: 2045

Answers (2)

learner
learner

Reputation: 1

def is_operand(c):
    return c.isdigit()

def prefix_to_infix(expression):
    stack = []
    for c in expression[::-1]:
        if is_operand(c):
            stack.append(c)
        else:
            o1=stack.pop()
            o2=stack.pop()
            if c== "+":
                element=   o1 + c + o2
                stack.append(element)
            if c=="-":
                element= o1 + c +o2 
                stack.append(element)
            if c== "*":
                element=  o1 + c +o2 
                stack.append(element)
    return stack
def evaluate(stack):
    expression=str(stack[0])
    return eval(expression)

Upvotes: 0

sciroccorics
sciroccorics

Reputation: 2427

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

Upvotes: 1

Related Questions