我曾经编写过使用堆栈来检查平衡方程的软件，但现在被要求编写类似的递归算法来检查嵌套括号和括号是否正确。
好的例子：() [] () ([]()[])
不好的例子：( (] ([)]
假设我的函数叫做：isBalanced。
每次调用时应该评估一个较小的子字符串（直到达到2个左括号的基本情况）吗？ 还是应该始终评估整个字符串并向内移动索引？
12个回答
58
首先，针对您最初的问题，要注意如果您正在处理非常长的字符串，则不要每次调用函数时都制作几乎相同但缺少一个字母的精确副本。因此，您应该使用索引或验证您选择的语言是否在幕后制作副本。
其次，我对所有在此处使用堆栈数据结构的答案都有异议。我认为您的任务的重点是让您理解使用递归时您的函数调用会创建一个堆栈。您不需要使用堆栈数据结构来保存括号，因为每个递归调用都是隐式堆栈上的新条目。
我将用一个匹配“（”和“）”的C程序进行演示。添加其他类型，如“[”和“]”，是读者的练习。在函数中，我仅保持了我的字符串位置（作为指针传递），因为递归是我的堆栈。
其次，我对所有在此处使用堆栈数据结构的答案都有异议。我认为您的任务的重点是让您理解使用递归时您的函数调用会创建一个堆栈。您不需要使用堆栈数据结构来保存括号，因为每个递归调用都是隐式堆栈上的新条目。
我将用一个匹配“（”和“）”的C程序进行演示。添加其他类型，如“[”和“]”，是读者的练习。在函数中，我仅保持了我的字符串位置（作为指针传递），因为递归是我的堆栈。
/* Search a string for matching parentheses. If the parentheses match, returns a
* pointer that addresses the nul terminator at the end of the string. If they
* don't match, the pointer addresses the first character that doesn't match.
*/
const char *match(const char *str)
{
if( *str == '\0' || *str == ')' ) { return str; }
if( *str == '(' )
{
const char *closer = match(++str);
if( *closer == ')' )
{
return match(++closer);
}
return str - 1;
}
return match(++str);
}
使用以下代码进行测试：
const char *test[] = {
"()", "(", ")", "", "(()))", "(((())))", "()()(()())",
"(() ( hi))) (())()(((( ))))", "abcd"
};
for( index = 0; index < sizeof(test) / sizeof(test[0]); ++index ) {
const char *result = match(test[index]);
printf("%s:\t", test[index]);
*result == '\0' ? printf("Good!\n") :
printf("Bad @ char %d\n", result - test[index] + 1);
}
输出：
(): Good!
(: Bad @ char 1
): Bad @ char 1
: Good!
(())): Bad @ char 5
(((()))): Good!
()()(()()): Good!
(() ( hi))) (())()(((( )))): Bad @ char 11
abcd: Good!
- indiv
3
50
有很多方法可以做到这一点，但最简单的算法是从左到右依次处理，将堆栈作为参数传递。
FUNCTION isBalanced(String input, String stack) : boolean
IF isEmpty(input)
RETURN isEmpty(stack)
ELSE IF isOpen(firstChar(input))
RETURN isBalanced(allButFirst(input), stack + firstChar(input))
ELSE IF isClose(firstChar(input))
RETURN NOT isEmpty(stack) AND isMatching(firstChar(input), lastChar(stack))
AND isBalanced(allButFirst(input), allButLast(stack))
ELSE
ERROR "Invalid character"
这里是Java的实现。请注意，我已经将其更改为栈在字符串的前面而不是后面进行推送，以方便操作。我还修改了它，使它只跳过非括号符号，而不将其报告为错误。
static String open = "([<{";
static String close = ")]>}";
static boolean isOpen(char ch) {
return open.indexOf(ch) != -1;
}
static boolean isClose(char ch) {
return close.indexOf(ch) != -1;
}
static boolean isMatching(char chOpen, char chClose) {
return open.indexOf(chOpen) == close.indexOf(chClose);
}
static boolean isBalanced(String input, String stack) {
return
input.isEmpty() ?
stack.isEmpty()
: isOpen(input.charAt(0)) ?
isBalanced(input.substring(1), input.charAt(0) + stack)
: isClose(input.charAt(0)) ?
!stack.isEmpty() && isMatching(stack.charAt(0), input.charAt(0))
&& isBalanced(input.substring(1), stack.substring(1))
: isBalanced(input.substring(1), stack);
}
测试工具：
String[] tests = {
"()[]<>{}",
"(<",
"]}",
"()<",
"(][)",
"{(X)[XY]}",
};
for (String s : tests) {
System.out.println(s + " = " + isBalanced(s, ""));
}
输出：
()[]<>{} = true
(< = false
]} = false
()< = false
(][) = false
{(X)[XY]} = true
- polygenelubricants
2
1如果问题是使用递归检查括号是否平衡，您不希望将堆栈作为递归函数的参数显式传递。 - dynamic
6这种三元嵌套使得阅读变得非常困难。这不是代码竞赛。你可以使用明确的控制流程。 - Rig
3
这个想法是保持一个开放括号的列表，如果你发现一个关闭括号，就检查它是否关闭了上次打开的括号：
- 如果这些括号匹配，那么从已打开的括号列表中删除最后一个，并继续对字符串的其余部分进行递归检查。
- 否则，你找到了一个关闭了从未打开过的括号，因此它不平衡。
当字符串最终为空时，如果括号列表也为空（即所有括号都已关闭），则返回true，否则返回false
算法（Java）:
public static boolean isBalanced(final String str1, final LinkedList<Character> openedBrackets, final Map<Character, Character> closeToOpen) {
if ((str1 == null) || str1.isEmpty()) {
return openedBrackets.isEmpty();
} else if (closeToOpen.containsValue(str1.charAt(0))) {
openedBrackets.add(str1.charAt(0));
return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
} else if (closeToOpen.containsKey(str1.charAt(0))) {
if (openedBrackets.getLast() == closeToOpen.get(str1.charAt(0))) {
openedBrackets.removeLast();
return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
} else {
return false;
}
} else {
return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
}
}
测试:
public static void main(final String[] args) {
final Map<Character, Character> closeToOpen = new HashMap<Character, Character>();
closeToOpen.put('}', '{');
closeToOpen.put(']', '[');
closeToOpen.put(')', '(');
closeToOpen.put('>', '<');
final String[] testSet = new String[] { "abcdefksdhgs", "[{aaa<bb>dd}]<232>", "[ff{<gg}]<ttt>", "{<}>" };
for (final String test : testSet) {
System.out.println(test + " -> " + isBalanced(test, new LinkedList<Character>(), closeToOpen));
}
}
输出:
abcdefksdhgs -> true
[{aaa<bb>dd}]<232> -> true
[ff{<gg}]<ttt> -> false
{<}> -> false
请注意，我已经导入了以下类：
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
- Luca Mastrostefano
2
public static boolean isBalanced(String str) {
if (str.length() == 0) {
return true;
}
if (str.contains("()")) {
return isBalanced(str.replaceFirst("\\(\\)", ""));
}
if (str.contains("[]")) {
return isBalanced(str.replaceFirst("\\[\\]", ""));
}
if (str.contains("{}")) {
return isBalanced(str.replaceFirst("\\{\\}", ""));
} else {
return false;
}
}
- jot
2
平衡括号（JS）
更直观的解决方案是使用堆栈，如下所示：
function isBalanced(str) {
const parentesis = {
'(': ')',
'[': ']',
'{': '}',
};
const closing = Object.values(parentesis);
const stack = [];
for (let char of str) {
if (parentesis[char]) {
stack.push(parentesis[char]);
} else if (closing.includes(char) && char !== stack.pop()) {
return false;
}
}
return !stack.length;
}
console.log(isBalanced('{[()]}')); // true
console.log(isBalanced('{[(]]}')); // false
console.log(isBalanced('([()]')); // false并且使用递归函数（不使用堆栈），可能会像下面这样：
function isBalanced(str) {
const parenthesis = {
'(': ')',
'[': ']',
'{': '}',
};
if (!str.length) {
return true;
}
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (parenthesis[char]) {
for (let j = str.length - 1; j >= i; j--) {
const _char = str[j];
if (parenthesis[_char]) {
return false;
} else if (_char === parenthesis[char]) {
return isBalanced(str.substring(i + 1, j));
}
}
} else if (Object.values(parenthesis).includes(char)) {
return false;
}
}
return true;
}
console.log(isBalanced('{[()]}')); // true
console.log(isBalanced('{[(]]}')); // false
console.log(isBalanced('([()]')); // false* 正如@Adrian所提到的，您还可以在递归函数中使用堆栈而无需向后查找
- Lior Elrom
1
从逻辑角度来看，这并不重要——如果您保留所有当前未平衡的括号的堆栈，并将其传递到每个递归步骤中，您将永远不需要向后查找，因此无论您在每个递归调用上切割字符串还是仅增加索引并仅查看当前的第一个字符都没有关系。
在大多数编程语言中，具有非可变字符串的语言，缩短字符串可能比在堆栈上传递稍大的字符串更昂贵（从性能方面考虑）。另一方面，在像C这样的语言中，您可以只是增加char数组中的指针。我想这取决于语言，哪种方法更“有效”。从概念上讲，它们都是等效的。
- Adrian Petrescu
1
在Scala编程语言中，我会这样做：
请编辑以使其完美。
我只是建议在Scala中进行转换。
def balance(chars: List[Char]): Boolean = {
def process(chars: List[Char], myStack: Stack[Char]): Boolean =
if (chars.isEmpty) myStack.isEmpty
else {
chars.head match {
case '(' => process(chars.tail, myStack.push(chars.head))
case ')' => if (myStack.contains('(')) process(chars.tail, myStack.pop)
else false
case '[' => process(chars.tail, myStack.push(chars.head))
case ']' => {
if (myStack.contains('[')) process(chars.tail, myStack.pop) else false
}
case _ => process(chars.tail, myStack)
}
}
val balancingAuxStack = new Stack[Char]
process(chars, balancingAuxStack)
}
请编辑以使其完美。
我只是建议在Scala中进行转换。
- MrOnyancha
0
我认为这取决于你的设计。你可以使用两个计数器或带有两个不同符号的堆栈，也可以使用递归来处理它，区别在于设计方法。
- Gabriel Ščerbák
0
func evalExpression(inStringArray:[String])-> Bool{
var status = false
var inStringArray = inStringArray
if inStringArray.count == 0 {
return true
}
// determine the complimentary bracket.
var complimentaryChar = ""
if (inStringArray.first == "(" || inStringArray.first == "[" || inStringArray.first == "{"){
switch inStringArray.first! {
case "(":
complimentaryChar = ")"
break
case "[":
complimentaryChar = "]"
break
case "{":
complimentaryChar = "}"
break
default:
break
}
}else{
return false
}
// find the complimentary character index in the input array.
var index = 0
var subArray = [String]()
for i in 0..<inStringArray.count{
if inStringArray[i] == complimentaryChar {
index = i
}
}
// if no complimetary bracket is found,so return false.
if index == 0{
return false
}
// create a new sub array for evaluating the brackets.
for i in 0...index{
subArray.append(inStringArray[i])
}
subArray.removeFirst()
subArray.removeLast()
if evalExpression(inStringArray: subArray){
// if part of the expression evaluates to true continue with the rest.
for _ in 0...index{
inStringArray.removeFirst()
}
status = evalExpression(inStringArray: inStringArray)
}
return status
}
- siva k
1
为了帮助 OP 解决当前的问题，可以在回答中添加一些解释说明。 - ρяσѕρєя K
0
PHP检查平衡括号的解决方案
<?php
/**
* @param string $inputString
*/
function isBalanced($inputString)
{
if (0 == strlen($inputString)) {
echo 'String length should be greater than 0';
exit;
}
$stack = array();
for ($i = 0; $i < strlen($inputString); $i++) {
$char = $inputString[$i];
if ($char === '(' || $char === '{' || $char === '[') {
array_push($stack, $char);
}
if ($char === ')' || $char === '}' || $char === ']') {
$matchablePairBraces = array_pop($stack);
$isMatchingPair = isMatchingPair($char, $matchablePairBraces);
if (!$isMatchingPair) {
echo "$inputString is NOT Balanced." . PHP_EOL;
exit;
}
}
}
echo "$inputString is Balanced." . PHP_EOL;
}
/**
* @param string $char1
* @param string $char2
* @return bool
*/
function isMatchingPair($char1, $char2)
{
if ($char1 === ')' && $char2 === '(') {
return true;
}
if ($char1 === '}' && $char2 === '{') {
return true;
}
if ($char1 === ']' && $char2 === '[') {
return true;
}
return false;
}
$inputString = '{ Swatantra (() {} ()) Kumar }';
isBalanced($inputString);
?>
- Swatantra Kumar
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
())(上运行测试程序时，我得到了“Bad @ char 3”的错误提示，这看起来对我来说是正确的。http://ideone.com/e.js/VBM8IU - indivis_balanced来委托这个函数。整个“返回第一个不匹配项的指针”其实是一个实现细节，调用者不应该必须了解它。 - ruakh