Python Lab - Linked Lists and Stacks

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

Give the time and space complexity of your solution. The node class, stack class, and test driver should be 3 separate py files.