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

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

1)对于每个开口支架:{ [ (将其推入堆叠.

2)对于每个结束括号:} ] )从堆栈弹出并检查括号的类型是否匹配.如果没有回来false;

即 String中的当前符号是},如果从堆栈中取出其他任何东西,{则false立即返回.

3)如果行尾和堆栈不为空,则返回false,否则true.

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