Prefix notation to infix notation in Python

Question

I am writing a small calculator (with prefix notation) and I'm curious how I'd convert prefix notation to infix notation. I currently have a function, but it's being weird, and I'm not sure how to fix it. By being weird, I mean that if given ['+', x, y] it will return (() + x + () + y) which is confusing me. Here's the code.

def pre_in(read):
    #print read
    tempOp = read[0]
    body = read[1:]
    expr = []
    for i in range(len(body)-1):
        if not isinstance(body[i], list) and body[i] != " ":
            expr.append(str(body[i]))
            expr.append(tempOp)
        else:
            expr.append(str(pre_in(body[i])))
            expr.append(tempOp)
    try:
        if not isinstance(body[-1], list):
            expr.append(str(body[-1]))
        else:
            expr.append(str(pre_in(body[-1])))
    except:
        pass
    if expr != None: return "("+' '.join(expr)+")"

What am I doing wrong?

I don't understand the problem (and your code). If I have `foo = ['+', x, y]`, the expression `[foo[1], foo[0], foo[2]]` will result in `[x, '+', y]`. Isn't that what you want? In case of nested expressions, you'd have to do simple recursion. Maybe you should give a clearer and more complex example of your input and expected output. — Björn Pollex, Jun 27 '11 at 20:12
you could also try using a stack, that is a common way of doing prefix<->infix, the stack would also solve nested expressions. — Hunter McMillen, Jun 27 '11 at 20:13
appears to be related to previous question by same guy: http://stackoverflow.com/questions/6338440/small-language-in-python — Warren P, Jun 27 '11 at 20:15
Space_C0wb0y: i was aiming for something that can handle multiple terms, like `['+', 2, 3, 4, 5]` would yield `2 + 3 + 4 + 5` — tekknolagi, Jun 27 '11 at 20:22
@Warren actually no. this is about prefix, the other was about postfix. i'm rethinking the structure of the language — tekknolagi, Jun 27 '11 at 20:22
@tekknolagi: The prefix notation of `2+3+4+5` would be `+ + + 2 3 4 5`. — Hyperboreus, Jun 27 '11 at 20:54
@tekknolagi In Lisp for sure with arbitrary parameter count. But I guess you will find as many prefix notation 'standards' as you find 'standards' for anything else. Some equivalent, some contradictory and some... — Hyperboreus, Jun 28 '11 at 15:29

Hyperboreus · Accepted Answer · 2011-06-27T20:41:34.687

5

Actually your code works fine.

print pre_in ( ['+', 8, 9] )

yields

(8 + 9)

EDIT: As the others have stated, maybe you want to use a stack. Here a simple sandbox implementation with some examples (it produces many parenthesis but those don't hurt):

class Calculator:
    def __init__ (self):
        self.stack = []

    def push (self, p):
        if p in ['+', '-', '*', '/']:
            op1 = self.stack.pop ()
            op2 = self.stack.pop ()
            self.stack.append ('(%s %s %s)' % (op1, p, op2) )
        elif p == '!':
            op = self.stack.pop ()
            self.stack.append ('%s!' % (op) )
        elif p in ['sin', 'cos', 'tan']:
            op = self.stack.pop ()
            self.stack.append ('%s(%s)' % (p, op) )
        else:
            self.stack.append (p)

    def convert (self, l):
        l.reverse ()
        for e in l:
            self.push (e)
        return self.stack.pop ()

c = Calculator ()

print c.convert ( ['+', 8, 9] )
print c.convert ( ['!', 42] )
print c.convert ( ['sin', 'pi'] )
print c.convert ( ['+', 'sin', '/', 'x', 2, 'cos', '/', 'x', 3] )

edited Jun 27 '11 at 20:41

answered Jun 27 '11 at 20:16

Hyperboreus

31,997
9
47
87

i normally run it on expressions with variables, like: ['+', x, y] – tekknolagi Jun 27 '11 at 20:20
Also `x = 8; y = 9; print pre_in ( ['+', x, y] )` runs fine. – Hyperboreus Jun 27 '11 at 20:23
what i meant was ['+', 'x', 'y'] – tekknolagi Jun 27 '11 at 20:24
i'm sorry, i was feeding it bad input. – tekknolagi Jun 27 '11 at 20:26
how do i close this for the reason that it was a bad question? – tekknolagi Jun 27 '11 at 20:27
I believe that without the call to `l.reverse()`, this would be a correct parser for _postfix_ notation - however, prefix notation is _not_ the reverse of postfix notation. For example, `x / (y + z)` is `x y z + /` in postfix notation and `/ x + y z` in prefix notation. However, a proper prefix parser would look very similar to what you have. – Aasmund Eldhuset Jun 27 '11 at 23:49
1

Aren't `/ x + y z` and `/ + y z x` equivalent? – Hyperboreus Jun 28 '11 at 15:28

martega · Answer 2 · 2012-06-22T20:11:19.830

1

Here's a fairly simple recursive solution.

def prefix_to_infix(expr):
    if type(expr) != type([]):
        # The expression is a number or variable.
        return str(expr)
    elif len(expr) == 2:
        # This is an operator expression with 1 argument.
        return str(expr[1])
    else:
        # This is an operator expression with 2 or more arguments.
        operator = expr[0]
        left_arg = prefix_to_infix([operator] + expr[1:-1])
        right_arg = prefix_to_infix(expr[-1])
        return "({0}{1}{2})".format(left_arg, operator, right_arg)

# prefix_to_infix(['+',1,2,3,4,5]) = '((((1+2)+3)+4)+5)'
# prefix_to_infix(['+',1,2,['*',3,4,5],6,7,8]) = '(((((1+2)+(3*4*5))+6)+7)+8)'

edited Jun 22 '12 at 20:11

answered Jun 22 '12 at 20:05

martega

2,103
2
21
33

But with trig functions and such? – tekknolagi Jun 22 '12 at 21:09
I was working under the assumption that the syntax for your prefix expressions were of the form ['operator', arg1, arg2, ... ,argN]. I also assumed that all operators were binary operators and left associative. It wouldn't really make sense to make trig functions in infix notation but maybe I'm just misunderstanding your question. – martega Jun 23 '12 at 00:43

score 1 · Answer 3 · answered Jun 27 '11 at 20:13

If your aim is not to develop the algorithm on your own, go to this page. There are links to two pages which explain the infix->postfix and postfix->infix algorithm. (And also, if you want to know how the algorithms are implemented in javascript, you can take a look at the source code of the page.)

mjv · Answer 4 · 2017-07-11T23:31:40.533

1

At the risk of being a bit overkill for this kind of simple parsing/conversion jobs, you may want to look at pyparsing.

edited Jul 11 '17 at 23:31

answered Jun 27 '11 at 20:22

mjv

73,152
14
113
156

Prefix notation to infix notation in Python

4 Answers4