CODEWITHSUNDEEP
python
Benny
Benny

Reputation: 498

Matching Parenthesis Recursivley

I wrote The recursive code bellow to match parenthesis. In some cases I get 'True' but if I add new parenthesis in some place in the string, which is incorrect, I still get 'True'. I debugged it and I didn't understand how to fix it, how can I correct it?

def is_balanced(parenthesis):
    if len(parenthesis) %2 == 1:
        return False
        left_value = parenthesis[:1:]
        right_value = parenthesis[-1::]
        return is_balanced(parenthesis[1:-1:]) if left_value != right_value else 
        True

    print(is_balanced('(()()[]()())')) => #True
    print(is_balanced('(()()[[()())')) => #still True

Upvotes: 2

Views: 92

Answers (3)

sangram
sangram

Reputation: 415

var inputString = "[[1+1]+(2*2)-{3/3}<}]";

console.log("Input String:", inputString);

//remove non bracket characters
var regexNonBracketPattern = /[^<>{}[\]()]/g;
var bracketOnlyString = inputString.replace(regexNonBracketPattern, "");

//find if it has any matching bracket
console.log("Bracket Only String:", bracketOnlyString);

var regexMatchingBracketsPattern = /(\(\)|\[\]|\<\>|\{\})+/;
let hasAnyMatchingBracket =
regexMatchingBracketsPattern.test(bracketOnlyString);

console.log("Has Any Matching Bracket:", hasAnyMatchingBracket);

var counter = 1;
while (regexMatchingBracketsPattern.test(bracketOnlyString)) {
    bracketOnlyString = bracketOnlyString.replace(regexMatchingBracketsPattern,"");

    if (bracketOnlyString == "") {
        break;
    } else {
        console.log("Counter Value:", counter);
        console.log("Iteration No (" + counter + "):", bracketOnlyString);
    }
    counter++;
}

if (bracketOnlyString.length != 0) {
    console.log("Provided string has some non matching brackets");
} else {
    console.log("Provided string has all matching brackets");
}

Upvotes: 0

user2390182
user2390182

Reputation: 73460

Here is a fairly concise regular expression based implementation:

import re

def is_balanced(par):
    pattern = re.compile('\(\)|{}|\[\]')  # matches '()', '[]', or '{}'
    return not par or bool(pattern.search(par)) and is_balanced(pattern.sub('', par))

Upvotes: 2

Ma0
Ma0

Reputation: 15204

One recursive approach would be the following:

def is_balanced(parenthesis):
    l = len(parenthesis)
    if l == 0:
        return True
    else:
        if '()' in parenthesis or '[]' in parenthesis:
            return is_balanced(parenthesis.replace('()', '').replace('[]', ''))
        else:
            return False

print(is_balanced('(()()[]()())'))  # True
print(is_balanced('(()()[[()())'))  # False

The idea here is to replace closed parenthesis and closed brackets with an empty string recursively and see if you end up with an empty string.

A simpler but not recursive approach would be:

def is_balanced(parenthesis):
    brackets = ['()', '{}', '[]']
    while any(x in parenthesis for x in brackets):
        for br in brackets:
            parenthesis = parenthesis.replace(br, '')
    return not parenthesis

Upvotes: 2

Related Questions