java - 使用堆栈检查分隔符

Question

代码检查字符串中的分隔符是否平衡。我一直在使用堆栈来解决这个问题。我将字符串遍历到末尾，每当遇到开始分隔符时，我将其插入堆栈，对于遇到的每个结束分隔符，我检查堆栈是否为空(如果为空则报告错误)，然后弹出堆栈以匹配弹出的字符和遇到的结束分隔符。我忽略字符串中的所有其他字符。在遍历结束时，我检查堆栈是否为空(即检查所有开始分隔符是否平衡)。如果不为空，我会报告错误。尽管我已经交叉检查了很多次，但代码似乎将每个字符串报告为无效(即带有不平衡的分隔符)。代码如下:

import java.util.*;
public class delimiter {
    public static void main(String args[]){
        String s1 = "()";
        String s2 = "[}[]";
        if(delimitercheck(s1)){
            System.out.println("s1 is a nice text!");
        }
        else
            System.out.println("S1 is not nice");
        if(delimitercheck(s2)){
            System.out.println("s2 is a nice text!");
        }
        else
            System.out.println("S2 is not nice");
    }
    public static boolean delimitercheck(String s){
        Stack<Character> stk = new Stack<Character>();
        if(s==null||s.length()==0)//if it's a null string return true
            return true;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){
                stk.push(s.charAt(i));
            }
            if(s.charAt(i)==')'||s.charAt(i)=='}'||s.charAt(i)==']'){
                if(stk.isEmpty()){
                    return false;
                }
                if(stk.peek()==s.charAt(i)){
                    stk.pop();
                }
            }
        }
        if(stk.isEmpty()){
            return true;
        }
        else
            return false;
    }
}

谁能指出我哪里出错了？

Answer 1

您的错误在这里:

            if(stk.peek()==s.charAt(i)){
                stk.pop();
            }

i '第一个字符不应等于 stk.peek() 。应该关闭它。即如果 stk.peek() == '{' , s.charAt(i)应该是'}' ， 等等。

此外，如果当前右括号与堆栈顶部不匹配，则应返回 false。

您可以为每种类型的括号设置单独的条件，也可以创建 Map<Character,Character>将每个左括号映射到其相应的右括号，然后您的条件将变为:

            if(map.get(stk.peek())==s.charAt(i)){
                stk.pop();
            } else {
                return false;
            }

哪里map可以初始化为:

Map<Character,Character> map = new HashMap<>();
map.put('(',')');
map.put('{','}');
map.put('[',']');