20. Valid parentheses

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool isValid(char *s) {
    int n = strlen(s);
    char *expected = malloc(n + 1); // closing brackets we still owe
    int top = 0;

    for (int i = 0; i < n; i++) {
        switch (s[i]) {
        case '(':
            expected[top++] = ')';
            break;
        case '[':
            expected[top++] = ']';
            break;
        case '{':
            expected[top++] = '}';
            break;
        default:
            if (top == 0 || expected[--top] != s[i]) {
                free(expected);
                return false;
            }
        }
    }
    bool valid = top == 0;
    free(expected);
    return valid;
}

20_solution1.cpp

#include <stack>
#include <string>
using namespace std;

class Solution {
public:
  bool isValid(string s) {
    stack<char> expected; // closing brackets we still owe

    for (char c : s) {
      switch (c) {
      case '(':
        expected.push(')');
        break;
      case '[':
        expected.push(']');
        break;
      case '{':
        expected.push('}');
        break;
      default:
        if (expected.empty() || expected.top() != c)
          return false;
        expected.pop();
      }
    }
    return expected.empty();
  }
};

20_solution2.cpp

#include <stack>
#include <string>
using namespace std;

class Solution {
public:
  bool isValid(string s) {
    stack<char> st;

    for (char c : s) {
      if (c == '(' || c == '[' || c == '{') {
        st.push(c);
      } else if (c == ')') {
        if (st.empty() || st.top() != '(')
          return false;
        st.pop();
      } else if (c == ']') {
        if (st.empty() || st.top() != '[')
          return false;
        st.pop();
      } else if (c == '}') {
        if (st.empty() || st.top() != '{')
          return false;
        st.pop();
      }
    }

    return st.empty();
  }
};

package main

func isValid(s string) bool {
    expected := []byte{} // closing brackets we still owe

    for i := 0; i < len(s); i++ {
        switch c := s[i]; c {
        case '(':
            expected = append(expected, ')')
        case '[':
            expected = append(expected, ']')
        case '{':
            expected = append(expected, '}')
        default:
            n := len(expected)
            if n == 0 || expected[n-1] != c {
                return false
            }
            expected = expected[:n-1]
        }
    }
    return len(expected) == 0
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValid(String s) {
        Deque<Character> expected = new ArrayDeque<>(); // closing brackets we still owe

        for (char c : s.toCharArray()) {
            switch (c) {
                case '(':
                    expected.push(')');
                    break;
                case '[':
                    expected.push(']');
                    break;
                case '{':
                    expected.push('}');
                    break;
                default:
                    if (expected.isEmpty() || expected.pop() != c)
                        return false;
            }
        }
        return expected.isEmpty();
    }
}

class Solution {
  isValid(s) {
    const expected = []; // closing brackets we still owe
    const closer = { "(": ")", "[": "]", "{": "}" };

    for (const c of s) {
      if (c in closer) expected.push(closer[c]);
      else if (expected.pop() !== c) return false;
    }
    return expected.length === 0;
  }
}

class Solution:
    def isValid(self, s: str) -> bool:
        expected = []  # closing brackets we still owe
        closer = {"(": ")", "[": "]", "{": "}"}

        for c in s:
            if c in closer:
                expected.append(closer[c])
            elif not expected or expected.pop() != c:
                return False
        return not expected

struct Solution;

impl Solution {
    fn is_valid(s: String) -> bool {
        let mut expected: Vec<char> = Vec::new(); // closing brackets we still owe

        for c in s.chars() {
            match c {
                '(' => expected.push(')'),
                '[' => expected.push(']'),
                '{' => expected.push('}'),
                _ => {
                    if expected.pop() != Some(c) {
                        return false;
                    }
                }
            }
        }
        expected.is_empty()
    }
}