Valid parentheses

Check that every bracket closes in the right order. The textbook use of a stack.

Time O(n)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

The most recently opened bracket must be the first one closed. That is last in, first out, so push every opener and pop on every closer to check the match.

Code

C++PythonC#

bool matches(char o, char c) {
    return (o == '(' && c == ')') || (o == '[' && c == ']') || (o == '{' && c == '}');
}

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

PAIRS = {')': '(', ']': '[', '}': '{'}

def is_valid(s: str) -> bool:
    stack = []
    for ch in s:
        if ch in '([{': stack.append(ch)
        else:
            if not stack: return False
            opening = stack.pop()
            if PAIRS[ch] != opening: return False
    return not stack

public static bool IsValid(string s) {
    var stack = new Stack<char>();
    foreach (char ch in s) {
        if (ch is '(' or '[' or '{') stack.Push(ch);
        else {
            if (stack.Count == 0) return false;
            char open = stack.Pop();
            if (!Matches(open, ch)) return false;
        }
    }
    return stack.Count == 0;
}

static bool Matches(char o, char c) =>
    (o, c) is ('(', ')') or ('[', ']') or ('{', '}');

Tips

Two ways to fail in the loop: a closer with an empty stack, or a closer that does not match the top.
Do not forget the final check. Leftover openers mean the string is invalid.

In the .NET library

Stack<T> has Push, Pop, Peek and TryPop. Pop on an empty stack throws InvalidOperationException, so check Count or use TryPop.