OO Programming and Data Structures | CS 241

05 Prove : Homework - Data Structures

Stacks

Outcomes

At the end of this study, successful students will be able to:

  1. Articulate the strengths and weaknesses of Stacks.

  2. Use Stacks in Python to solve problems.

Please be aware that while the concept of a stack is fairly straight-forward, the accompanying programming assignment here is somewhat challenging, so please start early and help one another.

Preparation Material

Please read the following:

Using Stacks in Python

Python does not have a specific, "Stack" data structure. Instead, they make use of the built-in List data structure. Please read Using Lists as Stacks from the official documentation.

In short, the list provides an .append() method that we use to push, and a .pop() method that removes the top item on the stack (i.e., the last item in the list) and returns it.

Homework Assignment

An interesting problem that Stacks can help us solve is that of determining if a program had balanced braces. For example, code like print(stuff[i]) is balanced where as print(stuff[i)], print(stuff[i], and print(stuff[i])) are not balanced.

To simplify the problem, we will use files that only contain braces (no other words). Your task is to write a program that will read in a file containing three kinds of braces: { }, ( ), and [ ] and display either "Balanced" or "Not balanced". To be balanced, a file must contain the same number of open braces as closed braces, and they must be closed in the reverse order of how they were opened. You should ignore all whitespace.

The following are examples of balanced braces:


{ ( [ ] ) }

{ }

[ [ [ ( ) ] ] ]

The following are examples of braces that are not balanced:


{ ( [

{ [ } ]

[ ] ] [

Getting Started

Figuring out this problem is a little tricky. Try to think about how a stack might help.

Because we need to have closing braces occur in the reverse order of the opening ones (think Last-in First-out), one idea is to think about putting opening braces onto a stack when they are encountered, and then when closing braces are encountered you could check to see if they match the brace that's currently on the top of the stack. Of course, you also need to make sure the stack has things in it, and ends with no extra items at the end of the program.

Take some time to think and work through this problem. These are the kinds of problems you could see on a job interview (although this one is common enough that you likely won't see it, specifically). If you have spent time and worked with others, but are still struggling with ideas of how to approach it, you are welcome to refer to this pseudocode that a class put together one semester.

TestBed and Submission

An automated TestBed script is provided to help you test your program. It will test your program on 6 different files.


testBed cs241/stacks05 braces.py

These files should have the following results:

In case it is helpful, these files are also available at GitHub.

You will not submit your program for grading, instead take the accompanying I-Learn quiz to report on your progress and your understand of stacks.

You are encouraged to work with others on the programming and the quiz.

Submission

When you have a good understanding of this data structure and have completed the programming project, take the accompanying I-Learn Quiz. It has questions about how the data structure works, and also, has places for your to report on the parts of the programming assignment that you completed.