The Program Specification

Given a symbol string to check parse one character at a time. If the character is an opening delimiter $($e$.$g$.(,\{,$ or $[)$ then it is pushed onto the stack. When a closing delimiter is encountered $($e$.$g$.),\},$ or $])$ the stack is popped.

Implement a stack by using Linked lists. A push operation is implemented by inserting a symbol node at the beginning of the list. A pop operating is implementing by deleting a symbol node from the beginning of the list $($aka the header or top node$).$

Node Class

class Node will contain a constructor, set methods $($data field and next field$),$ get methods and a helper method to determine if the node points to another node.

constructor: init data and next attributes

setters: validate parameters before changing state of private attribute; returns a boolean value if valid parameter

getters: return attributes

helper methods: validate parameter data; checks if a node points to another node

Stack Class

class Stack will contain a constructor, push, pop, peek, is$\_$empty, create$\_$stack and delete$\_$stack methods.

constructor: init head attribute; if data parameter push data onto stack

push$()$: push a node on top of the stack

pop$()$: remove the top node on the stack

peek$()$: if top node exists get data

is$\_$empty$()$ : checks if empty stack

create$\_$stack$()$: class method to create a Stack

delete$\_$stack$()$: release all the nodes in the stack.

Test Driver

Instantiates a Stack object.

Obtains user input.

Validates symbol matching.

Algorithm

a$)$ Create a stack

b$)$ While the end of input is not reached

If the character read is not a symbol to be balanced, ignore it$.$

If the character is an opening symbol $(\{[$ push it onto the stack.

If the character is a closing symbol $)\}]$ and the stack is empty report an error. Otherwise pop the stack.

If the symbol popped is not the corresponding opening symbol, report an error.

Testing Specification

$1)$ Provide at least the $3$ checks of balanced symbols:

test case $1([|)]$

test case $2()(()[()])$

test case $3\{\{([][])\}()\}$

$2)$ Provide a demonstration that your applications manages

non symbol characters

detects attempting to pop from an empty stack

detects an incorrect pairing symbol popped from the stack

Algorithm Analysis and Performance Evaluation

Give the time and space complexity of your solution.

Example Snippet Test Demonstration

Output $0$

Output $1$

#$...$

What to Turn In

Hand in $3.$py files. No zip files.

$1.$ Hand in node class: Use this title format for your $.$py file : yournamenode.py $($Note: Use YOUR name$).$

$2.$ Hand in stack class: Use this title format for your $.$py file : yournamestack.py $($Note: Use YOUR name$).$

$3.$ Hand in a test driver file. Name the output file yournamea$1.$py $($Again$,$ use YOUR name$).$

Submitting multiple files to an assignment

You will hand in $3$ files: $1)$ your $2$ class source files $($which will contain the Node and Stack classes$)$ and $2)$ the demo test driver file $($which will additionally contain the commented out run of the output at your console$).$

Your lab assignment requires uploading more than one file; you should upload these $3$ files as one submission. In this assignment you need to upload a $.$py file that contains your Node class, a $.$py file that contains your Stack class, and a $.$py file that contains your class test driver $-$ all part of one assignment submission. To add these files, the Add Another File button is clicked to upload the two files one by one. Check to make sure that all files get uploaded okay. When finished click Submit Assignment.

Submission Resources

For more information on how to submit your assignment, please visit:

How do I submit an online assignment? Canvas Student Guide

Assignments Overview Canvas Video Guide

Assignments Submissions Canvas Video Guide

Questions?

Feel free to ask in the forum!