Problem Statement

Given a string containing just the characters '(', ')', '{}, '}', '[', and ']', write a function to determine if the input string is valid. The input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every closing bracket has a corresponding opening bracket of the same type.

Examples

Example 1:

Input: "(){}[]"
Output: True

Example 2:

Input: "([)]"
Output: False

Explanation: For the open bracket '(' it is ended before the large bracket '[' which came after it.

Approaches

1️⃣ Using Stack Data Structure

Approach:

The most efficient way to solve this problem is by using a stack data structure. Here's how the approach works:

1. Initialize a Stack: Use a stack to keep track of the opening brackets.
2. Traverse the Expression: Go through each character in the expression:
   • If the character is an opening bracket ((, {, [), push it onto the stack.
   • If the character is a closing bracket (), }, ]), check if the stack is empty. If it is, the expression is not balanced (since there is no corresponding opening bracket).
   • If the stack is not empty, pop the top of the stack and check if the popped bracket matches the type of the current closing bracket. If they do not match, the expression is not balanced.
3. Final Check: After traversing the entire expression, if the stack is empty, the expression is balanced. If it is not empty, the expression is not balanced.

Code:

#include <iostream>
#include <stack>
#include <unordered_map>

bool isBalanced(const std::string& expression) {
    std::stack<char> stack;
    std::unordered_map<char, char> bracketPairs = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };

    for (char ch : expression) {
        // If the character is a closing bracket
        if (bracketPairs.find(ch) != bracketPairs.end()) {
            // Check if the stack is empty or the top of the stack does not match
            if (stack.empty() || stack.top() != bracketPairs[ch]) {
                return false; // Not balanced
            }
            stack.pop(); // Pop the matching opening bracket
        }
        // If it's an opening bracket, push to stack
        else if (ch == '(' || ch == '{' || ch == '[') {
            stack.push(ch);
        }
    }

    // If the stack is empty, all brackets were matched; otherwise, not balanced
    return stack.empty();
}

int main() {
    std::string expression = "(){}[]";

    if (isBalanced(expression)) {
        std::cout << "The expression is balanced.\n";
    } else {
        std::cout << "The expression is not balanced.\n";
    }

    return 0;
}

OR:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private: 
    /* Function to match the opening 
    and closing brackets */
    bool isMatched(char open, char close) {
    
        // Match
        if((open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}')
        )
        return true;
        
        // Mismatch
        return false;
    }
   
public:
    /* Function to check if the 
    string is valid */
    bool isValid(string str) {
       
        // Initialize a stack
        stack<char> st;
        
        // Start iterating on the string
        for(int i=0; i < str.length(); i++) {
        
            // If an opening bracket is found
            if(str[i] == '(' || str[i] == '[' || 
               str[i] == '{') {
                // Push on top of stack
                st.push(str[i]);
            }
        
            // Else if a closing bracket is found
            else {
                // Return false if stack is empty
                if(st.empty()) return false;
                
                // Get the top elemenfrom stack
                char ch = st.top();
                st.pop();
                
                /* If the opening and closing brackets 
                are not matched, return false */
                if(!isMatched(ch, str[i])) 
                    return false;
            }
        }
        
        /* If stack is empty, the 
        string is valid, else invalid */
        return st.empty();
    }
};

int main() {
    string str = "()[{}()]";
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to check if the 
    string is valid */
    bool ans = sol.isValid(str);
    
    if(ans)
        cout << "The given string is valid.";
    else 
        cout << "The given string is invalid.";
    
    return 0;
}

Explanation of the Code:

1. Stack and Bracket Pairs: A stack is used to store the opening brackets, and an unordered_map (hash map) is used to map closing brackets to their corresponding opening brackets.
2. Iterating Through the Expression: For each character in the expression:
   • If it's a closing bracket, the code checks if the stack is empty or if the top of the stack does not match the corresponding opening bracket. If so, the expression is not balanced.
   • If it's an opening bracket, the code pushes it onto the stack.
3. Final Check: At the end, if the stack is empty, it means all brackets have been correctly matched and the expression is balanced.

Complexity Analysis:

• Time Complexity: The time complexity is O(n), where n is the length of the expression. This is because each character is processed exactly once.
• Space Complexity: The space complexity is O(n) in the worst case, where all characters are opening brackets. In such a case, all characters are pushed onto the stack.