[Go to site: main page, start]
Ryans Tutorials
More great tutorials at RyansTutorials

Python Tutorial : Stacks

Stacks on!

Introduction

StacksIn this tutorial we will investigate a data structure called a stack. These can be quite useful for certain types of processing. We will explore this data structure in Python through a simple calculator made using functions. We will then expand and create an improved version using OOP.

 

What is a Stack?

A stack is effectively an array but with limited functionality. With an array you can read, write and manage a series of items with random access via a numerical index. With a stack you still store the items as a series however you are limited to adding items to the end and removing them from the end (in the order that they went in). This if often referred to as Last-in / First-out (LIFO).

Think of it like a pile of books, all in one single tower. If more books are added you add to the stack by placing them on top. If you want to get to a particular book you have to remove the books above it to get to it.

Technically we will be using a list as Python uses lists not arrays (subtle difference). Most people talk about arrays however so I am choosing to refer to them as arrays for convenience.

When using stacks there are four general operations :

  • is_empty - returns True if the stack is empty, False otherwise.
  • push - place an item at the top of the stack.
  • pop - take the top item off the stack and return it.
  • peek - return the top item from the stack but don't remove it from the stack.

Is_empty

Stacks is_empty

Push

Stacks push

Pop

Stacks pop

Peek

Stacks peek

Using a Stack to do Calculations

Stacks can be used for a variety of different tasks. An easy one to get your head around is calculations. If you don't know about Prefix-notation start by checking out the section at the bottom of this page.

With prefix notation, you start at the far right and move across. Every time you come across an operator you apply the operator to the two previous numbers, then you replace that operator, and the two numbers it operated upon with the result of the calculation.

A stack handles this process elegantly. Let's run through an example :

Calculation : * - 7 4 2

Stack :

Starting from the far right we add to the stack :

Calculation : * - 7 4

Stack : 2

The next item is also a digit so add it to the stack :

Calculation : * - 7

Stack : 2 4

7 is also a digit so add to the stack :

Calculation : * -

Stack : 2 4 7

The next item is an operator, so we pop the two items of the top of the stack (7 and 4), perform the operation on them (7 - 4) then put the result back on the stack :

Calculation : *

Stack : 2 3

The next item is also an operator so we do the same thing again :

Calculation :

Stack : 6

We are now at the end of the calculation. There should only be a single item in the stack which is the final answer.

Implementing Stacks with Functions

We will first implement stacks using only functions. The ideal way to do this is using a class however you may not have learnt about these yet / it can be easier to understand what is going on with a simpler implementation before getting into the cleaner solution (which we will look at next).

First off we will create a basic starting point. It is often best to start by creating a simple main function which we can do without having to put much thought into it.

prefix_calculator.py

  1.  
  2.  
  3.  
  4. # The main function that controls the calculator
  5. def main () :
  6.   # Input
  7.   calc_raw = input ("Enter calculation : ")
  8.   calc_items = calc_raw.split(' ')
  9.   
  10.   # Debugging output statement
  11.   print (calc_items)
  12.   
  13.   # Processing
  14.   final_result = 0
  15.   
  16.   # Output
  17.   print (f"Final result : {final_result}")
  18.  
  19. main()
  • We have left a few lines at the beginning of the file as we know we will build this part out further.
  • The debugging output statement allows us to test that the input is being split up as we intend.

If we run the program we should get the following :

  1. python3 prefix_calculator.py
  2. Enter calculation : - 5 4
  3. ['-', '5', '4']
  4. Final result : 0

We're happy that we can get input and also print some output so now let's flesh out the processing section. We will start by creating some stubs to get a general structure for our program. Put these at the top before the main declaration.

prefix_calculator.py

  1.  
  2. # Add an item to the top of the stack
  3. def stack_push (stack, item) :
  4.   
  5.   return True
  6.  
  7.  
  8. # Remove an item from the top of the stack and return it
  9. def stack_pop (stack) :
  10.   
  11.   return True
  12.  
  13.  
  14. # Process the calculation
  15. def process_items (calc_items) :
  16.   result = 0
  17.   
  18.   return result
  19.  
  20.  
  21. # The main function that controls the calculator
  22. def main () :
  23.   # Input
  24.   calc_raw = input ("Enter calculation : ")
  25.   calc_items = calc_raw.split(' ')
  26.   
  27.   # Debugging output statement
  28.   print (calc_items)
  29.   
  30.   # Processing
  31.   final_result = 0
  32.   
  33.   # Output
  34.   print (f"Final result : {final_result}")
  35.  
  36. def main()

Code that is greyed out is code that should already be in your file. It is provided to help you figure out where to paste this new code.

We should also update line 31 so that it refers to our newly created processing function :

  •   # Processing
  •   final_result = process_items (calc_items)

If we run the program again we should get the following :

  1. python3 prefix_calculator.py
  2. Enter calculation : - 5 4
  3. ['-', '5', '4']
  4. Final result : 0

All looking good. Now let's build out the stack specific functions :

prefix_calculator.py

  1.  
  2. # Add an item to the top of the stack
  3. def stack_push (stack, item) :
  4.   stack.append (item)
  5.   return True
  6.  
  7.  
  8. # Remove an item from the top of the stack and return it
  9. def stack_pop (stack) :
  10.   top_item = stack.pop ()
  11.   return top_item
  12.  

You may be wondering why we bother with these functions if each is just a single line of processing. The reason we put them into functions is to help with readability. Now when we refer to them in our processing it will read like what it does rather than us having to mentally translate each time.

And now we are ready to build out our processing. Our aim is to do this incrementally rather than all in one go.

First off we will get a basic framework in, add some items to the stack, not worry about the calculations yet and return the top item from the stack at the end.

prefix_calculator.py

  1.  
  2. # Process the calculation
  3. def process_items (calc_items) :
  4.   result = 0
  5.   calc_stack = []
  6.   
  7.   while len(calc_items) > 0 :
  8.     next_item = calc_items.pop ()
  9.     if next_item in ['-', '+', '/', '*'] :
  10.       var = 'placeholder'
  11.     else :
  12.       # Add number to stack
  13.       stack_push (calc_stack, int(next_item))
  14.   
  15.   return stack_pop (calc_stack)
  16.  

We have put line 10 in just so that we can run the program prior to building out this part of the function. If we had left it blank then Python would have complained.

If we run the script now and only supply numbers as our input it should return the first digit. We are adding items to the stack starting at the far right of the input and the first number in our input will be the last to be added to the stack.

  1. python3 prefix_calculator.py
  2. Enter calculation : 5 4
  3. ['5', '4']
  4. Final result : 4

We are almost done. Now we just need to add the processing that says if we come across an item which is an operation then we need to pop the last two digits off the stack, perform the operation on them then put the result back on to the stack.

prefix_calculator.py

  1.   while len(calc_items) > 0 :
  2.     next_item = calc_items.pop ()
  3.     if next_item in ['-', '+', '/', '*'] :
  4.       # Grab previous two items from the stack
  5.       item1 = stack_pop (calc_stack)
  6.       item2 = stack_pop (calc_stack)
  7.       
  8.       # Perform given operation on them
  9.       if next_item == '-' :
  10.         calculation = item1 - item2
  11.       if next_item == '+' :
  12.         calculation = item1 + item2
  13.       if next_item == '/' :
  14.         calculation = int(item1 / item2)
  15.       if next_item == '*' :
  16.         calculation = int(item1 * item2)
  17.       
  18.       # Place result back on the stack
  19.       stack_push (calc_stack, calculation)
  20.     else :
  21.       # Add number to stack

And now our program is complete. If you run it you should now be able to run complex calculations.

  1. python3 prefix_calculator.py
  2. Enter calculation : * - 7 5 2
  3. ['5', '4']
  4. Final result : 4

Just for completeness, here are the is_empty and peek functions, though they are not needed for the calculator program.

prefix_calculator.py

  1.  
  2. # Check if the stack is empty or not
  3. def stack_is_empty (stack) :
  4.   is_empty = False
  5.   if len(stack) == 0 :
  6.     is_empty = True
  7.   return is_empty
  8.  
  9.  
  10. # Look at what the top item in the stack is but don't remove it'
  11. def stack_peek (stack) :
  12.   return stack[-1]
  13.  

Implementing Stacks with OOP

Now that we have the general idea of how stacks work, let's make a cleaner implentation using Object Oriented Programming (OOP). This will allow us to encapsulate the processing of the stack along with the stack creating a single item that is easier to work with and manage.

Coming soon.

What is Prefix Notation?

As humans we normally work with what is called in-fix notation. These are more human readable. eg.

(7 - 5) * 2 = 8

This is easy to read as the operations are inbetween the items that they act upon.

This is not ideal as a notation for computers to perform the same calculations with however. With prefix-notation the operator is placed before the two items rather than inbetween. The same calculation written with prefix notation would look like this :

* - 7 5 2

This may seem a bit confusing at first so let's work through it. When working out such a calclation you first start from the far right. You move along until you see the first operation (in this case '-'). Then you perform that operation on the two items directly to the left of it.

- 7 5 is read as 7 - 5 = 2

You then replace those three items with the result and continue moving to the left.

* 2 2

Moving along we come to the next operation which is '*' and we do the same :

* 2 2 is read as 2 * 2 = 4

If you follow this process you should always end up at the last item (which will always be an operator) and only have two items preceding it (both of which are numbers).

It turns out that we can perform this process in code very cleanly as a stack.