## DEV Community 👩‍💻👨‍💻 is a community of 929,498 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #51 - Valid Curly Braces

Challenge
Write a function `areCurlyBracesMatched` that takes in a string `s` containing only `{` and/or `}` and returns `true` if `s` is properly matched, and `false` otherwise.

A string `s` is considered properly matched if the string is empty or if every open brace has a corresponding close brace.

Examples
`{{}}` is properly matched.
`{{{` is not properly matched.
`{}{}{}` is properly matched.

```areCurlyBracesMatched("{{{}{}}}"), true; areCurlyBracesMatched("{{"), false; areCurlyBracesMatched("{}}"), false; areCurlyBracesMatched(""), true;```

Happy coding!

This challenge comes from theonlydaryl on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

## Top comments (37) Here we go!

``````f=a=>{c=0;i=0;while(i<a.length&&c>=0){c+=a[i]=='{'?1:-1;++i}return !c}
``````

Read character by character, add 1 to a counter if the character is an opening bracket, subtract 1 if it is a closing one. If the counter EVER gets negative (hence, if we get in an "open close close" situation) of if it is positive on the last iteration (hence, if we get in an "open open close" situation), we consider the chain as invalid.

``````f("{{{}{}}}")
true
f("{{")
false
f("{}}")
false
f("")
true
f("}{")
false
`````` Amin

I think that these kind of challenges prior more the algorithm part than the gulfing part. Since ES6, JavaScript has became a good language for gulfing but sometimes self explanatory code is better than gulfed one.

Its a matter of taste I guess. Exactly! As a matter of fact, I prefer Alfredo Salzillo's solution as it is a clear and pretty oneliner. On these challenges I try to come up with solutions different than a straight-forward approach (and tend to golf it too), which I couldn't manage to do on this one. That explains the ugly part of the solution I provided, which is kinda disappointing! Alfredo Salzillo

One line JS

``````const areCurlyBracesMatched = string => [...string]
.map(c => c === '{' ? 1 : -1)
.reduce((acc, n) => acc + (acc >= 0 ? n : -1), 0) === 0;

areCurlyBracesMatched ("{}{}{}") // true
areCurlyBracesMatched ("}{") // false
areCurlyBracesMatched ("{{}") // false
areCurlyBracesMatched ("{{}}{}{}") // true
`````` Mazen Touati

I like this type of challenges that encourage the use of queues or/and stacks concepts. Anyway, this is my solution that suggests an early exist as soon as a brace does not match. Kilian

Let's see what you guys think...

### C++

``````#include <iostream>
#include <stack>
#include <string>

bool isValidCurlyBraceExpression(std::string expressionToCheck);

void test(std::string expression, bool expectation);

int main(int argc, char* argv[])
{
test("{{{}{}}}", true);
test("{{", false);
test("{}}", false);
test("}{", false);
test("", true);
return 0;
}

void test(std::string expression, bool expectation){
bool returnValue = isValidCurlyBraceExpression(expression);
if(returnValue == expectation)
std::cout << "Test succeeded \"" << expression << "\" = " << returnValue << std::endl;
else
std::cerr << "Test failed!   \"" << expression << "\" = " << returnValue << std::endl;
}

bool isValidCurlyBraceExpression(std::string expressionToCheck)
{
std::stack<char> openedBraces;
for (auto it = expressionToCheck.begin(); it != expressionToCheck.end(); ++it) {
if (*it == '{') {
openedBraces.push('{');
}
else if (*it == '}') {
if (openedBraces.empty())
return false;
openedBraces.pop();
}
}
if (openedBraces.empty())
return true;
else
return false;
}

`````` Donald Feury • Edited on

Here we Go!... I swear I'm funny sometimes

curly.go

``````package curly

// Validate will take a string of curly brackets, check it, and determine if it is valid (balanced and in proper order)
// "{}" = true
// "{{}" = false
// "{{}}" = true
func Validate(curlies string) bool {
if curlies == "" {
return true
}

balanced := 0

for _, curly := range curlies {
switch curly {
case '{':
balanced++
case '}':
balanced--
}
if balanced < 0 {
return false
}
}

return balanced == 0
}

``````

curly_test.go

``````package curly

import "testing"

var testCases = []struct {
description string
input       string
expected    bool
}{
{
"empty string",
"",
true,
},
{
"simple string",
"{}",
true,
},
{
"incorrect curlies",
"{{}",
false,
},
{
"out of order curlies",
"{}}{",
false,
},
{
"many curlies",
"{}{{{}{}}}",
true,
},
}

func TestValidate(t *testing.T) {
for _, test := range testCases {
if result := Validate(test.input); result != test.expected {
t.Fatalf("FAIL: %s, Validate(%s): %v - expected %v", test.description, test.input, result, test.expected)
}
t.Logf("PASS: %s", test.description)
}
}

`````` Olivier “Ölbaum” Scherler

With the examples given, this challenge is identical to Challenge 29: Xs and Os, because counting the braces suffice to get the answer.

If you add `areCurlyBracesMatched("}{"), false;`, though, it’s different.

I think it’s a pity that the examples for a lot of these challenges are missing some important cases that would help when the explanation is not completely clear. Alfredo Salzillo

Another one line JS solution

``````const areCurlyBracesMatched = string => !Array(Math.flor(string.length / 2))
.fill(0)
.reduce(s => s.replace(/{}/, ''), string);

`````` Amin

You made a typo: `Math.flor` should be `Math.floor`. Otherwise good take at using a regular expression. Unfortunately, it does not work for cases like

``````areCurlyBracesMatched("const f = a => { console.log(a)}")
``````

As the curly braces are separated by other characters. Alfredo Salzillo

Write a function areCurlyBracesMatched that takes in a string s containing only { and/or } and returns true if s is properly matched, and false otherwise.

For this challenge the string can only contain '{' or '}', so your example is not a valid input.

It's obvious that it can't be resolved with a regexp for the general case. ``````// validateBraces :: String -> Bool
const validateBraces = braces => braces ? [...braces.trim()]
.filter(char => char === '{' || char === '}')
.map(brace => brace === '{'? brace = 1 : -1)
.reduce((sum, value) => sum < 0 ? false : sum += value) === 0: 'No Braces'
`````` Michael Kohl • Edited on

F#:

``````module BraceMatching

type ParseResult = bool

type ParseState = int option

let private openBrace (state : ParseState) : ParseState =
Option.map (fun n -> n + 1) state

let private closingBrace (state : ParseState) : ParseState =
match Option.map (fun n -> n - 1) state with
| Some n when n >= 0 -> Some n
| _ -> None

let areCurlyBracesMatched (s : string) : ParseResult =
(Some 0, s)
||> Seq.fold (fun result ->
function
| '{' -> openBrace result
| '}' -> closingBrace result
| _ -> failwith "Invalid character")
|> function
| Some 0 -> true
| _ -> false
``````

• Used custom types to represent the parsing state and result.
• `Option` + pattern matching for the actual solution.

Tests:

``````module BraceMatchingTest

open FsUnit.Xunit
open Xunit
open BraceMatching

[<Fact>]
let matched() = areCurlyBracesMatched ("{{{}{}}}") |> should equal true

[<Fact>]
let unbalanced() = areCurlyBracesMatched ("{{") |> should equal false

[<Fact>]
let ``double close``() = areCurlyBracesMatched ("{}}") |> should equal false

[<Fact>]
let empty() = areCurlyBracesMatched ("") |> should equal true
`````` Python

``````import re
def areCurlyBracesMatched(s):
if len(re.findall('[^{}]',s)) > 0 : return False
while True:
start = s.find('{')
end = s.find('}')
if start < end and (start >=0 and end >= 0):
s=s.replace('{','',1)
s=s.replace('}','',1)
else:
break
if len(s) == 0: return True
else:   return False
`````` Oleksii Filonenko

Rust:

``````fn valid_curly_braces(input: &str) -> bool {
let mut counter = 0;
for c in input.chars() {
match c {
'{' => counter += 1,
'}' => counter -= 1,
_ => (),
};
if counter < 0 {
return false;
}
}
counter == 0
}
`````` Functional JS with Tail Call Optimization (TCO)

``````const test = require('./tester');

const validateTCO = (acc, str) => (
typeof str !== 'string'     ? false
: str.length === 0          ? acc === 0
: str.charAt(0) === '{'     ? validateTCO (acc + 1, str.slice(1))
: str.charAt(0) === '}'     ? validateTCO (acc - 1, str.slice(1))
: validateTCO (acc, str.slice(1))
);

const validate = str => validateTCO (0, str);

test (validate, [
{
in: ['{{}}'],
out: true,
},
{
in: ['{{{'],
out: false,
},
{
in: ['{}{}{}'],
out: true,
},
{
in: ['{abc {def} {{}}}'],
out: true,
},
]);
`````` Josh • Edited on

Ahh, this old trick. I've done it for at least two interviewers this summer. Terrific way for them to determine how good I am at building Rails applications, but, I digress.

``````def balanced?(string, left, right)
raise ArgumentError.new("Can't compare individual characters to a character sequence") if left.length >1 || right.length > 1
string.chars.reduce(0) do |count, char|
return false if count < 0
count += 1 if char == left
count -= 1 if char == right
end.zero?
end

def areCurlyBracesMatched(string)
balanced?(string, "{", "}")
end
`````` K.V.Harish

My solution in js

``````const areCurlyBracesMatched = (str) => {
let counter = 0;
str.split('').every((brace) => !((counter = brace === '{' ? counter+1 : counter-1) < 0));
return !counter;
};
`````` Simple JS solution

Iterate through the string and count up when you encounter a "{" and down when not.
Check after every iteration, if the last character was a closing brace too much and return false if so.
Finally, return true when the amount of opening braces matches the amount of closing braces (i == 0).

``````function areCurlyBracesMatched(s){
i = 0;
for (el of s){
i += "{" == el ? 1 : -1;
if (i < 0) return false;
}
return !i
};
`````` Rafael Acioly • Edited on

Python solution

``````from collections import Counter

def are_curly_braces_matched(braces: str) -> bool:
closing_brace = '}'
opening_brace = '{'

if braces == closing_brace:
return False

elements = Counter(braces)
return elements.get(opening_brace) == elements.get(closing_brace)
`````` Amin • Edited on

My take at the challenge written in Haskell.

``````countUnmatchedBraces :: Int -> Char -> Int
countUnmatchedBraces count character
| character == '{' = count - 1
| character == '}' = count + 1
| otherwise = count

unmatchedBraces :: String -> Int
unmatchedBraces = foldl countUnmatchedBraces 0

zero :: Int -> Bool
zero = (==) 0

areCurlyBracesMatched :: String -> Bool
areCurlyBracesMatched = zero . unmatchedBraces

man :: IO ()
main = do
putStrLn \$ show \$ areCurlyBracesMatched "const f = a => { console.log(a)" -- False
putStrLn \$ show \$ areCurlyBracesMatched "const f = a => { console.log(a) }" -- True
putStrLn \$ show \$ areCurlyBracesMatched "const f = a => console.log(a)" -- True
`````` Tiash • Edited on

OCaml solution:

``````let rec balance (count, array) =
let comb char = match char with
| '{' -> 1
| '}' -> -1
| _ -> 0
in match array with
| [] -> count = 0
| c :: cl -> if count < 0 then false
else balance ((count + comb c), cl);;

let explode str =
let rec expl idx array =
if idx < 0 then array
else expl (idx - 1) (str.[idx] :: array)
in expl (String.length str - 1) [];;

let isBalanced string = balance (0, explode (string));;
``````

Some outputs:

``````# isBalanced "";;
- : bool = true
# isBalanced "{";;
- : bool = false
# isBalanced "}";;
- : bool = false
# isBalanced "}{";;
- : bool = false
# isBalanced "{}";;
- : bool = true
# isBalanced "{}{}{}";;
- : bool = true
# isBalanced "{}{{{{{}{}}}}{}}";;
- : bool = true
# isBalanced "{}{{{{{}{}}}}{}";;
- : bool = false
``````

This solution skips the characters different from braces:

``````# isBalanced "abc";;
- : bool = true
# isBalanced "{abc}";;
- : bool = true
# isBalanced "{abc{}";;
- : bool = false
# isBalanced "{abc{a}}";;
- : bool = true
`````` E. Choroba

Perl solution.

Just remove all the `{}`s until there's nothing to remove. If you got an empty string, the input was valid.

``````#!/usr/bin/perl
use warnings;
use strict;

sub are_curly_braces_matched {
my (\$s) = @_;
1 while \$s =~ s/{}//g;
return ! length \$s
}

use Test::More tests => 4;

ok are_curly_braces_matched('{{{}{}}}');
ok ! are_curly_braces_matched('{{');
ok ! are_curly_braces_matched('{}}');
ok are_curly_braces_matched("");
``````

#### Head to your account's Settings to...

🌚 Enable dark mode
🔠 Change your default font
📚 Adjust your experience level to see more relevant content