Tasks Details
easy
1.
Brackets
Determine whether a given string of parentheses (multiple types) is properly nested.
Task Score
62%
Correctness
100%
Performance
40%
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:
function solution($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 ')'.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used PHP
Time spent on task 2 minutes
Notes
not defined yet
Code: 09:32:12 UTC,
php,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
// you can write to stdout for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($S) {
if (strlen($S) == 0)
return 0;
$brackets = new BracketList();
$len = strlen($S);
for ($c = 0; $c < $len; $c++) {
$char = $S[$c];
// echo 'charchter is '.$char;
if ($char == '[' || $char == '{' || $char == '(') {
$brackets->push($char);
} else {
// return 0 if no opening brackets found and
// first bracket is a closing bracket
if ($brackets->stackSize() == 0){
return 0;
}
if ($char === ')') {
if ($brackets->top() === '('){
$brackets->pop();
}
else{
return 0;
}
}
if ($char === '}') {
if ($brackets->top() === '{'){
$brackets->pop();
}
else{
return 0;
}
}
if ($char === ']') {
if ($brackets->top() === '['){
$brackets->pop();
}
else{
return 0;
}
}
}
}
if ($brackets->stackSize() == 0)
return 1;
return 0;
}
class BracketList {
protected $stack;
protected $limit;
public function __construct() {
// $this->limit = $li;
$this->stack = array();
// echo 'heere'.$this->limit;
}
public function stackSize() {
return sizeof($this->stack);
}
public function push($data) {
// echo 'li'.$this->limit.' s '.sizeof($this->stack) ;
//if(sizeof($this->stack) < $this->limit) {
array_unshift($this->stack, $data);
//} else
// throw new RunTimeException('full');
}
public function pop() {
if (!empty($this->stack)) {
array_shift($this->stack);
// } else
// throw new RunTimeException('empty');
}
}
public function isEmpty() {
return empty($this->stack);
}
public function top() {
if (!empty($this->stack))
return $this->stack[0];
}
}
Analysis
Code: 09:32:28 UTC,
php,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
// you can write to stdout for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($S) {
if (strlen($S) == 0)
return 1;
$brackets = new BracketList();
$len = strlen($S);
for ($c = 0; $c < $len; $c++) {
$char = $S[$c];
// echo 'charchter is '.$char;
if ($char == '[' || $char == '{' || $char == '(') {
$brackets->push($char);
} else {
// return 0 if no opening brackets found and
// first bracket is a closing bracket
if ($brackets->stackSize() == 0){
return 0;
}
if ($char === ')') {
if ($brackets->top() === '('){
$brackets->pop();
}
else{
return 0;
}
}
if ($char === '}') {
if ($brackets->top() === '{'){
$brackets->pop();
}
else{
return 0;
}
}
if ($char === ']') {
if ($brackets->top() === '['){
$brackets->pop();
}
else{
return 0;
}
}
}
}
if ($brackets->stackSize() == 0)
return 1;
return 0;
}
class BracketList {
protected $stack;
protected $limit;
public function __construct() {
// $this->limit = $li;
$this->stack = array();
// echo 'heere'.$this->limit;
}
public function stackSize() {
return sizeof($this->stack);
}
public function push($data) {
// echo 'li'.$this->limit.' s '.sizeof($this->stack) ;
//if(sizeof($this->stack) < $this->limit) {
array_unshift($this->stack, $data);
//} else
// throw new RunTimeException('full');
}
public function pop() {
if (!empty($this->stack)) {
array_shift($this->stack);
// } else
// throw new RunTimeException('empty');
}
}
public function isEmpty() {
return empty($this->stack);
}
public function top() {
if (!empty($this->stack))
return $this->stack[0];
}
}
User test case 1:
['']
Analysis
Code: 09:32:42 UTC,
php,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
// you can write to stdout for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($S) {
if (strlen($S) == 0)
return 1;
$brackets = new BracketList();
$len = strlen($S);
for ($c = 0; $c < $len; $c++) {
$char = $S[$c];
// echo 'charchter is '.$char;
if ($char == '[' || $char == '{' || $char == '(') {
$brackets->push($char);
} else {
// return 0 if no opening brackets found and
// first bracket is a closing bracket
if ($brackets->stackSize() == 0){
return 0;
}
if ($char === ')') {
if ($brackets->top() === '('){
$brackets->pop();
}
else{
return 0;
}
}
if ($char === '}') {
if ($brackets->top() === '{'){
$brackets->pop();
}
else{
return 0;
}
}
if ($char === ']') {
if ($brackets->top() === '['){
$brackets->pop();
}
else{
return 0;
}
}
}
}
if ($brackets->stackSize() == 0)
return 1;
return 0;
}
class BracketList {
protected $stack;
protected $limit;
public function __construct() {
// $this->limit = $li;
$this->stack = array();
// echo 'heere'.$this->limit;
}
public function stackSize() {
return sizeof($this->stack);
}
public function push($data) {
// echo 'li'.$this->limit.' s '.sizeof($this->stack) ;
//if(sizeof($this->stack) < $this->limit) {
array_unshift($this->stack, $data);
//} else
// throw new RunTimeException('full');
}
public function pop() {
if (!empty($this->stack)) {
array_shift($this->stack);
// } else
// throw new RunTimeException('empty');
}
}
public function isEmpty() {
return empty($this->stack);
}
public function top() {
if (!empty($this->stack))
return $this->stack[0];
}
}
User test case 1:
['']
Analysis
Code: 09:32:44 UTC,
php,
final,
score:
62
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
// you can write to stdout for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($S) {
if (strlen($S) == 0)
return 1;
$brackets = new BracketList();
$len = strlen($S);
for ($c = 0; $c < $len; $c++) {
$char = $S[$c];
// echo 'charchter is '.$char;
if ($char == '[' || $char == '{' || $char == '(') {
$brackets->push($char);
} else {
// return 0 if no opening brackets found and
// first bracket is a closing bracket
if ($brackets->stackSize() == 0){
return 0;
}
if ($char === ')') {
if ($brackets->top() === '('){
$brackets->pop();
}
else{
return 0;
}
}
if ($char === '}') {
if ($brackets->top() === '{'){
$brackets->pop();
}
else{
return 0;
}
}
if ($char === ']') {
if ($brackets->top() === '['){
$brackets->pop();
}
else{
return 0;
}
}
}
}
if ($brackets->stackSize() == 0)
return 1;
return 0;
}
class BracketList {
protected $stack;
protected $limit;
public function __construct() {
// $this->limit = $li;
$this->stack = array();
// echo 'heere'.$this->limit;
}
public function stackSize() {
return sizeof($this->stack);
}
public function push($data) {
// echo 'li'.$this->limit.' s '.sizeof($this->stack) ;
//if(sizeof($this->stack) < $this->limit) {
array_unshift($this->stack, $data);
//} else
// throw new RunTimeException('full');
}
public function pop() {
if (!empty($this->stack)) {
array_shift($this->stack);
// } else
// throw new RunTimeException('empty');
}
}
public function isEmpty() {
return empty($this->stack);
}
public function top() {
if (!empty($this->stack))
return $this->stack[0];
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
1.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
expand all
Performance tests
large1
simple large positive test, 100K ('s followed by 100K )'s + )(
simple large positive test, 100K ('s followed by 100K )'s + )(
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.14 sec.
running time: >6.00 sec., time limit: 0.14 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.14 sec.
2.
0.004 s
OK
3.
0.248 s
TIMEOUT ERROR,
running time: 0.25 sec., time limit: 0.10 sec.
large2
simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()
simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()
✘
TIMEOUT ERROR
running time: 0.50 sec., time limit: 0.10 sec.
running time: 0.50 sec., time limit: 0.10 sec.
1.
0.500 s
TIMEOUT ERROR,
running time: 0.50 sec., time limit: 0.10 sec.
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.088 s
OK
multiple_full_binary_trees
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+
✔
OK
1.
0.028 s
OK
2.
0.028 s
OK
3.
0.028 s
OK
4.
0.028 s
OK
5.
0.004 s
OK
broad_tree_with_deep_paths
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+
✘
TIMEOUT ERROR
running time: 0.12 sec., time limit: 0.10 sec.
running time: 0.12 sec., time limit: 0.10 sec.
1.
0.108 s
OK
2.
0.116 s
TIMEOUT ERROR,
running time: 0.12 sec., time limit: 0.10 sec.