{
"metadata": {
"name": "",
"signature": "sha256:0a83dcc11d890f96092d5395b0fb08b80fd72d940b0b48dc460b2e496128cd71"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Chapter 4 : Stacks and Queues"
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Exmaple 4.1 Page no : 120"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class StackX:\n",
" def __init__(self,s):\n",
" self.maxSize = s\n",
" self.stackArray = []\n",
" self.top = -1\n",
"\n",
" def push(self,j):\n",
" self.top += 1\n",
" self.stackArray.append(j)\n",
" \n",
" def pop(self):\n",
" p = self.stackArray[self.top]\n",
" self.top -= 1\n",
" self.stackArray.remove(p)\n",
" return p\n",
" \n",
" def peek(self):\n",
" return self.stackArray[self.top]\n",
"\n",
" def isEmpty(self):\n",
" return (self.top == -1)\n",
"\n",
" def isFull(self):\n",
" return (self.top == self.maxSize-1);\n",
"\n",
"theStack = StackX(10) # make new stack\n",
"theStack.push(20)\n",
"theStack.push(40)\n",
"theStack.push(60)\n",
"theStack.push(80)\n",
"while( not theStack.isEmpty() ):\n",
" value = theStack.pop()\n",
" print value,"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"80 60 40 20\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 4.2 Page No : 124"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class StackX:\n",
" def __init__(self,s):\n",
" self.maxSize = s\n",
" self.stackArray = []\n",
" self.top = -1\n",
"\n",
" def push(self,j):\n",
" self.top += 1\n",
" self.stackArray.append(j)\n",
" \n",
" def pop(self):\n",
" p = self.stackArray[self.top]\n",
" self.top -= 1\n",
" self.stackArray.remove(p)\n",
" return p\n",
" \n",
" def peek(self):\n",
" return self.stackArray[self.top]\n",
"\n",
" def isEmpty(self):\n",
" return (self.top == -1)\n",
"\n",
" def isFull(self):\n",
" return (self.top == self.maxSize-1);\n",
"\n",
"\n",
"class Reverser:\n",
" def __init__(self,i):\n",
" self.input = i\n",
" self.output = ''\n",
" self.theStack = None\n",
"\n",
" def doRev(self):\n",
" stackSize = len(self.input)\n",
" self.theStack = StackX(stackSize)\n",
" for j in range(stackSize):\n",
" ch = self.input[j]\n",
" self.theStack.push(ch)\n",
" while( not self.theStack.isEmpty() ):\n",
" ch = self.theStack.pop()\n",
" self.output = self.output + ch\n",
" return self.output\n",
"\n",
"\n",
"while(True):\n",
" print \"Enter a string: \" ,\n",
" i = raw_input() \n",
" if( i == \"\"):\n",
" break\n",
" theReverser = Reverser(i)\n",
" output = theReverser.doRev()\n",
" print \"Reversed: \" , output"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter a string: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"part\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" Reversed: trap\n",
"Enter a string: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 4.3 Page No : 128"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class StackX:\n",
" def __init__(self,s):\n",
" self.maxSize = s\n",
" self.stackArray = []\n",
" self.top = -1\n",
"\n",
" def push(self,j):\n",
" self.top += 1\n",
" self.stackArray.append(j)\n",
" \n",
" def pop(self):\n",
" p = self.stackArray[self.top]\n",
" self.top -= 1\n",
" self.stackArray.remove(p)\n",
" return p\n",
" \n",
" def peek(self):\n",
" return self.stackArray[self.top]\n",
"\n",
" def isEmpty(self):\n",
" return (self.top == -1)\n",
"\n",
" def isFull(self):\n",
" return (self.top == self.maxSize-1);\n",
"\n",
"class BracketChecker:\n",
" def __init__(self,i):\n",
" self.input = i \n",
" self.theStack = None\n",
"\n",
" def check(self):\n",
" stackSize = len(self.input)\n",
" self.theStack = StackX(stackSize)\n",
" for j in range(stackSize):\n",
" ch = self.input[j]\n",
" if (ch == '{' or ch == '[' or ch=='('):\n",
" self.theStack.push(ch)\n",
" elif (ch=='}' or ch==']' or ch==')'):\n",
" if( not self.theStack.isEmpty() ):\n",
" chx = self.theStack.pop()\n",
" if( (ch=='}' and chx!='{') or (ch==']' and chx!='[') or (ch==')' and chx!='(') ):\n",
" print \"Error: \" , ch , \" at \" , j \n",
" else:\n",
" print 'Error: ', ch , ' at ' ,j\n",
" else:\n",
" pass\n",
" if( not self.theStack.isEmpty() ):\n",
" print 'Error: missing right delimiter'\n",
"\n",
"while(True):\n",
" print 'Enter string containing delimiters: '\n",
" i = raw_input()\n",
" if( i == ''):\n",
" break\n",
" theChecker = BracketChecker(i)\n",
" theChecker.check()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter string containing delimiters: \n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"a{b(c]d}e\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Error: ] at 5\n",
"Enter string containing delimiters: \n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter string containing delimiters: \n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 4.4 Page No : 138"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class Queue:\n",
" def __init__(self,s):\n",
" self.maxSize = s\n",
" self.queArray = []\n",
" for i in range(s):\n",
" self.queArray.append(0)\n",
" self.front = 0\n",
" self.rear = -1\n",
" self.nItems = 0\n",
"\n",
" def insert(self,j):\n",
" if(self.rear == self.maxSize-1):\n",
" self.rear = -1\n",
" self.rear += 1\n",
" self.queArray[self.rear] = j\n",
" self.nItems += 1\n",
"\n",
" def remove(self):\n",
" temp = self.queArray[self.front]\n",
" #self.queArray.remove(temp)\n",
" self.front += 1\n",
" if(self.front == self.maxSize):\n",
" # deal with wraparound\n",
" self.front = 0\n",
" self.nItems-=1\n",
" return temp\n",
"\n",
" def peekFront(self):\n",
" return self.queArray[self.front]\n",
"\n",
" def isEmpty(self):\n",
" # true if queue is empty\n",
" return (self.nItems==0)\n",
"\n",
" def isFull(self):\n",
" # true if queue is full\n",
" return (self.nItems==self.maxSize)\n",
"\n",
" def size(self):\n",
" # number of items in queue\n",
" return self.nItems\n",
"\n",
"theQueue = Queue(5) # queue holds 5 items\n",
"theQueue.insert(10) # insert 4 items\n",
"theQueue.insert(20) \n",
"theQueue.insert(30) \n",
"theQueue.insert(40) \n",
"theQueue.remove() # remove 3 items\n",
"theQueue.remove() \n",
"theQueue.remove()\n",
"theQueue.insert(50) # insert 4 more items\n",
"theQueue.insert(60)\n",
"theQueue.insert(70)\n",
"theQueue.insert(80)\n",
"while( not theQueue.isEmpty() ): # // remove and display\n",
" n = theQueue.remove()\n",
" print n ,"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"40 50 60 70 80\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 4.5 Page No : 141"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class Queue:\n",
" def __init__(self,s):\n",
" self.maxSize = s\n",
" self.queArray = []\n",
" for i in range(s):\n",
" self.queArray.append(0)\n",
" self.front = 0\n",
" self.rear = -1\n",
"\n",
" def insert(self,j):\n",
" if(self.rear == self.maxSize-1):\n",
" self.rear = -1\n",
" self.rear += 1\n",
" self.queArray[self.rear] = j\n",
"\n",
" def remove(self):\n",
" temp = self.queArray[self.front]\n",
" #self.queArray.remove(temp)\n",
" self.front += 1\n",
" if(self.front == self.maxSize):\n",
" # deal with wraparound\n",
" self.front = 0\n",
" return temp\n",
"\n",
" def peek(self):\n",
" return self.queArray[self.front]\n",
"\n",
" def isEmpty(self):\n",
" # true if queue is empty\n",
" return ( self.rear+1==self.front or (self.front+self.maxSize-1==self.rear) )\n",
"\n",
" def isFull(self):\n",
" # true if queue is full\n",
" return ( self.rear+2==self.front or (self.front+self.maxSize-2==self.rear) )\n",
"\n",
" def size(self):\n",
" # number of items in queue\n",
" if(self.rear >= self.front):\n",
" # contiguous sequence\n",
" return self.rear-self.front+1\n",
" else:\n",
" # broken sequence\n",
" return (self.maxSize-self.front) + (self.rear+1)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 6
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 4.6 Page No : 147"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"\n",
"class PriorityQ:\n",
" # array in sorted order, from max at 0 to min at size-1\n",
" def __init__(self,s):\n",
" self.maxSize = s\n",
" self.queArray = []\n",
" for i in range(s):\n",
" self.queArray.append(0)\n",
" self.nItems = 0\n",
"\n",
" def insert(self,item):\n",
" # insert item\n",
" if(self.nItems==0):\n",
" self.queArray[self.nItems] = item\n",
" self.nItems += 1\n",
" else:\n",
" # if items,\n",
" j = self.nItems\n",
" while j >= 0:\n",
" if( item > self.queArray[j] ):\n",
" self.queArray[j+1] = self.queArray[j] # shift upward\n",
" else:\n",
" break\n",
" j -= 1\n",
" self.queArray[j+1] = item\n",
" self.nItems += 1\n",
"\n",
" def remove(self):\n",
" # remove minimum item\n",
" self.nItems -= 1\n",
" return self.queArray[self.nItems]\n",
"\n",
" def peekMin(self):\n",
" # peek at minimum item\n",
" return self.queArray[self.nItems-1]\n",
"\n",
" def isEmpty(self):\n",
" # true if queue is empty\n",
" return (self.nItems==0)\n",
"\n",
" def isFull(self):\n",
" # true if queue is full\n",
" return (self.nItems == self.maxSize)\n",
"\n",
"thePQ = PriorityQ(6)\n",
"thePQ.insert(30)\n",
"thePQ.insert(50)\n",
"thePQ.insert(10)\n",
"thePQ.insert(40)\n",
"thePQ.insert(20)\n",
"while(not thePQ.isEmpty() ):\n",
" item = thePQ.remove()\n",
" print item ,"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"10 20 30 40 50\n"
]
}
],
"prompt_number": 7
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 4.7 Page No : 161"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class StackX:\n",
" def __init__(self,s):\n",
" self.maxSize = s\n",
" self.stackArray = []\n",
" self.top = -1\n",
"\n",
" def push(self,j):\n",
" self.top += 1\n",
" self.stackArray.append(j)\n",
" \n",
" def pop(self):\n",
" p = self.stackArray[self.top]\n",
" self.top -= 1\n",
" self.stackArray.remove(p)\n",
" return p\n",
" \n",
" def peek(self):\n",
" return self.stackArray[self.top]\n",
"\n",
" def isEmpty(self):\n",
" return (self.top == -1)\n",
"\n",
" def isFull(self):\n",
" return (self.top == self.maxSize-1);\n",
"\n",
" def peekN(self,n): # return item at index n\n",
" return self.stackArray[n]\n",
" \n",
" def size(self): # return size\n",
" return self.top+1\n",
" \n",
" def displayStack(self,s):\n",
" print s\n",
" print 'Stack (bottom-->top): ',\n",
" for j in range(self.size()):\n",
" print self.peekN(j) ,\n",
" print ''\n",
"\n",
"class InToPost:\n",
" # infix to postfix conversion\n",
" def __init__(self,i):\n",
" self.input = i\n",
" self.stackSize = len(self.input)\n",
" self.theStack = StackX(self.stackSize)\n",
" self.output = ''\n",
"\n",
" def doTrans(self):\n",
" # do translation to postfix\n",
" for j in range(self.stackSize):\n",
" ch = self.input[j]\n",
" self.theStack.displayStack(\"For \"+ ch +\" \") # *diagnostic*\n",
" if ch=='+' or ch=='-':\n",
" self.gotOper(ch, 1)\n",
" elif ch=='*' or ch=='/':\n",
" self.gotOper(ch, 2)\n",
" elif ch=='(':\n",
" self.theStack.push(ch)\n",
" elif ch==')':\n",
" self.gotParen(ch)\n",
" else:\n",
" self.output = self.output + ch # write it to output\n",
" while( not self.theStack.isEmpty() ): # pop remaining opers\n",
" self.theStack.displayStack('While ') # *diagnostic*\n",
" self.output = self.output + self.theStack.pop() # write to output\n",
" self.theStack.displayStack(\"End\")\n",
" return self.output\n",
"\n",
" def gotOper(self,opThis, prec1):\n",
" # got operator from input\n",
" while( not self.theStack.isEmpty() ):\n",
" opTop = self.theStack.pop()\n",
" if( opTop == '(' ):\n",
" self.theStack.push(opTop)\n",
" break\n",
" else:\n",
" prec2 = 0\n",
" if(opTop=='+' or opTop=='-'): # find new op prec\n",
" prec2 = 1\n",
" else:\n",
" prec2 = 2\n",
" if(prec2 < prec1): # if prec of new op less\n",
" self.theStack.push(opTop)\n",
" break;\n",
" else:\n",
" self.output = self.output + opTop # than prec of old\n",
" self.theStack.push(opThis)\n",
"\n",
" def gotParen(self,ch):\n",
" # got right paren from input\n",
" while( not self.theStack.isEmpty() ):\n",
" chx = self.theStack.pop()\n",
" if( chx == '(' ):\n",
" # if popped '('\n",
" break\n",
" # we're done\n",
" else:\n",
" # if popped operator\n",
" self.output = self.output + chx # output it\n",
"\n",
"while(True):\n",
" print 'Enter infix: ',\n",
" i = raw_input()\n",
" # read a string from kbd\n",
" if( i == ''):\n",
" # quit if [Enter]\n",
" break\n",
" theTrans = InToPost(i)\n",
" output = theTrans.doTrans() # do the translation\n",
" print \"Postfix is \" , output"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter infix: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"A*(B+C)-D/(E+F)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" For A \n",
"Stack (bottom-->top): \n",
"For * \n",
"Stack (bottom-->top): \n",
"For ( \n",
"Stack (bottom-->top): * \n",
"For B \n",
"Stack (bottom-->top): * ( \n",
"For + \n",
"Stack (bottom-->top): * ( \n",
"For C \n",
"Stack (bottom-->top): * ( + \n",
"For ) \n",
"Stack (bottom-->top): * ( + \n",
"For - \n",
"Stack (bottom-->top): * \n",
"For D \n",
"Stack (bottom-->top): - \n",
"For / \n",
"Stack (bottom-->top): - \n",
"For ( \n",
"Stack (bottom-->top): - / \n",
"For E \n",
"Stack (bottom-->top): - / ( \n",
"For + \n",
"Stack (bottom-->top): - / ( \n",
"For F \n",
"Stack (bottom-->top): - / ( + \n",
"For ) \n",
"Stack (bottom-->top): - / ( + \n",
"While \n",
"Stack (bottom-->top): - / \n",
"While \n",
"Stack (bottom-->top): - \n",
"End\n",
"Stack (bottom-->top): \n",
"Postfix is ABC+*DEF+/-\n",
"Enter infix: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 8
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 4.8 Page No : 168"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class StackX:\n",
" def __init__(self,s):\n",
" self.maxSize = s\n",
" self.stackArray = []\n",
" for i in range(s):\n",
" self.stackArray.append(0.0)\n",
" self.top = -1\n",
"\n",
" def push(self,j):\n",
" self.top += 1\n",
" self.stackArray[self.top] = j #.append(j)\n",
" \n",
" def pop(self):\n",
" p = self.stackArray[self.top]\n",
" self.top -= 1\n",
" self.stackArray.remove(p)\n",
" return p\n",
" \n",
" def peek(self):\n",
" return self.stackArray[self.top]\n",
"\n",
" def isEmpty(self):\n",
" return (self.top == -1)\n",
"\n",
" def isFull(self):\n",
" return (self.top == self.maxSize-1);\n",
"\n",
" def peekN(self,n): # return item at index n\n",
" return self.stackArray[n]\n",
" \n",
" def size(self): # return size\n",
" return self.top+1\n",
" \n",
" def displayStack(self,s):\n",
" print s ,\n",
" print 'Stack (bottom-->top): ',\n",
" for j in range(self.top+1):\n",
" print self.peekN(j) ,\n",
" print ''\n",
"\n",
"class ParsePost:\n",
" # infix to postfix conversion\n",
" def __init__(self,i):\n",
" self.input = i\n",
" self.theStack = None\n",
"\n",
" def doParse(self):\n",
" self.theStack = StackX(20)\n",
" interAns = 0\n",
" for j in range(len(self.input)):\n",
" ch = self.input[j]\n",
" self.theStack.displayStack(ch + ' ')\n",
" if(ch >= '0' and ch <= '9'):\n",
" self.theStack.push( ord(ch)-ord('0') )\n",
" else:\n",
" num2 = self.theStack.pop()\n",
" num1 = self.theStack.pop()\n",
" if ch=='+':\n",
" interAns = num1 + num2\n",
" elif ch=='-':\n",
" interAns = num1 - num2\n",
" elif ch=='*':\n",
" interAns = num1 * num2\n",
" elif ch=='/':\n",
" interAns = num1 / num2\n",
" else:\n",
" interAns = 0\n",
" self.theStack.push(interAns)\n",
" interAns = self.theStack.pop()\n",
" return interAns\n",
"\n",
"while(True):\n",
" print 'Enter postfix: ',\n",
" i = raw_input()\n",
" # read a string from kbd\n",
" if( i == ''):\n",
" # quit if [Enter]\n",
" break\n",
" aParser = ParsePost(i)\n",
" output = aParser.doParse() # do the evaluation\n",
" print \"Evaluates to \" , output"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter postfix: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"345+*612+/-\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" 3 Stack (bottom-->top): \n",
"4 Stack (bottom-->top): 3 \n",
"5 Stack (bottom-->top): 3 4 \n",
"+ Stack (bottom-->top): 3 4 5 \n",
"* Stack (bottom-->top): 3 9 \n",
"6 Stack (bottom-->top): 27 \n",
"1 Stack (bottom-->top): 27 6 \n",
"2 Stack (bottom-->top): 27 6 1 \n",
"+ Stack (bottom-->top): 27 6 1 2 \n",
"/ Stack (bottom-->top): 27 6 3 \n",
"- Stack (bottom-->top): 27 2 \n",
"Evaluates to 25\n",
"Enter postfix: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 9
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}