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

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

我在选择做什么时遇到问题。我是否应该将每个左括号或右括号、方括号或大括号放在一个堆栈中，然后将它们弹出？如果我弹出它们，那对我有什么帮助？

原文由 Mike John 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

1. 对于每个开括号： { [ ( 将其推入堆栈。

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

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

1. 如果行尾和堆栈不为空，返回 false ，否则返回 --- true 。

原文由 Nikolay Kuznetsov 发布，翻译遵循 CC BY-SA 3.0 许可协议

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

原文由 Clyde 发布，翻译遵循 CC BY-SA 3.0 许可协议