Data Structure Using C

Question

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([)]"

Output: false

Example 5:

Input: s = "{[]}"

Output: true

Answer 1

Hi Pharrell, I would recommend using a stack data structure for this exercise. You can implement the stack as an abstract data type in C. Since there doesn't appear to be a limit on the length of the input string, the stack should include logic for dynamic memory allocation (i.e. using malloc and free) to increase the size of the underlying array/linked list as needed. I would recommend the data type support push, pop, and length operations. (If you haven't covered dynamic memory allocation, then the course instructor may not be expecting that, and a simpler implementation with a fixed array size may be OK.)

If you do some searching, there are plenty of resources online showing examples of how to implement such a data structure.

In the main program, you can initialize a new stack and then read each character of the string sequentially. For each open paren/bracket character, push the corresponding value onto the stack. For each close paren/bracket character, pop a value off the top of the stack and perform a comparison. If at any point a popped value does not correspond to the same type of read value (paren, bracket, curly bracket) OR if there is no value stored in the stack, it means the string is invalid and the program can return false. Once the program reaches the end of the string, if the stack is empty then the string is valid; if there are still values on the stack then the string is invalid.

Feel free to comment if you have questions!