class StackX:
def __init__(self,s):
self.maxSize = s
self.stackArray = []
self.top = -1
def push(self,j):
self.top += 1
self.stackArray.append(j)
def pop(self):
p = self.stackArray[self.top]
self.top -= 1
self.stackArray.remove(p)
return p
def peek(self):
return self.stackArray[self.top]
def isEmpty(self):
return (self.top == -1)
def isFull(self):
return (self.top == self.maxSize-1);
theStack = StackX(10) # make new stack
theStack.push(20)
theStack.push(40)
theStack.push(60)
theStack.push(80)
while( not theStack.isEmpty() ):
value = theStack.pop()
print value,
class StackX:
def __init__(self,s):
self.maxSize = s
self.stackArray = []
self.top = -1
def push(self,j):
self.top += 1
self.stackArray.append(j)
def pop(self):
p = self.stackArray[self.top]
self.top -= 1
self.stackArray.remove(p)
return p
def peek(self):
return self.stackArray[self.top]
def isEmpty(self):
return (self.top == -1)
def isFull(self):
return (self.top == self.maxSize-1);
class Reverser:
def __init__(self,i):
self.input = i
self.output = ''
self.theStack = None
def doRev(self):
stackSize = len(self.input)
self.theStack = StackX(stackSize)
for j in range(stackSize):
ch = self.input[j]
self.theStack.push(ch)
while( not self.theStack.isEmpty() ):
ch = self.theStack.pop()
self.output = self.output + ch
return self.output
while(True):
print "Enter a string: " ,
i = raw_input()
if( i == ""):
break
theReverser = Reverser(i)
output = theReverser.doRev()
print "Reversed: " , output
class StackX:
def __init__(self,s):
self.maxSize = s
self.stackArray = []
self.top = -1
def push(self,j):
self.top += 1
self.stackArray.append(j)
def pop(self):
p = self.stackArray[self.top]
self.top -= 1
self.stackArray.remove(p)
return p
def peek(self):
return self.stackArray[self.top]
def isEmpty(self):
return (self.top == -1)
def isFull(self):
return (self.top == self.maxSize-1);
class BracketChecker:
def __init__(self,i):
self.input = i
self.theStack = None
def check(self):
stackSize = len(self.input)
self.theStack = StackX(stackSize)
for j in range(stackSize):
ch = self.input[j]
if (ch == '{' or ch == '[' or ch=='('):
self.theStack.push(ch)
elif (ch=='}' or ch==']' or ch==')'):
if( not self.theStack.isEmpty() ):
chx = self.theStack.pop()
if( (ch=='}' and chx!='{') or (ch==']' and chx!='[') or (ch==')' and chx!='(') ):
print "Error: " , ch , " at " , j
else:
print 'Error: ', ch , ' at ' ,j
else:
pass
if( not self.theStack.isEmpty() ):
print 'Error: missing right delimiter'
while(True):
print 'Enter string containing delimiters: '
i = raw_input()
if( i == ''):
break
theChecker = BracketChecker(i)
theChecker.check()
class Queue:
def __init__(self,s):
self.maxSize = s
self.queArray = []
for i in range(s):
self.queArray.append(0)
self.front = 0
self.rear = -1
self.nItems = 0
def insert(self,j):
if(self.rear == self.maxSize-1):
self.rear = -1
self.rear += 1
self.queArray[self.rear] = j
self.nItems += 1
def remove(self):
temp = self.queArray[self.front]
#self.queArray.remove(temp)
self.front += 1
if(self.front == self.maxSize):
# deal with wraparound
self.front = 0
self.nItems-=1
return temp
def peekFront(self):
return self.queArray[self.front]
def isEmpty(self):
# true if queue is empty
return (self.nItems==0)
def isFull(self):
# true if queue is full
return (self.nItems==self.maxSize)
def size(self):
# number of items in queue
return self.nItems
theQueue = Queue(5) # queue holds 5 items
theQueue.insert(10) # insert 4 items
theQueue.insert(20)
theQueue.insert(30)
theQueue.insert(40)
theQueue.remove() # remove 3 items
theQueue.remove()
theQueue.remove()
theQueue.insert(50) # insert 4 more items
theQueue.insert(60)
theQueue.insert(70)
theQueue.insert(80)
while( not theQueue.isEmpty() ): # // remove and display
n = theQueue.remove()
print n ,
class Queue:
def __init__(self,s):
self.maxSize = s
self.queArray = []
for i in range(s):
self.queArray.append(0)
self.front = 0
self.rear = -1
def insert(self,j):
if(self.rear == self.maxSize-1):
self.rear = -1
self.rear += 1
self.queArray[self.rear] = j
def remove(self):
temp = self.queArray[self.front]
#self.queArray.remove(temp)
self.front += 1
if(self.front == self.maxSize):
# deal with wraparound
self.front = 0
return temp
def peek(self):
return self.queArray[self.front]
def isEmpty(self):
# true if queue is empty
return ( self.rear+1==self.front or (self.front+self.maxSize-1==self.rear) )
def isFull(self):
# true if queue is full
return ( self.rear+2==self.front or (self.front+self.maxSize-2==self.rear) )
def size(self):
# number of items in queue
if(self.rear >= self.front):
# contiguous sequence
return self.rear-self.front+1
else:
# broken sequence
return (self.maxSize-self.front) + (self.rear+1)
class PriorityQ:
# array in sorted order, from max at 0 to min at size-1
def __init__(self,s):
self.maxSize = s
self.queArray = []
for i in range(s):
self.queArray.append(0)
self.nItems = 0
def insert(self,item):
# insert item
if(self.nItems==0):
self.queArray[self.nItems] = item
self.nItems += 1
else:
# if items,
j = self.nItems
while j >= 0:
if( item > self.queArray[j] ):
self.queArray[j+1] = self.queArray[j] # shift upward
else:
break
j -= 1
self.queArray[j+1] = item
self.nItems += 1
def remove(self):
# remove minimum item
self.nItems -= 1
return self.queArray[self.nItems]
def peekMin(self):
# peek at minimum item
return self.queArray[self.nItems-1]
def isEmpty(self):
# true if queue is empty
return (self.nItems==0)
def isFull(self):
# true if queue is full
return (self.nItems == self.maxSize)
thePQ = PriorityQ(6)
thePQ.insert(30)
thePQ.insert(50)
thePQ.insert(10)
thePQ.insert(40)
thePQ.insert(20)
while(not thePQ.isEmpty() ):
item = thePQ.remove()
print item ,
class StackX:
def __init__(self,s):
self.maxSize = s
self.stackArray = []
self.top = -1
def push(self,j):
self.top += 1
self.stackArray.append(j)
def pop(self):
p = self.stackArray[self.top]
self.top -= 1
self.stackArray.remove(p)
return p
def peek(self):
return self.stackArray[self.top]
def isEmpty(self):
return (self.top == -1)
def isFull(self):
return (self.top == self.maxSize-1);
def peekN(self,n): # return item at index n
return self.stackArray[n]
def size(self): # return size
return self.top+1
def displayStack(self,s):
print s
print 'Stack (bottom-->top): ',
for j in range(self.size()):
print self.peekN(j) ,
print ''
class InToPost:
# infix to postfix conversion
def __init__(self,i):
self.input = i
self.stackSize = len(self.input)
self.theStack = StackX(self.stackSize)
self.output = ''
def doTrans(self):
# do translation to postfix
for j in range(self.stackSize):
ch = self.input[j]
self.theStack.displayStack("For "+ ch +" ") # *diagnostic*
if ch=='+' or ch=='-':
self.gotOper(ch, 1)
elif ch=='*' or ch=='/':
self.gotOper(ch, 2)
elif ch=='(':
self.theStack.push(ch)
elif ch==')':
self.gotParen(ch)
else:
self.output = self.output + ch # write it to output
while( not self.theStack.isEmpty() ): # pop remaining opers
self.theStack.displayStack('While ') # *diagnostic*
self.output = self.output + self.theStack.pop() # write to output
self.theStack.displayStack("End")
return self.output
def gotOper(self,opThis, prec1):
# got operator from input
while( not self.theStack.isEmpty() ):
opTop = self.theStack.pop()
if( opTop == '(' ):
self.theStack.push(opTop)
break
else:
prec2 = 0
if(opTop=='+' or opTop=='-'): # find new op prec
prec2 = 1
else:
prec2 = 2
if(prec2 < prec1): # if prec of new op less
self.theStack.push(opTop)
break;
else:
self.output = self.output + opTop # than prec of old
self.theStack.push(opThis)
def gotParen(self,ch):
# got right paren from input
while( not self.theStack.isEmpty() ):
chx = self.theStack.pop()
if( chx == '(' ):
# if popped '('
break
# we're done
else:
# if popped operator
self.output = self.output + chx # output it
while(True):
print 'Enter infix: ',
i = raw_input()
# read a string from kbd
if( i == ''):
# quit if [Enter]
break
theTrans = InToPost(i)
output = theTrans.doTrans() # do the translation
print "Postfix is " , output
class StackX:
def __init__(self,s):
self.maxSize = s
self.stackArray = []
for i in range(s):
self.stackArray.append(0.0)
self.top = -1
def push(self,j):
self.top += 1
self.stackArray[self.top] = j #.append(j)
def pop(self):
p = self.stackArray[self.top]
self.top -= 1
self.stackArray.remove(p)
return p
def peek(self):
return self.stackArray[self.top]
def isEmpty(self):
return (self.top == -1)
def isFull(self):
return (self.top == self.maxSize-1);
def peekN(self,n): # return item at index n
return self.stackArray[n]
def size(self): # return size
return self.top+1
def displayStack(self,s):
print s ,
print 'Stack (bottom-->top): ',
for j in range(self.top+1):
print self.peekN(j) ,
print ''
class ParsePost:
# infix to postfix conversion
def __init__(self,i):
self.input = i
self.theStack = None
def doParse(self):
self.theStack = StackX(20)
interAns = 0
for j in range(len(self.input)):
ch = self.input[j]
self.theStack.displayStack(ch + ' ')
if(ch >= '0' and ch <= '9'):
self.theStack.push( ord(ch)-ord('0') )
else:
num2 = self.theStack.pop()
num1 = self.theStack.pop()
if ch=='+':
interAns = num1 + num2
elif ch=='-':
interAns = num1 - num2
elif ch=='*':
interAns = num1 * num2
elif ch=='/':
interAns = num1 / num2
else:
interAns = 0
self.theStack.push(interAns)
interAns = self.theStack.pop()
return interAns
while(True):
print 'Enter postfix: ',
i = raw_input()
# read a string from kbd
if( i == ''):
# quit if [Enter]
break
aParser = ParsePost(i)
output = aParser.doParse() # do the evaluation
print "Evaluates to " , output