Understand the Application

Balancing of symbols in mathematical analysis, text processing, functional programming is becoming more and more prevalent in big data scientific computing. What better time than now to build an application to check for balanced symbols?

Our instructional material this week talks about using stacks to check whether a given expressions has balanced symbols. This algorithm is useful for compilers to analyze tokens in a programming language's syntax.

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.