</>EmbeddedInterview

How do you check if brackets in a string are balanced (Valid Parentheses)?

EasyArrays & Strings (Coding Round)

Short answer: Use a stack. Push every opening bracket; on a closing bracket, the stack must be non-empty and its top must be the matching opener, which you pop. At the end, the stack must be empty. O(n) time, O(n) space (bounded by the string length).

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

bool valid_brackets(const char *s)
{
    size_t len = strlen(s);
    char stack[256];                       /* fixed size: reject inputs that would overflow */
    size_t top = 0;
    for (size_t i = 0; i < len; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            if (top == sizeof stack) return false;      /* too deep */
            stack[top++] = c;
        } else if (c == ')' || c == ']' || c == '}') {
            char want = (c == ')') ? '(' : (c == ']') ? '[' : '{';
            if (top == 0 || stack[top - 1] != want) return false;
            top--;
        }
    }
    return top == 0;
}
/* "{[()]}" -> true, "([)]" -> false, "((" -> false */

Three ways to fail: a closer with an empty stack (")("), a closer that does not match the top ("([)]"), and openers left over at the end ("((").

Only one bracket type? You do not need a stack, just a counter: increment on (, decrement on ), fail if it ever goes negative, and require 0 at the end.

Embedded notes: use a fixed-size array as the stack and handle overflow explicitly instead of recursing or allocating. The same pattern validates nesting in a JSON or configuration parser on a device with no heap.

Follow-ups: minimum number of insertions to balance (count unmatched openers and closers), and the longest valid parentheses substring (stack of indices).