我写了下面的递归代码来匹配括号。在某些情况下,我得到“True”,但如果我在字符串中的某个位置添加新的括号(这是不正确的),我仍然得到“True”。我调试了一下,不明白如何修复,请问如何修复?
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
这是一个相当简洁的基于正则表达式的实现:
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))
一种递归方法如下:
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
这里的想法是递归地用空字符串替换闭括号和闭括号,然后看看最终是否得到空字符串。
更简单但非递归的方法是:
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
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");
}