括号匹配问题栈的应用

爱被打了一巴掌 2022-12-21 04:46 126阅读 0赞

**题目描述**

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
    括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
    示例1
    输入"["
    返回值
    false
    
    示例2
    输入"[]"
    返回值true

**import java.util.*;
    
    
    public class Solution {
        
        /**
         * 
         * @param s string字符串 
         * @return bool布尔型
         */
        
        //思路：把括号的后一半入栈  若紧接着字符数组的下一个元素 不等于出栈元素 则返回false
        public boolean isValid (String s) {
        
            // write code here
            Stack<Character> stack = new Stack<Character>();
            for(char c:s.toCharArray()){
        
                if(c =='(')
                    stack.push(')');
                else if(c =='[')
                    stack.push(']');
                else if(c =='{')
                    stack.push('}');
                else if(stack.empty()||stack.pop()!=c)
                    return false;
            }
            return stack.empty();
        }
    }**

class Solution {
        
        public boolean isValid(String s) {
        
             //如果是左括号则直接入栈
             Stack<Character> stack=new Stack<>();
               char[] charArray=s.toCharArray();
               for(char ch:charArray){
        
                    if(ch=='('||ch=='{'||ch=='['){
        
                        stack.push(ch);
                    }else{
        
    
                 //如果是右括号，并且此时栈不为空 出栈
                      if(!stack.isEmpty()){
        
                          if(ch==')'){
        
                              if(stack.pop()!='(')
                              return false;
                          }else if(ch=='}'){
        
                              if(stack.pop()!='{')
                              return false;
                          }else if(ch==']'){
        
                                if(stack.pop()!='[')
                                return false;
                          }
                      }
                        //如果此时是右括号，但栈为空
                        else{
        
                            return false;
                          }
                    }
                   
               }
               return stack.isEmpty();
        }
    }
    
    
    
    
    
    
    
    
    
    
    
    /*class Solution {
        public boolean isValid(String s) {
            int n = s.length();
            if (n % 2 == 1) {
                return false;
            }
    
            Map<Character, Character> pairs = new HashMap<Character, Character>() {
        {
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }};
            Deque<Character> stack = new LinkedList<Character>();
            for (int i = 0; i < n; i++) {
                char ch = s.charAt(i);
                if (pairs.containsKey(ch)) {
                    if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                        return false;
                    }
                    stack.pop();
                } else {
                    stack.push(ch);
                }
            }
            return stack.isEmpty();
        }
    }
    **/