Matching Brackets with a Stack

def is_valid(s):
    while True:                          # delete every adjacent pair, again and again
        t = s.replace("()", "").replace("[]", "").replace("{}", "")
        if t == s:                       # nothing left to delete
            return s == ""
        s = t

Reading {[()]} — The stack holds the brackets still open, each with its position. Green pairs have matched.

bool isValid(const string& s) {
    unordered_map<char, char> opener = {{')', '('}, {']', '['}, {'}', '{'}};
    stack<char> open;                        // the brackets still open, the most recent on top
    for (char c : s) {
        if (!opener.count(c)) {              // an opener waits for its closer
            open.push(c);
        } else {
            if (open.empty() || open.top() != opener[c]) return false;   // nothing open, or the wrong kind
            open.pop();
        }
    }
    return open.empty();                     // anything left was never closed
}

def is_valid(s):
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []                           # the brackets still open, the most recent on top
    for c in s:
        if c not in opener:              # an opener waits for its closer
            stack.append(c)
        else:
            if not stack or stack[-1] != opener[c]:
                return False             # nothing open, or the wrong kind
            stack.pop()
    return not stack                     # anything left was never closed

static boolean isValid(String s) {
    Map<Character, Character> opener = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> open = new ArrayDeque<>();      // the brackets still open, the most recent on top
    for (char c : s.toCharArray()) {
        if (!opener.containsKey(c)) {                 // an opener waits for its closer
            open.push(c);
        } else {
            char want = opener.get(c);
            if (open.isEmpty() || open.peek() != want) return false;   // nothing open, or the wrong kind
            open.pop();
        }
    }
    return open.isEmpty();                            // anything left was never closed
}

function isValid(s) {
    const opener = { ")": "(", "]": "[", "}": "{" };
    const open = [];                         // the brackets still open, the most recent on top
    for (const c of s) {
        if (!(c in opener)) {                // an opener waits for its closer
            open.push(c);
        } else {
            if (open.length === 0 || open[open.length - 1] !== opener[c]) return false;  // nothing open, or the wrong kind
            open.pop();
        }
    }
    return open.length === 0;                // anything left was never closed
}

Reading ([)] — The closer meets the wrong kind on top, and the check stops there.

Removing from (a))b( — The stack holds positions. Red brackets are the ones removed.

string minRemoveToMakeValid(const string& s) {
    stack<int> open;                         // positions of the '(' still open
    vector<bool> drop(s.size(), false);      // the brackets to remove
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') {
            open.push(i);
        } else if (s[i] == ')') {
            if (!open.empty()) open.pop();   // it closes the most recent open '('
            else drop[i] = true;             // nothing open: one ')' too many
        }
    }
    while (!open.empty()) {                  // still open at the end: one '(' too many each
        drop[open.top()] = true;
        open.pop();
    }
    string out;
    for (int i = 0; i < (int)s.size(); i++)
        if (!drop[i]) out += s[i];
    return out;
}

def min_remove_to_make_valid(s):
    stack = []                           # positions of the '(' still open
    drop = set()                         # the brackets to remove
    for i, c in enumerate(s):
        if c == "(":
            stack.append(i)
        elif c == ")":
            if stack:
                stack.pop()              # it closes the most recent open '('
            else:
                drop.add(i)              # nothing open: one ')' too many
    drop.update(stack)                   # still open at the end: one '(' too many each
    return "".join(c for i, c in enumerate(s) if i not in drop)

static String minRemoveToMakeValid(String s) {
    Deque<Integer> open = new ArrayDeque<>();         // positions of the '(' still open
    boolean[] drop = new boolean[s.length()];         // the brackets to remove
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            open.push(i);
        } else if (c == ')') {
            if (!open.isEmpty()) open.pop();          // it closes the most recent open '('
            else drop[i] = true;                      // nothing open: one ')' too many
        }
    }
    for (int i : open) drop[i] = true;                // still open at the end: one '(' too many each
    StringBuilder out = new StringBuilder();
    for (int i = 0; i < s.length(); i++)
        if (!drop[i]) out.append(s.charAt(i));
    return out.toString();
}

function minRemoveToMakeValid(s) {
    const open = [];                         // positions of the '(' still open
    const drop = new Set();                  // the brackets to remove
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            open.push(i);
        } else if (s[i] === ")") {
            if (open.length > 0) open.pop(); // it closes the most recent open '('
            else drop.add(i);                // nothing open: one ')' too many
        }
    }
    for (const i of open) drop.add(i);       // still open at the end: one '(' too many each
    let out = "";
    for (let i = 0; i < s.length; i++)
        if (!drop.has(i)) out += s[i];
    return out;
}

def simplify_path(path):
    stack = []                           # the directory names so far
    for part in path.split("/"):
        if part == "..":
            if stack:
                stack.pop()              # up one level; at the root, stay put
        elif part and part != ".":
            stack.append(part)           # a name, even "..."
    return "/" + "/".join(stack)

def asteroid_collision(asteroids):
    stack = []                           # the survivors so far, left to right
    for a in asteroids:
        alive = True
        while alive and a < 0 and stack and stack[-1] > 0:
            if stack[-1] < -a:
                stack.pop()              # the right-mover on top is smaller: it explodes, keep going
            elif stack[-1] == -a:
                stack.pop()              # the same size: both explode
                alive = False
            else:
                alive = False            # the right-mover is bigger: a explodes
        if alive:
            stack.append(a)
    return stack

def find_celebrity(mat):
    n = len(mat)
    stack = list(range(n))               # everyone starts as a candidate
    while len(stack) > 1:
        a, b = stack.pop(), stack.pop()
        if mat[a][b]:
            stack.append(b)              # a knows b, so a isn't the celebrity
        else:
            stack.append(a)              # a doesn't know b, so b isn't the celebrity
    c = stack[0]
    for i in range(n):                   # the last one standing still has to be checked
        if i != c and (mat[c][i] or not mat[i][c]):
            return -1
    return c

def is_valid(s):
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c not in opener:
            stack.append(c)
        elif stack.pop() != opener[c]:   # pops even when nothing is open
            return False
    return not stack

def is_valid(s):
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c not in opener:
            stack.append(c)
        else:
            if not stack or stack[-1] != opener[c]:
                return False
            stack.pop()
    return True                          # forgets what's still open

def is_valid(s):
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif not stack:
            return False
        else:
            stack.pop()                  # any opener will do: the kind is never checked
    return not stack

def min_remove_to_make_valid(s):
    kept, open_ = [], 0
    for c in s:
        if c == ")" and open_ == 0:
            continue                     # a ')' with nothing open: drop it
        open_ += 1 if c == "(" else -1 if c == ")" else 0
        kept.append(c)
    out = []
    for c in kept:                       # drop the extra '(' ... counting from the left
        if c == "(" and open_ > 0:
            open_ -= 1
            continue
        out.append(c)
    return "".join(out)