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

Question

我想测试输入字符串是否平衡。如果有一个匹配的开始和结束括号、括号或大括号，这将是平衡的。

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;
}

我在选择做什么时遇到了问题。我是否应该将每个开始或结束的括号、括号或大括号放在一个堆栈中，然后将它们弹出？如果我把它们拿出来，这对我有什么帮助？

Answer 1

以下是一个Java代码示例，用于检测字符串是否平衡。

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

这个想法是-

• 对于每个开始括号( [ {，将其推送到堆栈上。
• 对于结束括号) ] }，尝试从堆栈中弹出匹配的开始括号( [ }。如果找不到匹配的开始括号，则字符串不平衡。
• 如果处理完完整的字符串后，堆栈是空的，那么字符串是平衡的。否则字符串不平衡。

Answer 2

是的，堆栈是任务的合适选择，或者你可以使用递归函数。如果你使用堆栈，那么你的想法是推动堆栈上的每个打开括号，当你遇到一个关闭括号时，你检查堆栈的顶部是否匹配它。如果匹配，就把它弹出，如果不匹配，那就是错误。完成后，堆栈应该是空的。

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");
        }
    }
}

Answer 3

1）对于每个打开的括号：{ [ (将其推送到堆栈。

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

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

3）如果行结束和堆栈不是空的，返回false，否则返回true。