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]
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
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/+*
