Oeufcoque Penteano - 1 year ago 56

Python 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`

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.

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 Source

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
```