Medium · stack

Balanced Brackets

You do not need a stack library to have a stack: an array plus an index that only touches the end is one. This problem is the classic reason that trick exists — brackets close most-recent-opened-first, and that is precisely what a stack stores.

At a glancePush openers onto an array; on a closer, check it matches the top and pop. Print YES if you never mismatch and the stack is empty at the end; NO otherwise.

Problem

Input: One line of at most 1000 characters, containing only ( ) [ ] { }.

Output: YES if the brackets are balanced and properly nested, NO otherwise.

Samples:

Input	Output
`([{}])`	`YES`
`(]`	`NO`
`(((`	`NO`

Balanced means two things at once: every closer finds a matching opener (never pop an empty stack), and every opener eventually closes (the stack ends empty). Missing either half fails.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Only the most recent opener can close next

Scan left to right. Whenever you see (, [ or {, remember it. Whenever you see a closer, it must match the last opener you still owe — anything else (like ([)]) is broken no matter what comes later. Remembering in reverse order of arrival is exactly what a stack does.

Hint 2 — Three failure modes, three checks

A closer arrives but the stack is empty → NO. A closer arrives and the top does not match its type → NO. The line ends with something still on the stack (like ((() → NO. Only when none of the three happens do you print YES. Having all three checks clear before you type is half the problem done.

Hint 3 — Naming the match test

A compact way: a closer matches the top when (open == '(' && c == ')') || (open == '[' && c == ']') || (open == '{' && c == '}'). Storing openers only — never closers — keeps the stack trivial; if you ever find yourself pushing closers, stop and rethink the loop.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    char s[1005];
    cin.getline(s, 1005);
    char stack[1005];
    int top = 0;

    int i = 0;
    while (s[i] != '\0') {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            stack[top] = c;
            top++;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == 0) { cout << "NO" << endl; return 0; }
            char open = stack[top - 1];
            bool match = (open == '(' && c == ')') ||
                         (open == '[' && c == ']') ||
                         (open == '{' && c == '}');
            if (!match) { cout << "NO" << endl; return 0; }
            top--;
        }
        i++;
    }

    cout << (top == 0 ? "YES" : "NO") << endl;
    return 0;
}

You have now used the array-as-stack idiom, and it reaches far past brackets: undo history, DFS and expression evaluation all live on it. The sibling pattern for text needs no stack at all — two indices walking toward each other — which is exactly how Palindrome String works.

Deep dive

Why this works

Brackets close in reverse order of opening — last opened, first closed — which is the definition of a stack (LIFO). An array plus an integer top is a complete stack: push is stack[top++] = c, pop is top--, peek is stack[top-1].

The cost

O(n) time for a line of n characters — each character is pushed or popped at most once — and O(n) space in the worst case (a line of nothing but openers).

Where it goes wrong

Popping an empty stack: ] alone arrives at a closer with nothing to match. Check top == 0 before touching stack[top-1], or you read garbage below index zero.
Forgetting the leftover check. ((( prints YES if you only react to closers — the stack must be empty at the end, so the last line needs top == 0.

Next step

The other way to test symmetry in a string needs no stack at all: two indices walking toward each other in Palindrome String.

Two things to remember

A stack is an array plus an index that only touches the end.
Three ways to fail: empty-stack pop, type mismatch, leftovers at the end.

🐞 This version fails — open it and try

Counts opens and closes but ignores their types — ([)] slips through

#include <iostream>
using namespace std;

int main() {
    char s[1005];
    cin.getline(s, 1005);
    int open = 0;
    int i = 0;
    while (s[i] != '\0') {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') open++;
        else if (s[i] == ')' || s[i] == ']' || s[i] == '}') open--;
        i++;
    }
    cout << (open == 0 ? "YES" : "NO") << endl;
    return 0;
}