{ "metadata": { "name": "ch4" }, "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": "'''\nexample 4.1\nStack implemantation\n'''\nclass 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\ntheStack = StackX(10) # make new stack\ntheStack.push(20)\ntheStack.push(40)\ntheStack.push(60)\ntheStack.push(80)\nwhile( 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": "'''\nexample 4.2\nStack implemantation\n'''\nclass 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\nclass 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\nwhile(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\nEnter 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": "'''\nExample 4.3\n'''\nclass 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\nclass 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\nwhile(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\nEnter 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": "'''\nExample 4.4\n'''\nclass 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\ntheQueue = Queue(5) # queue holds 5 items\ntheQueue.insert(10) # insert 4 items\ntheQueue.insert(20) \ntheQueue.insert(30) \ntheQueue.insert(40) \ntheQueue.remove() # remove 3 items\ntheQueue.remove() \ntheQueue.remove()\ntheQueue.insert(50) # insert 4 more items\ntheQueue.insert(60)\ntheQueue.insert(70)\ntheQueue.insert(80)\nwhile( 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": "'''\nExample 4.5\n'''\nclass 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": "'''\nExample 4.6\n'''\n\nclass 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\nthePQ = PriorityQ(6)\nthePQ.insert(30)\nthePQ.insert(50)\nthePQ.insert(10)\nthePQ.insert(40)\nthePQ.insert(20)\nwhile(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": "'''\nExample 4.7\ninfix : converts infix arithmetic expressions to postfix\n'''\n\nclass 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\nclass 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\nwhile(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 \nStack (bottom-->top): \nFor * \nStack (bottom-->top): \nFor ( \nStack (bottom-->top): * \nFor B \nStack (bottom-->top): * ( \nFor + \nStack (bottom-->top): * ( \nFor C \nStack (bottom-->top): * ( + \nFor ) \nStack (bottom-->top): * ( + \nFor - \nStack (bottom-->top): * \nFor D \nStack (bottom-->top): - \nFor / \nStack (bottom-->top): - \nFor ( \nStack (bottom-->top): - / \nFor E \nStack (bottom-->top): - / ( \nFor + \nStack (bottom-->top): - / ( \nFor F \nStack (bottom-->top): - / ( + \nFor ) \nStack (bottom-->top): - / ( + \nWhile \nStack (bottom-->top): - / \nWhile \nStack (bottom-->top): - \nEnd\nStack (bottom-->top): \nPostfix is ABC+*DEF+/-\nEnter 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": "'''\nExample 4.8\n'''\nclass 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\nclass 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\nwhile(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): \n4 Stack (bottom-->top): 3 \n5 Stack (bottom-->top): 3 4 \n+ Stack (bottom-->top): 3 4 5 \n* Stack (bottom-->top): 3 9 \n6 Stack (bottom-->top): 27 \n1 Stack (bottom-->top): 27 6 \n2 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 \nEvaluates to 25\nEnter 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": {} } ] }