[算法]有效的括号

- 日理万妓 2022-04-08 19:19 219阅读 0赞

伪代码

> 1.得到字符串.  
> 2.创建一个linkedList(用来模拟Stack)  
> 2.非空判断,空返回true  
> 3.遍历字符串  
> 如果第一次碰到三个括号(\[\{中的任意一个右括号直接返回false  
> 相当于这种情况  
> \}\{\}(\{\})//第一个括号是右括号必定是错误的  
> 如果碰到左括号,给linkedlist中添加对应的右括号,碰到右括号,判断linkedlist末尾的右括号是否与其匹配,匹配则删除linkedlist末尾的括号,不匹配直接返回false  
> 相当于这种情况  
> 假设字符串是`{([])}`  
> 遍历完前三个应该是linklist中结果应该是`{([`  
> 遍历完完成应该是linklist中结果应该是`空`

#### 代码实现 ####

public class Test {
        public static boolean isValid(String s) {
    //        用来模拟栈队列,存放右括号
            LinkedList<Character> l = new LinkedList();
    //        对字符串进行非空判断
            if (s.isEmpty()) return true;
    //        遍历字符串
            for (char c : s.toCharArray()) {
    //            如果是"("则将")"压栈
                if (c=='(') {
                    l.add(')');
                } else if (c == '[') {
    //            如果是"["则将"]"压栈
                    l.add(']');
                } else if (c == '{') {
    //            如果是"{"则将"}"压栈
                    l.add('}');
                } else {
    //              如果没有左括号则集合中为空,返回false
    //                或者遇到右括号弹栈时,括号类型不一致,也返回false
                    if (l.isEmpty() || l.removeLast() != c) {
                        return false;
                    }
                }
            }
    //        遍历完成,集合中应当也是空的.
            return l.isEmpty();
        }
    
        public static void main(String[] args) {
            String s = "()[]{}";
            boolean valid = isValid(s);
            System.out.println(valid);
        }
    
    }

> 输出结果:true