Given a string with several opening and closing brackets, we want to check if the brackets are balanced when every opening bracket is closed.
Examples:
( ( ) ( ( ) ) ) is balanced whereas ( ) ) is not.
( ) ( ) ( ) ( ) is balanced whereas ( ( ) ( ) ) ) is not
) ) ( ( is not balanced.
Solutions:
This is a perfect fit for our stack data structure.
- Every time we see the opening bracket, we can push it to the stack. Also if we see a closing bracket before we see an opening bracket, we return false / not balanced.
- Every time we see a closing bracket, we pop the opening bracket we already pushed if the stack is not empty
- Finally, if we still have left overs in the stack after we are done through the string it means there is a closing bracket missing.
Stack<string> stack = new Stack<string>();
for (int i = 0; i < A.Length; i++) {
if (A[i] == '(')
stack.Push(A[i].ToString());
else {
if (stack.Count != 0)
stack.Pop();
else
return false;
}
}
if (stack.Count == 0)
return true;