Monthly Archives: February 2017

Implementing Stack using List in Python – Python Programming Essentials

- - Python, Tutorials, Web

Intro

Stack is a collection of objects inserted and removed in a last-in first-out fashion (LIFO). Objects can be inserted onto stack at any time but only the object inserted last can be accessed or removed which coins the object to be top of the stack.

Realization of Stack Operations using List

 

Methods Realization using List Running Time
S.push(e) L.append(e) O(1)*
S.pop() L.pop() O(1)*
S.top() L[-1] O(1)
S.isempty() len(L) == 0 O(1)
len(S) len(L) O(1)

What is O(1)* ?

The running time for push and pop operations are given O(1)* in the above table. This is known as amortization. It is a principle used in complexity analysis of data structures and algorithms. It should be used carefully and for special cases only.

Why did we use amortized analysis for push/pop?

The list(our stack’s underlying data structure) is a series of objects which eventually are realized by arrays. The objects are stored in a continuous block of memory which offers indexing property for lists. As such, a list cannot occupy the entire memory but restricts to some specific size. When there is no more space for the objects to be added to the end of the list, a new memory series is allocated with the increased size, all the objects are copied to the new allocation and new object is added next to the last object of the current series. The previously held memory is then released free. Here, on every append, resizing of list is not required but true once in a while. Hence the running time of append in list (push on stack) for most elements is O(1) but as a whole in an amortized sense, it is O(1)* which accounts for the timely resizing and copying of elements.

Similarly for pop operations, shrinking of the underlying list is done once in a while therefore accounting for an amortized complexity of O(1)*

Implementation of Stack using List

 

class ListStack:
    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)


    def isempty(self):
        return len(self._data) == 0

    def top(self):
        return self._data[-1]

    def push(self, e):
        self._data.append(e)

    def pop(self):
        return self._data.pop()

Conclusion

Stack is an important data structure for realizing solutions to various programming problems. As such, it is even more essential to understand the running time evaluations and working mechanism of these data structures.

Follow me on github Github

Hire me for a project Fiverr

Raising and Handling Exceptions in Python – Python Programming Essentials

- - Tutorials

Brief Introduction

Any unexpected events that occur during the execution of a program is known to be an exception. Like everything, exceptions are also objects in python that is either an instance of Exception class or an instance of underlying class derived from the base class Exception. Exceptions may occur due to logical errors in the program, running out of memory, etc..

Common Exception Types

Class Description
Exception A base class for most error types
AttributeError Raised by syntax obj.foo, if obj has no member named foo
EOFError Raised if “end of file” reached for console or file input
IOError Raised upon failure of I/O operation (e.g., opening file)
IndexError Raised if index to sequence is out of bounds
KeyError Raised if nonexistent key requested for set or dictionary
KeyboardInterrupt Raised if user types ctrl-C while program is executing
NameError Raised if nonexistent identifier used
StopIteration Raised by next(iterator) if no element
TypeError Raised when wrong type of parameter is sent to a function
ValueError Raised when parameter has invalid value (e.g., sqrt(−5))
ZeroDivisionError Raised when any division operator used with 0 as divisor
For an example, following produces a TypeError exception
abs(‘hello world’) #expects numeric parameter but string given
Example of ValueError

Although the type of the passed parameter is correct, the value is illegitimate.

int(‘hello world’)
int(‘3.14’)

Raising an Exception

An exception can be raised from anywhere within the program though the keyword raise followed by an instance of any of the exception classes.

For example, when your program is expecting a positive integer to process but the I/O stream sent a negative integer, you could raise an Exception as such:

raise ValueError(‘Expecting a positive integer, got negative’) #instance of ValueError exception class

Handling an Exception

Now that we have talked on raising an exception, we should program such that the exception is dealt as required, else the execution of the program terminates. It is advisible to catch each exception types separately although python allows a more generic exception handling for any type of exceptions that may occur.

Examples of Common Usage:

try: 
    result = x/y
except ZeroDivisionError:
    #do as per required

Other common exception handling:

try:
    fp = open(‘sample.txt’ )
except IOError as e:
    print( Unable to open the file: , e)

Conclusion

Exceptions are an important principles of programming for any languages. It should be used wisely. On a concluding note, a try-except block can have a finally block as well. An example of use of finally can be to close a connection regardless of the successful or failed transmission of messages. Additionally, a try-except combination can have a single try block with multiple except blocks catching various classes of exception.

Follow me on github https://github.com/bhishan

Hire me for a project https://fiverr.com/bhishan