Solved exercise: array-based stack and balanced brackets in C

Build a fixed-size stack over an array in C and use it to check whether a formula has its parentheses, brackets and braces balanced.

Exam Code C Data structures Basic level Tested code

Data Structures · Practice sheetExercise 2 · 2.5 points · 25 min

A very simple scientific calculator stores formulas as text and, before evaluating them, checks that their groupings are well formed. There are three kinds of grouping: parentheses ( ), square brackets [ ] and braces { }. Every other character in the formula (digits, letters, operators, spaces) is ignored.

A formula is balanced if every closing symbol matches the most recent opening symbol that is still open and is of the same kind, and when the text ends no opening symbol is left unclosed. For instance, {[()]} is balanced, while ([)] is not, and neither are (() nor )(.

Part A. Define a stack of characters implemented over a static array of capacity MAX_STACK = 32, with the operations stack_init, stack_is_empty, stack_is_full, push and pop. The operations that may fail (pushing onto a full stack, popping from an empty stack) must report the failure through their return value and must never read or write outside the array.

Part B. Write the function int is_balanced(const char *formula) that uses that stack and returns 1 if the formula is balanced and 0 otherwise. If the stack becomes full because more than 32 openings are pending at the same time, the formula counts as not balanced.

Input. The first line holds an integer n (0 ≤ n ≤ 100), the number of formulas. Then come n lines, each with a formula of at most 200 characters. A line may be empty (an empty formula, which counts as balanced). The program treats each line as the text up to the first line feed or carriage return, so Windows line endings (\r\n) do not change the result.

Output. For each formula, one line with its order number starting at 1, a colon, a space and the word YES or NO. If n is 0 nothing is printed. The worked example below the statement shows six formulas and the answers your program must produce for them.

Sample input

6
{[()]}
([)]
(()
)(
3*(a+b)-[c/{d}]
x+y

Expected output

1: YES
2: NO
3: NO
4: NO
5: YES
6: YES

Array-based stack: structure, initialisation, push, pop and empty/full queries, with bounds checking

1.0

Correct matching algorithm (push on opening, compare on closing, ignore every other character)

1.0

Edge cases: closing without opening, leftover openings, empty formula and stack overflow

0.5

Hints

Hint 1 · Which structure always remembers the latest pending opening?

A stack: the last opening symbol pushed is the first one that must be closed. Walk the formula character by character and decide what to do depending on whether it is an opening, a closing or anything else.

Hint 2 · What exactly happens when you meet a closing symbol?

There are three ways to fail: the stack is empty (a closing symbol with no opening), the popped symbol is not the opening of the same kind, or the formula ends with a non-empty stack. A small helper that maps a closing character to its opening character keeps the code short.

Hint 3 · How do you represent the stack inside the array?

Keep an integer top holding the number of stored elements: the stack is empty when it is 0 and full when it equals MAX_STACK. Push writes data[top] and then increments; pop decrements and then reads data[top]. Check the bounds first and return 0 when the operation cannot be done.

Solution

Explained solution

The solution keeps two levels apart: the stack, which knows nothing about brackets, and is_balanced, which only uses the stack interface. The stack is a struct with an array data and a counter top holding how many elements are stored; the next free slot is always data[top].

push and pop return 1 when the operation succeeded and 0 when it could not be done, and pop delivers the character through an output pointer. That way the caller can react to failures and the stack never touches memory outside its array. If passing results through pointers is still shaky, review this exercise on pass by value and by reference.

#include <stdio.h>
#include <string.h>

#define MAX_STACK 32
#define MAX_LINE 256

typedef struct {
    char data[MAX_STACK];
    int top; /* number of stored elements */
} Stack;

static void stack_init(Stack *s) {
    s->top = 0;
}

static int stack_is_empty(const Stack *s) {
    return s->top == 0;
}

static int stack_is_full(const Stack *s) {
    return s->top == MAX_STACK;
}

static int push(Stack *s, char c) {
    if (stack_is_full(s)) {
        return 0;
    }
    s->data[s->top] = c;
    s->top++;
    return 1;
}

static int pop(Stack *s, char *c) {
    if (stack_is_empty(s)) {
        return 0;
    }
    s->top--;
    *c = s->data[s->top];
    return 1;
}

static char opening_of(char closing) {
    switch (closing) {
    case ')': return '(';
    case ']': return '[';
    case '}': return '{';
    default:  return '\0';
    }
}

static int is_balanced(const char *formula) {
    Stack s;
    char c;
    char top_char;
    stack_init(&s);
    for (size_t i = 0; formula[i] != '\0'; i++) {
        c = formula[i];
        if (c == '(' || c == '[' || c == '{') {
            if (!push(&s, c)) {
                return 0; /* too many openings pending at once */
            }
        } else if (c == ')' || c == ']' || c == '}') {
            if (!pop(&s, &top_char)) {
                return 0; /* closing with no opening */
            }
            if (top_char != opening_of(c)) {
                return 0; /* mismatched kinds */
            }
        }
    }
    return stack_is_empty(&s);
}

int main(void) {
    char line[MAX_LINE];
    int n;

    if (fgets(line, sizeof line, stdin) == NULL) {
        return 0;
    }
    if (sscanf(line, "%d", &n) != 1) {
        return 0;
    }
    for (int k = 1; k <= n; k++) {
        if (fgets(line, sizeof line, stdin) == NULL) {
            line[0] = '\0';
        }
        line[strcspn(line, "\r\n")] = '\0';
        printf("%d: %s\n", k, is_balanced(line) ? "YES" : "NO");
    }
    return 0;
}

The Stack struct holds data[MAX_STACK] and top. stack_init sets top to 0. stack_is_empty and stack_is_full are one-line comparisons, but calling them instead of repeating the condition everywhere is what prevents off-by-one bounds mistakes.

In push the first thing checked is stack_is_full; only when there is room does it write data[top] and increment top. In pop the order is reversed: check stack_is_empty, decrement top, and only then read data[top], which is the last stored element. That order is the crux: reading before decrementing would read the free slot above the data.

is_balanced walks the string with the index i. If the character c is an opening, it is pushed, and if push returns 0 (full stack) the function answers 0 at once. If it is a closing, the function pops into top_char; if there was nothing to pop it is a closing without an opening, and if top_char differs from opening_of(c) the groupings cross. Every other character does nothing. At the end the formula is correct only when the stack is empty.

Relate that to the worked example, whose six formulas appear below. Line 1, {[()]}, pushes three openings and pops them in reverse order, so it ends empty and prints YES. Line 2, ([)], pops [ when it meets ) and fails on the kind comparison. Line 3, ((), consumes the whole string with one opening still on the stack, so the final stack_is_empty returns 0. Line 4, )(, fails on the very first character because pop returns 0. Lines 5 and 6 print YES: the first mixes digits and operators that are simply ignored, the second contains no grouping at all.

In main each line is read with fgets into a 256-byte buffer and cut at the first \r or \n with strcspn; that is why a Windows line ending does not alter the verdict, as the last test shows. The longest allowed formula (200 characters) fits comfortably. About the overflow test: 33 consecutive openings print NO because the 33rd push returns 0, while 32 openings followed by 32 closings print YES, since they fill the stack exactly without exceeding it. An empty line prints YES because nothing is pushed, and with n = 0 the loop body never runs and nothing is printed.

Code and tests on GitLab

Step-by-step trace · generated by running the code

Step	line	i	c	action	top
1	1	0	{	push	1
2	1	1	[	push	2
3	1	2	(	push	3
4	1	3	)	pop	2
5	1	4	]	pop	1
6	1	5	}	pop	0
7	1	-1	$	end	0
8	2	0	(	push	1
9	2	1	[	push	2
10	2	2	)	mismatch	1
11	3	0	(	push	1
12	3	1	(	push	2
13	3	2	)	pop	1
14	3	-1	$	end	1
15	4	0	)	underflow	0
16	5	0	3	skip	0
17	5	1	*	skip	0
18	5	2	(	push	1
19	5	3	a	skip	1
20	5	4	+	skip	1
21	5	5	b	skip	1
22	5	6	)	pop	0
23	5	7	-	skip	0
24	5	8	[	push	1
25	5	9	c	skip	1
26	5	10	/	skip	1
27	5	11	{	push	2
28	5	12	d	skip	2
29	5	13	}	pop	1
30	5	14	]	pop	0
31	5	-1	$	end	0
32	6	0	x	skip	0
33	6	1	+	skip	0
34	6	2	y	skip	0
35	6	-1	$	end	0

Test cases

Case	Input	Expected output	Actual output	Result
Worked example with mixed cases	6 {[()]} ([)] (() )( 3*(a+b)-[c/{d}] x+y	1: YES 2: NO 3: NO 4: NO 5: YES 6: YES	1: YES 2: NO 3: NO 4: NO 5: YES 6: YES	OK
Zero formulas	0	(empty)	(empty)	OK
Empty formula and single symbols	3 ( }	1: YES 2: NO 3: NO	1: YES 2: NO 3: NO	OK
Stack overflow at the limit	3 ((((((((((((((((((((((((((((((((( ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) (((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))	1: NO 2: NO 3: YES	1: NO 2: NO 3: YES	OK
Windows line endings	2 {[(a)]} [(])	1: YES 2: NO	1: YES 2: NO	OK

Actual outputs: code compiled with gcc 14.4.0 (C17) and run in an isolated container on 13 October 2026.

Complexity

Time is O(L) per formula, where L is its length: each character is examined once, and push and pop are O(1) because they only touch data[top] and the counter. For n formulas the total is O(n · L), which with the stated limits (100 lines of 200 characters) is a few tens of thousands of elementary steps.

Extra memory is O(1) with respect to the input: the stack always occupies MAX_STACK characters plus one integer, no matter how long the formula is. That fixed bound is exactly why the statement must define what happens when it is exceeded; here the formula is declared not balanced.

Common mistakes

• Pushing without checking whether the stack is full. Writing at index 32 goes past the end of the array: undefined behaviour that, depending on the struct layout, may silently corrupt the top field or appear to work.
• Popping without checking whether the stack is empty, so top becomes negative and the read goes before the array. A closing with no opening, as in )(, triggers it immediately.
• Returning 1 at the end of the string without verifying that the stack is empty: (() would then be reported as balanced.
• Counting symbols instead of using a stack: with three counters, ([)] looks correct because each kind has as many openings as closings, yet the closing order is wrong.
• Forgetting to strip the newline left by fgets: it does not affect the groupings because \n is ignored, but it is a bad habit, and with \r\n both characters must go.
• Reading data[top] before decrementing top in pop: that yields the free slot, not the last stored element.

Variants

Report the position of the first error

Instead of YES or NO, print the 1-based position of the first character that breaks the balance. The stack must then also store the index of each opening, for example in a parallel array pos[MAX_STACK]. An invalid closing is reported at its own position; if openings remain at the end, report the position of the oldest one still on the stack.

Dynamic stack that grows on demand

Replace the static array with a pointer obtained from malloc plus a capacity field. When top == capacity, double the capacity with realloc, checking that it does not return NULL. The 32-opening limit then disappears, at the price of a stack_free function that releases the memory. You can revise dynamic allocation in this exercise on malloc and free.

What the professor will ask

“Why does <code>pop</code> return an int and deliver the character through a pointer instead of simply returning the character, and what would go wrong if it returned a <code>char</code>?”

Because two different things must be reported: whether the operation succeeded and which value came out. If the function returned only a char, some value would have to be reserved as an error marker (say '\0'), and that is fragile, since in another use of the same stack that value could be legitimate data. With an int return code and an output parameter, success is separated from the payload, the stack works for any content, and the caller is forced to decide what to do when the stack is empty.

On the syllabus

Stacks and queues are a standard block in data structures courses. The syllabus of ISIS1206 Estructuras de datos at Universidad de los Andes (Colombia), for example, lists «pilas y colas» in its schedule, after lists and before the basic sorting algorithms. The page consulted only names the topic; it does not describe how the structure is implemented nor which exercises are set, so this practice sheet should be read as a generic exercise on the topic and not as a problem taken from that course.

Opinion · Missing context

What should a fixed-size stack do when it fills up? Here the answer is to declare the formula unbalanced, but that is a design decision, not a mathematical truth. Most students never notice the question exists: they declare the array, assume it never overflows, and the sample formulas happily agree with them.

That matters because the habit of ignoring a structure's limit is the one that later ships as a production bug. A top answer on this sheet should state what the stack promises when the space runs out.

Related articles from LaRebelión

Solved exercise: dynamic matrices with malloc and free in CSolved exercise: pass by value and by reference in CSolved exercise: C matrix sums, transpose and trace in C

• Programming exercises
• Solved exercise: interfaces, default methods and multiple implementation in Java
• Solved exercise: polymorphism and dynamic binding in Java

Article generated with AI.larebelion

Byline · Chief editor · English edition · London

“A stack with no overflow check is not a data structure, it is a bug waiting for the thirty-third opening bracket.”