Infix to prefix conversion in Python

Question

I wanted to make an infix to prefix converter. When I ran the code, the operator in the string sends all the operators in the beginning of the returning string.

How can I fix the code below?

class Stack:
    def __init__(self):
        self.a = []
    def isEmpty(self):
        return self.a == []
    def push(self,i):
        self.a.append(i)
    def pop(self):
        return self.a.pop()
    def peek(self):
        return self.a[len(self.a)-1]

def infixToPrefix(s):
    prec = {'/':3,'*':3,'+':2,'-':2,'^':4,'(':1}
    opStack = Stack()

    prefixList = []
    temp = []
    for token in s:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            prefixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                temp.append(topToken)
                topToken = opStack.pop()
            prefixList = temp + prefixList
            temp = []
        else:
            while (not opStack.isEmpty()) and \
                  (prec[opStack.peek()]>= prec[token]):
                temp.append(opStack.pop())
            prefixList = temp + prefixList
            temp = []
            opStack.push(token)
    while not opStack.isEmpty():
        temp.append(opStack.pop())
    prefixList = temp + prefixList
    return ''.join(prefixList)
print infixToPrefix("(A+B)*C-(D-E)*(F+G)")

Your code is invalid. The last line while... is syntactically incorrect. — user764357
– user764357, Commented Sep 22, 2014 at 6:34
Is the expected output: -*+ABC*-DE+FG ? Have you tried putting some print statements into your Stack methods and strategic places through your loop so you can follow what's going on? Have you tried running through your algorithm by hand, with pencil & paper, to make sure it does what you expect it to? — PM 2Ring
– PM 2Ring, Commented Sep 22, 2014 at 9:27
I should also mention that your digit tokenizing needs fixing, unless you are only feeding single digit numbers to the program. — PM 2Ring
– PM 2Ring, Commented Sep 22, 2014 at 9:30

0 _ · Accepted Answer · 2015-01-23 08:12:09Z

1

Don't reinvent the wheel. Use a parser generator instead. For example, PLY (Python lex-yacc) is a good option. You can start by looking at a basic example and either do the conversion within the production rules themselves, or produce an abstract syntax tree equipped with flattening methods that return prefix, infix, or postfix notation. Note that the difference between these three is whether the operator is inserted in pre-, in between, or post-order during a depth-first traversal of the syntax tree (implemented either as a single function or recursively -- the latter leads to simpler and more modular code).

answered Jan 23, 2015 at 8:12

0 _

11.8k12 gold badges85 silver badges112 bronze badges

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

1 Comment

0 _ Over a year ago

One hand-crafted solution can be found here.

mnemonicj · Accepted Answer · 2016-09-30 09:34:44Z

It might be late to post this answer, but I'm also leaving this as a reference for anyone else. It seems OP, that you already solved the issue when converting from infix to postfix. If that's the case, you can use that same algorithm and code to convert your text to a prefix notation.

All you'd need to do is invert your text first, and then pass that text through your algorithm. Once you invert your text, you'll also store your text in your Stack already inverted. After you've processed this, you need to re-invert your text again to it's original form and you'll get your prefix notation.

Be sure to keep track of what you compare in your dictionary though, you'll no longer compare your operands with the "(".

Hope this helps.

Collectives™ on Stack Overflow

Infix to prefix conversion in Python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related