logo标签列表

如何检查一个字符串是否平衡？

javastringstack
12
我想测试一个输入字符串是否是平衡的。如果存在匹配的开放和关闭括号、方括号或大括号，那么它将是平衡的。
example:
{} balanced
() balanced
[] balanced
If S is balanced so is (S)
If S and T are balanced so is ST


public static boolean isBalanced(String in)
{
    Stack st = new Stack();

    for(char chr : in.toCharArray())
    {
        if(chr == '{')
            st.push(chr);

    }

    return false;
}

我在选择如何处理问题时遇到了困难。我应该把每个开括号、闭括号或大括号放在一个栈中，然后弹出它们吗？如果我弹出它们，这真的有帮助吗？

1
这是一个作业问题吗？ - David O'Meara
从Javadoc中可以看到，建议使用Deque而不是Stack。Deques也可以用作LIFO（后进先出）堆栈。应该优先使用此接口，而不是传统的Stack类。 - O.Badr
11个回答
28

1) 对于每个左括号： { [ ( 将其推入栈中。

2) 对于每个右括号： } ] ) 从栈中弹出并检查括号类型是否匹配。 如果不匹配，则返回 false；

例如. 字符串中的当前符号是 }，如果从堆栈中弹出的不是 { 中的任何其他字符，则立即返回false。

3) 如果到达行尾而且堆栈不为空，则返回 false，否则返回 true。

11

是的，堆栈是这个任务的合适选择，或者您可以使用递归函数。如果您使用堆栈，则想法是将每个开括号推送到堆栈上，当您遇到闭括号时，检查堆栈顶部是否与其匹配。如果匹配，则弹出它，如果不匹配，则出现错误。完成时，堆栈应该是空的。

import java.util.Stack;
public class Balanced {
    public static boolean isBalanced(String in)
    {
        Stack<Character> st = new Stack<Character>();

        for(char chr : in.toCharArray())
        {
            switch(chr) {

                case '{':
                case '(':
                case '[':
                    st.push(chr);
                    break;

                case ']':
                    if(st.isEmpty() || st.pop() != '[') 
                        return false;
                    break;
                case ')':
                    if(st.isEmpty() || st.pop() != '(')
                        return false;
                    break;
                case '}':
                    if(st.isEmpty() || st.pop() != '{')
                        return false;
                    break;
            }
        }
        return st.isEmpty();
    }
    public static void main(String args[]) {
        if(args.length != 0) {
            if(isBalanced(args[0]))
                System.out.println(args[0] + " is balanced");
            else
                System.out.println(args[0] + " is not balanced");
        }
    }
}
3
以下是一个Java代码示例，用于检测字符串是否平衡。

http://introcs.cs.princeton.edu/java/43stack/Parentheses.java.html

这个想法是 -

  • 对于每个开括号 ( [ {，将其推入堆栈。
  • 对于闭括号 ) ] }，尝试从堆栈中弹出匹配的开括号 ( [ }。如果找不到匹配的开括号，则字符串不平衡。
  • 如果在处理完整个字符串后，堆栈为空，则字符串平衡。否则，字符串不平衡。
2

简单来说，如果它是平衡的，那就意味着你的堆栈应该是空的。

为了实现这一点，在解析}时需要弹出栈。

额外的要求是检查是否在}前是 { 或者弹出的字符是一个 {。

1

我假设null或empty值是一个平衡的字符串，我使用了一个Map来跟踪每个开/闭括号：

static boolean isBalanced(String value) {
    if (value == null || value.isBlank()) {
      return true;
    }

    if (value.length() % 2 != 0) {
      return false;
    }

    Map<Character, Character> bracketMirrors = Map.of('(', ')',
      '{', '}',
      '[', ']');

    Deque<Character> characters = new ArrayDeque<>();

    for (char c : value.toCharArray()) {
      if (bracketMirrors.containsValue(c)) {
        if (characters.isEmpty() || c != bracketMirrors.get(characters.pop())) {
          return false;
        }
      } else {
        characters.push(c);
      }
    }

    return characters.isEmpty();
  }
1
我使用一个整数变量（或者可能是一个字节变量）来解决此问题，每种括号类型只需要一个变量。
public boolean checkWithIntegers(String input) {

    int brackets = 0;

    for (char c: input.toCharArray()) {

        switch (c) {

            case '(':

                brackets++;

                break;

            case ')':

                if (brackets == 0)
                    return false;

                brackets--;

                break;

            default:

                break;
        }
    }


    return brackets == 0;
}

public static void main(String... args) {

    Borrar b = new Borrar();
    System.out.println( b.checkWithIntegers("") );
    System.out.println( b.checkWithIntegers("(") );
    System.out.println( b.checkWithIntegers(")") );
    System.out.println( b.checkWithIntegers(")(") );
    System.out.println( b.checkWithIntegers("()") );

}

OBS

  1. 我假设一个空字符串是平衡的。这个可以通过之前的检查来改变。
  2. 我只使用了一种括号类型的例子，但是其他类型可以很快地添加，只需添加另一个case switch。

希望这有所帮助。 干杯！

0
import java.util.*;
public class Parenthesis
{
    public static void main (String ...argd)
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("enetr string");
        String s=sc.nextLine();
        Stack<Character> st=new Stack<Character>();  
        for (int i=0;i<s.length();++i)
        {
            if((s.charAt(i)=='(')||(s.charAt(i)=='{')||(s.charAt(i)=='['))
            {
                st.push(s.charAt(i));
            }
            else if(st.isEmpty()==false)
            {   
            switch(s.charAt(i))
            {
            case']':
                if(st.pop()!='[')
                {
                    System.out.println("unbalanced");
                    System.exit(0);
                }
                break;
            case'}':
                if(st.pop()!='{')
                {
                    System.out.println("unbalanced");
                    System.exit(0);
                }
                break;
            case')':
                if(st.pop()!='(')
                {
                    System.out.println("unbalanced");
                    System.exit(0);
                }
                break;
            }
            }
        }           
        if(st.isEmpty())
        {
            System.out.println("balanced paranthesis");
        }
        else 
            System.out.println("not balance");
    }   
}
请在您的答案中添加简短的解释，以帮助未来的访问者。 - Nikolay Mihaylov
0
public class IsBalanced {

static Boolean isBalanced(String expStr) {
    Boolean balanced = false;

    int openedBraces = 0;
    int closeddBraces = 0;
    for (int i = 0; i < expStr.length(); i++) {
        if (expStr.charAt(i) == '{' || expStr.charAt(i) == '(' || expStr.charAt(i) == '[') {
            for (int j = i + 1; j < expStr.length(); j++) {
                if (expStr.charAt(i) == '{') {
                    if (expStr.charAt(j) == '}') {
                        closeddBraces++;
                        break;
                    }
                } else if (expStr.charAt(i) == '(') {
                    if (expStr.charAt(j) == ')') {
                        closeddBraces++;
                        break;
                    }
                } else if (expStr.charAt(i) == '[') {
                    if (expStr.charAt(j) == ']') {
                        closeddBraces++;
                        break;
                    }
                }
            }
            openedBraces++;
        }
    }
    System.out.println("openedBraces : " + openedBraces + " , closeddBraces : " + closeddBraces);
    if (openedBraces == closeddBraces) {
        balanced = true;
    }
    return balanced;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    String str = "{[()]}[[]](";
    if (isBalanced(str))
        System.out.println("Balanced");
    else
        System.out.println("NotBalanced");
}

}
0
def balance (string):

    if ((len(string)%2)!=0):
        return("Not Balanced")
    else:
        check_num=[]    
        def check(num1,num2):
            if ((num1=='['and num2==']') or (num1=='{'and num2=='}') or (num1=='('and num2==')')) :
                check_num.append('B')
            else:
                 check_num.append('N')

        i=0        
        while i < (len(string)-1):
            check(string[i],string[i+1])
            i+=2

        if 'N' in check_num:
             return("Not Balanced")
        else:
            return("Balanced")
1
检查连续是否平衡 - Ar_666
0
import java.util.Stack;

public class SyntaxChecker {

    /**
     * This enum represents all types of open brackets. If we have a new type then
     * just add it to this list with the corresponding closed bracket in the other
     * ClosedBracketTypes enum  
     * @author AnishBivalkar
     *
     */
    private enum OpenBracketTypes {
        LEFT_ROUND_BRACKET('('),
        LEFT_SQUARE_BRACKET('['),
        LEFT_CURLY_BRACKET('{');

        char ch;

        // Constructs the given bracket type
        OpenBracketTypes(char ch) {
            this.ch = ch;
        }

        // Getter for the type of bracket
        public final char getBracket() {
            return ch;
        }


        /**
         * This method checks if the current character is of type OpenBrackets
         * @param name
         * @return True if the current character is of type OpenBrackets, false otherwise
         */
        public static boolean contains(final char name) {
            for (OpenBracketTypes type : OpenBracketTypes.values()) {
                if (type.getBracket() == name) {
                    return true;
                }
            }

            return false;
        }
    }

    /**
     * This enum represents all types of Closed brackets. If we have a new type then
     * just add it to this list with the corresponding open bracket in the other
     * OpenBracketTypes enum    
     * @author AnishBivalkar
     *
     */
    private enum CloseBracketTypes {
        RIGHT_ROUND_BRACKET(')'),
        RIGHT_SQUARE_BRACKET(']'),
        RIGHT_CURLY_BRACKET('}');

        char ch;
        CloseBracketTypes(char ch) {
            this.ch = ch;
        }

        private char getBracket() {
            return ch;
        }

        /**
         * This method checks if a given bracket type is a closing bracket and if it correctly
         * completes the opening bracket
         * @param bracket
         * @param brackets
         * @return
         */
        public static boolean isBracketMatching(char bracket, Stack<Character> brackets) {
            // If the current stack is empty and we encountered a closing bracket then this is
            // an incorrect syntax
            if (brackets.isEmpty()) {
                return false;
            } else {
                if (bracket == CloseBracketTypes.RIGHT_ROUND_BRACKET.getBracket()) {
                    if (brackets.peek() == OpenBracketTypes.LEFT_ROUND_BRACKET.getBracket()) {
                        return true;
                    }
                } else if (bracket == CloseBracketTypes.RIGHT_SQUARE_BRACKET.ch) {
                    if (brackets.peek() == OpenBracketTypes.LEFT_SQUARE_BRACKET.getBracket()) {
                        return true;
                    }
                } else if (bracket == CloseBracketTypes.RIGHT_CURLY_BRACKET.ch) {
                    if (brackets.peek() == OpenBracketTypes.LEFT_CURLY_BRACKET.getBracket()) {
                        return true;
                    }
                }

                return false;
            }
        }

        /**
         * This method checks if the current character is of type ClosedBrackets
         * @param name
         * @return true if the current character is of type ClosedBrackets, false otherwise
         */
        public static boolean contains(final char name) {
            for (CloseBracketTypes type : CloseBracketTypes.values()) {
                if (type.getBracket() == name) {
                    return true;
                }
            }

            return false;
        }
    }


    /**
     * This method check the syntax for brackets. There should always exist a
     * corresponding closing bracket for a open bracket of same type.
     * 
     * It runs in O(N) time with O(N) worst case space complexity for the stack
     * @param sentence The string whose syntax is to be checked
     * @return         True if the syntax of the given string is correct, false otherwise
     */
    public static boolean matchBrackets(String sentence) {
        boolean bracketsMatched = true;

        // Check if sentence is null
        if (sentence == null) {
            throw new IllegalArgumentException("Input cannot be null");
        }

        // Empty string has correct syntax
        if (sentence.isEmpty()) {
            return bracketsMatched;
        } else {
            Stack<Character> brackets = new Stack<Character>();
            char[] letters = sentence.toCharArray();

            for (char letter : letters) {

                // If the letter is a type of open bracket then push it 
                // in stack else if the letter is a type of closing bracket 
                // then pop it from the stack
                if (OpenBracketTypes.contains(letter)) {
                    brackets.push(letter);
                } else if (CloseBracketTypes.contains(letter)) {
                    if (!CloseBracketTypes.isBracketMatching(letter, brackets)) {
                        return false;
                    } else {
                        brackets.pop();
                    }
                }
            }

            // If the stack is not empty then the syntax is incorrect
            if (!brackets.isEmpty()) {
                bracketsMatched = false;
            }
        }

        return bracketsMatched;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        String words = "[[][][]Anfield[[]([])[]]becons()]";
        boolean isSyntaxCorrect = SyntaxChecker.matchBrackets(words);

        if (isSyntaxCorrect) {
            System.out.println("The syntax is correct");
        } else {
            System.out.println("Incorrect syntax");
        }
    }
}

对此任何反馈都非常欢迎。如果您发现有什么错误或无用的地方，请批评指正。我只是在努力学习。

1
请您能为您的答案提供一些解释，并将其分解为 SSCCE 吗？很难确定这样确切地解决了用户的问题，似乎超出了用户尝试实现的范围。一个更简洁的代码示例，只回答用户的问题，并结合一些说明，会使这个答案更好。 - Thunderforge
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接