How do you check if brackets in a string are balanced (Valid Parentheses)?
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).