1

我想检查一个字符串是否与递归平衡。我在论坛上发现了一些与这个问题相关的其他帖子，一些答案是我不懂的编程语言。在 Stack Overflow 上阅读了类似的问题后，我可以用堆栈来完成，我该如何递归地做到这一点？

private static boolean isBalanced(String s, char match)
{
    char c;

    if(s.isEmpty())
        return true;

    for(int i = 0; i < s.length(); i++)
    {
        c = s.charAt(i); 

        if(c == '{') 
            return isBalanced(s.substring(i+1), '}');

        else if(c == '[')
            return isBalanced(s.substring(i+1), ']');

        else if(c == '(')
            return isBalanced(s.substring(i+1), ')');

        // Closing matches.
        else if(c == match)
            return true;

    }

    return 
}

请帮忙。

编辑：不，我不希望任何人为我编写代码，事实上，我会很高兴知道如何去做。这就是为什么我不理解其他语言的答案，因为它们太特定于该语言而不是算法。

EDIT2：是平衡的是 {}()[] 和任何组合，例如 [()]

4

5 回答 5

3

使用递归的想法与使用堆栈的原理相同。调用堆栈是您的 LIFO 结构，您根据它进行调用。

取一个简单的平衡字符串：

String bal = "(This is (perfectly) balanced.)";

首先要做的事情 - 让我们建立我们的条件。

  • 我们不关心任何不是括号、大括号或括号的东西。我们可以忽略任何不是这三个角色之一的角色。
  • 如果我们遇到括号、大括号或方括号，我们会立即递归并在字符串的其余部分搜索它的匹配项。也就是说，如果我从 开始bal，我会在 上递归bal.substring(1)。

我不会使用循环，因为您仍在遍历整个字符串。我宁愿使用它，以减少我必须回溯的字符数量。

于 2013-02-19T03:47:03.443 回答
3

这是算法，我刚刚尝试过并且有效。想法是，在每个左括号上，您都希望右括号是相同类型的。上面的函数需要这样调用isBalanced("([2+3])", 0, new Stack<Character>())。预期的字符使用stack.

public static boolean isBalanced(String s, int i, Stack<Character> expected) {
    /* end has reached and not expecting anything then break */
    if (i == s.length())
        return expected.isEmpty();

    char c = s.charAt(i);
    /* expecting something and it is a closing type */
    /* then it should match expecting type */
    if (c == '}' || c == ')' || c == ']') {
        char e = expected.isEmpty() ? '\0' : expected.pop();
        if(e != c)
            return false;
    }

    if(c == '{') 
        expected.push('}');
    else if(c == '[')
        expected.push(']');
    else if(c == '(')
        expected.push(')');

    /* call recursively with i + 1 */ 
    return isBalanced(s, i + 1, expected);

}

这是代码的非堆栈版本：调用是这样的isBalanced2("{[]}[()]", 0, '\0') < 0 ? false : true。

public static int isBalanced2(String s, int i, char match)
{
    if(i >= s.length())
        return match == '\0' ? 0 : -1;

    char c;
    int j;
    for(j = i; j < s.length(); j++)
    {
        c = s.charAt(j); 
        /* any of the closing type */
        if(c == ']' || c == '}' || c == ')') {
            return c == match ? j : -1;
        }

        if(c == '{') 
            j = isBalanced2(s, j + 1, '}');

        else if(c == '[')
            j = isBalanced2(s, j + 1, ']');

        else if(c == '(')
            j = isBalanced2(s, j + 1, ')');

        if(j == -1)
            break;
    }

    return match != '\0' ? -1 : j;
}
于 2013-02-19T03:57:47.877 回答
1

直接循环是这里的快速解决方案：

private static boolean isBalanced(String s)
{
    char[] chars = new char[s.length()];
    int size = 0;
    for (int i = 0; i < s.length(); i++)
    {
        char c = s.charAt(i);
        if (c == '{' || c == '(' || c == '[') chars[size++] = c;
        if (c == '}' && (size == 0 || chars[--size] != '{')) return false;
        if (c == ')' && (size == 0 || chars[--size] != '(')) return false;
        if (c == ']' && (size == 0 || chars[--size] != '[')) return false;
    }

    return true;
}

算法的复杂度是O(N)，没有子字符串等。

于 2013-02-19T08:24:00.293 回答
0

让我们正式地处理这个问题，以增加我们在没有大量调试的情况下提出可行的解决方案的可能性。

什么是平衡弦？这是一个简单的语法：

BalancedString: Sequence end-of-string;

Sequence:
    Fragment Sequence |
    (* empty *);

Fragment:
    '(' Sequence ')' |
    '[' Sequence ']' |
    '{' Sequence '}' |
    any-character-not-in-'()[]{}';

请注意，此语法生成的字符串(hello)[[good]{bye}]具有多个“顶级”组。

现在让我们把它变成一个递归下降解析器。每个非终结符（BalancedString、Sequence和Fragment）都成为一个函数。我们将从解析“BalancedString”非终端的函数开始：

private static bool parseBalancedString(String input, int offset) {
    offset = parseSequence(input, offset);
    return offset == input.length();
}

请注意，此函数期望parseSequence返回它停止解析的偏移量。接下来写吧parseSequence。我们将使用循环而不是直接递归。

private static int parseSequence(String input, int offset) {
    bool parseSucceeded = true;
    while (parseSucceeded) {
        int newOffset = parseFragment(input, offset);
        parseSucceeded = newOffset > offset;
        newOffset = offset;
    }
    return offset;
}

请注意，parseSequence期望parseFragment返回它停止解析的偏移量，如果失败，它应该返回它传递的偏移量。现在我们将编写parseFragment. 我们将从三个相似的产生式中提取公共代码到一个辅助函数中。

private static int parseFragment(String input, int offset) {
    if (offset >= input.length()) {
        return offset;
    }

    switch (input.charAt(offset)) {
        case '(': return helpParseFragment(input, offset, ')');
        case '[': return helpParseFragment(input, offset, ']');
        case '{': return helpParseFragment(input, offset, '}');
        default: return offset + 1;
    }
}

辅助函数期望接收开启者的偏移量，以便在失败时返回该偏移量。如果成功，它将返回刚刚过去的偏移量。

private static int helpParseFragment(String input, int offset, char closer) {
    int newOffset = parseSequence(input, offset + 1);
    if (newOffset > offset && newOffset < input.length() && input.charAt(newOffset) == closer) {
        return newOffset + 1;
    } else {
        return offset;
    }
}
于 2013-02-19T04:42:45.410 回答
0 
import java.util.*;
class Solution{

   public static void main(String []argh)
   {
      Scanner sc = new Scanner(System.in);


      while (sc.hasNext()) 
      {
         String input=sc.next();
         Stack<Character> stacky = new Stack<>();
          int x=0,y=0,z=0,a=0,b=0,c=0;
         for (int i = 0; i < input.length(); i++) 
         {

                switch(input.charAt(i)) 
                {
                    case '[' : a++; break;
                    case '{' : b++;break;

                     case '(' : c++;
                    break;

                    case ']' :x++; break;
                    case '}' : y++; break;

                     case ')' :
                            z++;
                    break;



                default: stacky.push(input.charAt(i));
          }


            //Complete the code

            if(x==a && y==b && z==c)
                {

                System.out.println("true");

                 }
             else
                 {
                 System.out.println("false");
             }




      }

   }
   }}

http://www.geekpandit.com/2016/07/25/simple-balanced-parenthesis-problem-stack-implementation/。

于 2016-08-03T11:38:46.083 回答