Python prefix to infix notation using a stack data structure

Question

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.

Are you searching for an optimisation for your code or another approach ? — Chiheb Nexus
– Chiheb Nexus, Commented Apr 21, 2018 at 14:47
Another approach perhaps, I'm not really comfortable with manipulating the stack, I kinda drew out what I need to do then wrote the code, but doesnt seem too convincing how it worked out. — Prashin Jeevaganth
– Prashin Jeevaganth, Commented Apr 21, 2018 at 14:55

sciroccorics · Accepted Answer · 2018-04-21 15:53:51Z

1

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

edited Apr 21, 2018 at 15:53

answered Apr 21, 2018 at 14:50

sciroccorics

2,4271 gold badge11 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Prashin Jeevaganth Over a year ago

yes, my assignment's test cases uses nested lists, I find it weird too

Prashin Jeevaganth Over a year ago

could u do it without the formatting characters? Or better still try to use the stack structure provided? I wasn't really taught on those skills, maybe I was expected to do it without them.

sciroccorics Over a year ago

@Prashin: OK, I replaced the formatting characters by pure string concatenation

Prashin Jeevaganth Over a year ago

I actually have a burning question on how I can change the code if I want to evaluate the results in the string form, say ((5 * 4) + (2 - 1)), is there a concise way of writing it besides writing conditional statements to match the operator in each bracket?

sciroccorics Over a year ago

@Prashin: I've edited my answer to add a solution for evaluation

learner · Accepted Answer · 2020-11-22 18:49:14Z

0

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)

answered Nov 22, 2020 at 18:49

learner

1

Collectives™ on Stack Overflow

Python prefix to infix notation using a stack data structure

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related