dev.to staff

Posted on Aug 28, 2019

Daily Challenge #51 - Valid Curly Braces

#challenge

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 (35)

La blatte • Aug 28 '19 • Edited

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

Alfredo Salzillo • Aug 28 '19

Why you post the uglified code?

La blatte • Aug 28 '19

I just try to find a really short working solution, hence the uglified code! That's why I try to explain it as much as I can after that

Amin • Aug 28 '19

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.

La blatte • Aug 29 '19

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 • Aug 28 '19

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 • Aug 28 '19

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.

Amin • Aug 28 '19

Hey! I didn't know we could embed repl here. Looking dope!

Mazen Touati • Aug 28 '19

Yup, liquid tags are fun 🦄

Donald Feury • Aug 29 '19 • Edited

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)
    }
}

Alfredo Salzillo • Aug 28 '19

Another one line JS solution

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

Amin • Aug 28 '19

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 • Aug 28 '19

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.

Avalander • Aug 30 '19

Smart! I like it!

Kilian • Aug 29 '19

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;
}

Olivier “Ölbaum” Scherler • Aug 29 '19

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.

E. Choroba • Aug 29 '19

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("");

Seiei Miyagi • Aug 28 '19 • Edited

ruby <3

def areCurlyBracesMatched(s)
  s.match?(/\A(?<curly_brace>\{\g<curly_brace>*\})*\z/)
end

Jarod Smith • Aug 28 '19 • Edited

// 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'

View full discussion (35 comments)

DEV Community

Daily Challenge #51 - Valid Curly Braces

Top comments (35)

C++

Read next

Squash Elo Rating System

AgentQL Launch Week Recap—make the web AI-ready

Introduction to Chaos Engineering and LitmusChaos

Linux Kernel and Boot process for Beginner