Good Infix to Prefix implementation in Python that

Question

I have been looking without much luck for an implementation of Python that converts infix to prefix that ranges on a sufficient amount of arithmetic and logic operators and care about its properties on a good python implementation. More specifically I am interested on the operators that would appear on a conditional clause of a C program. (e.g. it would transform a > 0 && b > 1 in prefix.

Since I am still newbie to Python I would appreciate if anyone could offer me the implementation or some tips on going about this.

I found an implementation around the internet that I lost the reference for (below), but it only cares about the more simple operators. I am a little clueless on how to do this on this version, and if anyone knew a version that already included all the operators I would appreciate to avoid any operator being ignored by accident.

Such implementation should also account for parenthesis.

Please comment if you need more details!

Thank you.

def parse(s):
for operator in ["+-", "*/"]:
    depth = 0
    for p in xrange(len(s) - 1, -1, -1):
        if s[p] == ')': depth += 1
        if s[p] == '(': depth -= 1
        if not depth and s[p] in operator:
            return [s[p]] + parse(s[:p]) + parse(s[p+1:])
s = s.strip()
if s[0] == '(':
    return parse(s[1:-1])
return [s]

Answer 1

I don't quite have time to write an implementation right now, but here is an implementation I wrote that converts infix to postfix (reverse polish) notation (reference: Shunting-yard algorithm). It shouldn't be too hard to do the modify this algorithm to do prefix instead:

• ops is the set() of operator tokens.
• prec is a dict() containing operand tokens as keys and an integer for operator precedence as it's values (e.g { "+": 0, "-": 0, "*": 1, "/": 1})
• Use regular expressions to parse a string into a list of tokens.

(really, ops and prec could just be combined)

def infix_postfix(tokens):
    output = []
    stack = []
    for item in tokens:
        #pop elements while elements have lower precedence
        if item in ops:
            while stack and prec[stack[-1]] >= prec[item]:
                output.append(stack.pop())
            stack.append(item)
        #delay precedence. append to stack
        elif item == "(":
            stack.append("(")
        #flush output until "(" is reached
        elif item == ")":
            while stack and stack[-1] != "(":
                output.append(stack.pop())
            #should be "("
            print stack.pop()
        #operand. append to output stream
        else:
            output.append(item)
    #flush stack to output
    while stack:
        output.append(stack.pop())
    return output

Answer 2

I am reading An Introduction to Data Structures and Algorithms - Jean-Paul Tremblay, and I wrote a python implementation of a program described in that book for infix to RPN.

SYMBOL = ['+', '-', '*', '/', '^', 'VAR', '(', ')']
INPUT_PRECEDENCE = [1, 1, 3, 3, 6, 7, 9, 0]
STACK_PRECEDENCE = [2, 2, 4, 4, 5, 8, 0, None]
RANK = [-1, -1, -1, -1, -1, 1, None, None]

INFIX = '(a+b^c^d)*(e+f/d)'
POLISH_TEST = 'abcd^^+efd/+*'

def getIndex (symbol):
    if (symbol.isalpha()):
        index = 5
    else:
        index = SYMBOL.index (symbol)
    return index

def InfixToReversePolish (INFIX):
    #initialize
    POLISH = []
    STACK = []
    #append ')' to infix
    INFIX = INFIX + ')'
    #push '(' on to the stack
    STACK.append (SYMBOL[6])
    for i in range(0, len(INFIX)):
        #read the next char in the infix
        NEXT = INFIX[i]
        #what is the index of next in the precedence and rank tables?
        index = getIndex (NEXT)
        if (len (STACK) == 0):
            print ('Invalid input string')
            return
        #if we encounter ')', we pop the stack till we find '('. we discard both '(' and ')'
        if index == 7:
            ch = STACK.pop()
            while getIndex (ch) != 6:
                POLISH.append (ch)
                ch = STACK.pop()
            continue
        #while next input precedence is less than or equal to the top stack precedence    
        while (INPUT_PRECEDENCE[index] <= STACK_PRECEDENCE[getIndex(STACK[len(STACK) - 1])]):
            POLISH.append (STACK.pop())
        #push next on to the stack
        STACK.append (NEXT)
    return POLISH

ex = ''.join (InfixToReversePolish (INFIX))
print ('Reverse Polish Expression is', ex)

Reverse Polish Expression is abcd^^+efd/+*