diff options
Diffstat (limited to 'Data_Structures_and_Algorithms_in_Java/ch4.ipynb')
| -rw-r--r-- | Data_Structures_and_Algorithms_in_Java/ch4.ipynb | 704 |
1 files changed, 661 insertions, 43 deletions
diff --git a/Data_Structures_and_Algorithms_in_Java/ch4.ipynb b/Data_Structures_and_Algorithms_in_Java/ch4.ipynb index bfba5c3b..11002dc8 100644 --- a/Data_Structures_and_Algorithms_in_Java/ch4.ipynb +++ b/Data_Structures_and_Algorithms_in_Java/ch4.ipynb @@ -1,6 +1,7 @@ { "metadata": { - "name": "ch4" + "name": "", + "signature": "sha256:0a83dcc11d890f96092d5395b0fb08b80fd72d940b0b48dc460b2e496128cd71" }, "nbformat": 3, "nbformat_minor": 0, @@ -11,25 +12,66 @@ "cell_type": "heading", "level": 1, "metadata": {}, - "source": "Chapter 4 : Stacks and Queues" + "source": [ + "Chapter 4 : Stacks and Queues" + ] }, { "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Exmaple 4.1 Page no : 120" + "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,", + "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" + "text": [ + "80 60 40 20\n" + ] } ], "prompt_number": 1 @@ -38,41 +80,108 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 4.2 Page No : 124" + "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", + "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: " + "text": [ + "Enter a string: " + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "part\n" + "text": [ + "part\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": " Reversed: trap\nEnter a string: " + "text": [ + " Reversed: trap\n", + "Enter a string: " + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "\n" + "text": [ + "\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": "\n" + "text": [ + "\n" + ] } ], "prompt_number": 2 @@ -81,47 +190,120 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 4.3 Page No : 128" + "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()", + "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" + "text": [ + "Enter string containing delimiters: \n" + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "a{b(c]d}e\n" + "text": [ + "a{b(c]d}e\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": "Error: ] at 5\nEnter string containing delimiters: \n" + "text": [ + "Error: ] at 5\n", + "Enter string containing delimiters: \n" + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "\n" + "text": [ + "\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": "Enter string containing delimiters: \n" + "text": [ + "Enter string containing delimiters: \n" + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "\n" + "text": [ + "\n" + ] } ], "prompt_number": 4 @@ -130,19 +312,82 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 4.4 Page No : 138" + "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 ,", + "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" + "text": [ + "40 50 60 70 80\n" + ] } ], "prompt_number": 5 @@ -151,12 +396,59 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 4.5 Page No : 141" + "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)", + "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": [], @@ -166,19 +458,78 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 4.6 Page No : 147" + "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 ,", + "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" + "text": [ + "10 20 30 40 50\n" + ] } ], "prompt_number": 7 @@ -187,41 +538,201 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 4.7 Page No : 161" + "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", + "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: " + "text": [ + "Enter infix: " + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "A*(B+C)-D/(E+F)\n" + "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: " + "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" + "text": [ + "\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": "\n" + "text": [ + "\n" + ] } ], "prompt_number": 8 @@ -230,41 +741,148 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 4.8 Page No : 168" + "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", + "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: " + "text": [ + "Enter postfix: " + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "345+*612+/-\n" + "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: " + "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" + "text": [ + "\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": "\n" + "text": [ + "\n" + ] } ], "prompt_number": 9 @@ -272,7 +890,7 @@ { "cell_type": "code", "collapsed": false, - "input": "", + "input": [], "language": "python", "metadata": {}, "outputs": [] |