SDE - Intern

This solution utilizes a stack data structure; the C++ STL stack is used instead of implementing one from scratch.

The stack is templated with the char datatype because individual characters from the string s will be pushed on top of it as we iterate through s.

ch is assigned the pointer to the string s using the std::string::data() method. This will serve as the starting point of the while-loop, which will run as long as there as a character at the pointer.

The gist of the while-loop involves first checking if the current character is one of the left parantheses ('(', '{', or '['), or one of the right parentheses (')', '}', or ']'). If it is the former, simply push it onto the top of the stack using the std::stack::push() method. If it is the latter, check the top of the stack to see if there is a corresponding left parenthesis using the std::stack::top() method. If there is a matching left parenthesis, remove the top character from the stack using the std::stack::pop() method. However, if the top character of the stack does not match the current ch character, return false. At the end of each iteration, increment the ch pointer by 1 to move it to the next character in s.

After the while-loop, if the stack is not empty, it means that there are left parentheses that were not matched with their corresponding right parenthesis. Therefore, check whether the stack is empty using the std::stack::empty() method, and return false if the stack is not empty.

If the code has not returned false at this point, we can safely conclude that the string of parentheses is valid. Therefore, return true.