DEV Community

Daily Challenge #51 - Valid Curly Braces

dev.to staff on August 28, 2019

Challenge Write a function areCurlyBracesMatched that takes in a string s containing only { and/or } and returns true if s is properly matched, and...
Collapse
 
ynndvn profile image
La blatte • 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
Collapse
 
alfredosalzillo profile image
Alfredo Salzillo

Why you post the uglified code?

Collapse
 
ynndvn profile image
La blatte

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

Thread Thread
 
aminnairi profile image
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.

Thread Thread
 
ynndvn profile image
La blatte

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!

Collapse
 
alfredosalzillo profile image
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
Collapse
 
mazentouati profile image
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.

Collapse
 
aminnairi profile image
Amin

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

Collapse
 
mazentouati profile image
Mazen Touati

Yup, liquid tags are fun πŸ¦„

Collapse
 
dak425 profile image
Donald Feury • 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)
    }
}

Collapse
 
alfredosalzillo profile image
Alfredo Salzillo

Another one line JS solution

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

Collapse
 
aminnairi profile image
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.

Collapse
 
alfredosalzillo profile image
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.

Collapse
 
avalander profile image
Avalander

Smart! I like it!

Collapse
 
kilitr profile image
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;
}

Collapse
 
oscherler profile image
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.

Collapse
 
choroba profile image
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("");
Collapse
 
hanachin profile image
Seiei Miyagi • Edited

ruby <3

def areCurlyBracesMatched(s)
  s.match?(/\A(?<curly_brace>\{\g<curly_brace>*\})*\z/)
end
Collapse
 
jasman7799 profile image
Jarod Smith • 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'
Collapse
 
rafaacioly profile image
Rafael Acioly • Edited

Python solution

from collections import Counter


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

    if braces[0] == closing_brace:
        return False

    elements = Counter(braces)
    return elements.get(opening_brace) == elements.get(closing_brace)
Collapse
 
tiash990 profile image
Tiash • Edited

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
Collapse
 
brightone profile image
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
}
Collapse
 
matrossuch profile image
Mat-R-Such

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
Collapse
 
gnsp profile image
Ganesh Prasad

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,
    },
]);
Collapse
 
thepeoplesbourgeois profile image
Josh • Edited

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
Collapse
 
kvharish profile image
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;
}; 
Collapse
 
delixx profile image
DeLiXx • Edited

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
};
Collapse
 
aminnairi profile image
Amin • Edited

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

Try it online.

Collapse
 
toanleviet95 profile image
Toan Le Viet • Edited

I use a flag which is increased if it was '{' and decrease if it was '}'

Collapse
 
serbuvlad profile image
Șerbu Vlad Gabriel

Did you make sure that sequences like "}{" are correctly identified as invalid?

Collapse
 
toanleviet95 profile image
Toan Le Viet

My mistake for this case. Many thanks :D

Collapse
 
alexkhismatulin profile image
Alex Khismatulin • Edited

Elegant JS solution

areCurlyBracesMatched = s => {
  while(s.includes('{}')) s = s.replace('{}', '');
  return !s;
}
Collapse
 
alfredosalzillo profile image
Alfredo Salzillo

I love this one.

Collapse
 
olekria profile image
Olek Ria

Some F#

let rec areCurlyBracesMatched (x:string) =
    match "{}" |> x.IndexOf with
    | -1 ->  x.Length = 0
    | _  ->  x.Replace("{}", "") |> areCurlyBracesMatched
Collapse
 
juyn profile image
Xavier Dubois πŸ‡«πŸ‡· • Edited

Damn, there is never any PHP solutions, I've to get to it !