DSA Pattern: Valid Parentheses using Stack

Valid Parentheses is a classic interview question that tests your understanding of Linear Data Structures, specifically the Stack (LIFO).

The Logic

As we traverse the string:

1. If we see an opening bracket ('(', '{', '['), we push it onto the stack.
2. If we see a closing bracket:
   • Check if the stack is empty (if so, it's invalid).
   • Pop the top of the stack and check if it matches the current closing bracket.
3. After the loop, the stack must be empty for the string to be valid.

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