Advertisement
Guest User

infix to prefix gone wrong

a guest
Sep 22nd, 2014
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.28 KB | None | 0 0
  1. class Stack:
  2.     def __init__(self):
  3.         self.a = []
  4.     def isEmpty(self):
  5.         return self.a == []
  6.     def push(self,i):
  7.         self.a.append(i)
  8.     def pop(self):
  9.         return self.a.pop()
  10.     def peek(self):
  11.         return self.a[len(self.a)-1]
  12.  
  13. def infixToPrefix(s):
  14.     prec = {'/':3,'*':3,'+':2,'-':2,'^':4,'(':1}
  15.     opStack = Stack()
  16.    
  17.     prefixList = []
  18.     temp = []
  19.     for token in s:
  20.         if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
  21.             prefixList.append(token)
  22.         elif token == '(':
  23.             opStack.push(token)
  24.         elif token == ')':
  25.             topToken = opStack.pop()
  26.             while topToken != '(':
  27.                 temp.append(topToken)
  28.                 topToken = opStack.pop()
  29.             prefixList = temp + prefixList
  30.             temp = []
  31.         else:
  32.             while (not opStack.isEmpty()) and \
  33.                   (prec[opStack.peek()] >= prec[token]):
  34.                 temp.append(opStack.pop())
  35.             prefixList = temp + prefixList
  36.             temp = []
  37.             opStack.push(token)
  38.     while not opStack.isEmpty():
  39.         temp.append(opStack.pop())
  40.     prefixList = temp + prefixList
  41.     return ''.join(prefixList)
  42. print infixToPrefix("(A+B)*C-(D-E)*(F+G)")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement