Ashford University Algorithms and Data Structures Project

ALGORITHM

Propose a data structure that supports the stack operations PUSH, POP, and a thirdoperation FIND_MIN which returns the smallest element in the stack (does notdelete the element).

All three operations should run in O(1) worst case time. Write algorithms for thethree operations.

Provide an example (with actual numbers) to show how each algorithm works.

PROGRAM

Stack for checking Balanced Parentheses, Brackets, and Braces

In this assignment, you are using Sequential List (Array) to implement the Stack,with Push and Pop operation. You need to write your own Push and Pop operations(and any other operations that you might need).

Use your Stack to match balanced parentheses, brackets, and braces. For example,input string ”{ ( [ ] ) [ ( ) ] } should return TRUE, and “( ( [ ] [ ) { } )” shouldreturn FALSE.

I suggest implementing this by creating a Stack, pushing a (or [or {onto the stackwhenever one of those characters is seen, and popping it off when thecorresponding closing character is seen. If the wrong character is at the top of thestack, the parentheses do not match, and the program should return false.

Test your program with several inputs, to cover balanced and unbalance cases. Usesimple as well as complex parenthesized string of (, {, and [ . Use appropriate errormessages; stack-full, stack-empty, and so on. Print the string and say if it isbalanced or unbalanced.