Brackets at app.codility.com/programmers in C Explained: Determine whether a given string of parentheses (multiple types) is properly nested.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Lesson 7 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 3 Jul 2025
Problem
A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:• S is empty;
• S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.
Write a function:
int solution(char *S);
that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.
For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.
Write an efficient algorithm for the following assumptions:
• N is an integer within the range [0..200,000];
• string S is made only of the following characters: '(', '{', '[', ']', '}' and/or ')'.
Note:
There are three types of brackets, which are ( open with ) close; { open with } close; and [ open with ] close.The issue with algorithm problems is not just to produce a working solution function, but it is to produce a working (correct) solution that is efficient (performance).
The properly nested pairs are: (), {}, and [] . Each open bracket on the left must have a close bracket on the right. Closed pairs cannot be interleaved, like ({)} for example, which should be (){} or {}() . No group or subgroup of pairs can start with a close bracket. The total number of brackets must be even.
Let V = "[{([{()}])}]"
Let W = "({[({[]})]})"
Let S = "[{([{()}])}]({[({[]})]})"
This is a properly nested string consisting of two subgroups. Note that at the center of each subgroup is an open and close bracket. Immediately on the left and right of that, are open and close brackets (which may be different kind of brackets). This continues outwards until a subgroup is formed.
Strategy
Do not forget that an empty string is a properly nested string. So the first thing to do, is to check if the string is empty. If it is, return 1 and the algorithm stops.A string or substring should not begin with a close bracket. If that is the case, return 0 and the algorithm stops. Otherwise begin to push the open brackets on the left into a stack. When a closing bracket is encountered, it must be closing the last bracket pushed to the stack (center of subgroup). If that is not the case, then return 0 and algorithm stops. If that is the case, then (so far so good) the last bracket in the stack and the bracket coming in, form a properly nested pair. In that case, remove the last bracket in the stack and do not push the in-coming bracket to the stack. The stack loses one bracket at the top. Note that a closing bracket followed by its opening bracket, such as }{ , does not form a properly nested pair.
This continues until all the brackets in the given string have been accessed. If the stack is not empty at this time, then not all the opening brackets were closed. In that case, return 0 (not properly nested).
Solution in O(N) Time
The C stack developed in the lesson for this task (problem) is used here. A program with the solution function is as follows (read through the code and comments). Pay particular attention to the solution function definition and to the user code in the main() function.#include <stdio.h>The output is:
#include <stdlib.h>
struct Element {
int value;
struct Element *previous;
};
struct Stack {
int size;
struct Element *back;
int (*top)();
void (*push)(int);
void (*pop)();
} stack;
int top() {
if (stack.size > 0) //stack has at least 1 element
return stack.back->value; //use -> to obtain value from a pointer
else
printf("Error: No element to remove from stack!\n");
}
void push(int inte) {
struct Element *element = malloc(sizeof(struct Element)); //declaring and creating the object, element
if (element != 0) { //check whether allocation of memory element was successful
element->value = inte;
if (stack.size == 0) { //first element
element->previous = 0;
stack.back = element;
stack.size = stack.size + 1; //add 1 to size
}
else {
element->previous = stack.back; //previous points to previous element
stack.back = element; //stack points to new element
stack.size = stack.size + 1; //add 1 to size
}
}
else {
printf("Error: New element could not be created!\n");
exit(1);
}
}
void pop() {
if (stack.size > 0) { //stack has at least 1 element
struct Element *lastElement = stack.back;
stack.back = lastElement->previous; //point to previous element
free(lastElement); //free last (top) element from memory
stack.size = stack.size - 1; //subtract 1 from size
}
else {
printf("Error: No element to remove from stack!\n");
exit(1);
}
}
int solution(char *S) {
if (S[0] == '\0') //length of string is 0
return 1;
int i = 0;
while (S[i] != '\0') {
char c = S[i];
if ((c == '{') || (c == '(') || (c == '['))
stack.push(c);
else if ((c == '}' || c == ')' || c == ']') && stack.size != 0) { //next iteration
char b = stack.top();
stack.pop();
if ((b=='{'&&c!='}') || (b=='('&&c!=')') || (b=='['&&c!=']')) //catches [) in "([)()]"
return 0;
}
else
return 0; //closing bracket without open bracket in next iteration
++i;
}
if (stack.size > 0)
return 0;
return 1;
}
int main(int argc, char **argv)
{
//Assigning stack attributes and methods (functions)
stack.size = 0;
stack.top = top;
stack.push = push;
stack.pop = pop;
//user code begins
char P[] = "{[()()]}";
int ret1 = solution(P);
printf("%i\n", ret1);
char Q[] = "([)()]";
int ret2 = solution(Q);
printf("%i\n", ret2);
char R[] = "";
int ret3 = solution(R);
printf("%i\n", ret3);
//user code begins
return 0;
}
1
0
1
Note the condition, &&(stk.size != 0) in the overall else-if condition. That condition can easily be omitted (forgotten). Also appreciate the difference between the use of || and && . The last "return 1" in the solution() function, means no abnormality was detected.
Any string in C ends with '\0' , which is not typed in a string content in double quotes. So, an empty string has just '\0' and not ' '.
The solution function is:
int solution(char *S)
which means the length of the string is not among the parameters (arguments). So a string array has to be sent for *S, and a while loop used, to end when '\0' is met.
At app.codility.com/programmers the scoring and detected time complexity for this solution() is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Thanks for reading.