I’m stuck on a Programming question and need an explanation.
ALGORITHM
Propose a data structure that supports the stack operations PUSH, POP, and a third operation FIND_MIN which returns the smallest element in the stack (does not delete the element).
All three operations should run in O(1) worst case time. Write algorithms for the three 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 “( ( [ ] [ ) { } )” should return FALSE.
I suggest implementing this by creating a Stack, pushing a (or [or {onto the stack whenever one of those characters is seen, and popping it off when the corresponding closing character is seen. If the wrong character is at the top of the stack, the parentheses do not match, and the program should return false.
Test your program with several inputs, to cover balanced and unbalance cases. Use simple as well as complex parenthesized string of (, {, and [ . Use appropriate error messages; stack-full, stack-empty, and so on. Print the string and say if it is balanced or unbalanced.
