Valid Parentheses: How to Check for Balanced Parentheses in Code

Introduction

In this post, I will discuss how to determine if a given string of parentheses is valid or not using different programming languages.

Problem Statement

The problem is to check if a string consisting of parentheses, braces, and square brackets is valid or not. The string is considered valid if it satisfies the following conditions:

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

• Open brackets must be closed in the correct order.

• Every close bracket has a corresponding open bracket of the same type.

Data Structures Used

I will be using the stack data structure to solve this problem. A stack is a last-in, first-out (LIFO) data structure that stores items in a linear order. I will push opening brackets onto the stack, and when I encounter a closing bracket, I will pop the top element from the stack and check if it matches the closing bracket.

Algorithmic Approach

I will use the following approach to solve the problem:

1. Initialize an empty stack.

2. Traverse the given string from left to right.

3. If the current character is an opening bracket, push it onto the stack.

4. If the current character is a closing bracket, check if the stack is empty. If it is, return false. Otherwise, pop the top element from the stack and check if it matches the closing bracket. If it doesn't, return false.

5. After traversing the entire string, check if the stack is empty. If it is, return true. Otherwise, return false.

Code Implementation

Here's the C++ implementation of the above approach:

bool isValid(string s)
{
   stack<char> S;
   for(char c :s ){
    if(c=='(' || c=='[' || c=='{' )
            S.push(c);
    else{
         if (S.empty()) {
            return false;
        }
        if(S.top()=='(' && c==')'){
            S.pop();
        }
        else if(S.top()=='[' && c==']'){
            S.pop();
        }
        else if(S.top()=='{' && c=='}'){
            S.pop();
        }
        else
            return false;
        }
   }
   return S.empty();
}

Here's the Python implementation of the above approach:

def isValid(self, s: str) -> bool:
    stack = []
    for ele in s:
        if(ele == '{' or ele == '(' or ele == '['):
            stack.append(ele)
        else:
            if not stack:
                return False
            if(stack[len(stack)-1] == '(' and ele == ')'):
                stack.pop()
            elif(stack[len(stack)-1] == '{' and ele == '}'):
                stack.pop()
            elif(stack[len(stack)-1] == '[' and ele == ']'):
                stack.pop()
            else:
                return False
    return not stack

Analysis of My Interpretation

Our solution works as expected and passes all the test cases and edge cases. The time complexity of our solution is O(n), where n is the length of the input string. This is because I are iterating through each character in the input string only once. The space complexity of our solution is also O(n), because in the worst case, I may need to store all the opening brackets in the stack.

Conclusion

In this blog post, I discussed the problem of validating parentheses in a string. I provided a detailed explanation of the algorithmic approach and the data structures used to solve this problem. I also implemented the solution in both C++ and Python and tested it with various test cases and edge cases. Finally, I analyzed the time and space complexity of our solution and concluded that it is an optimal solution for this problem.