有效括号序列

[题](有效括号序列_牛客题霸_牛客网 (nowcoder.com))

1. 代码

   class Solution {
   public:
       /**
        * 
        * @param s string字符串 
        * @return bool布尔型
        */
       bool isValid(string s) {
           // write code here
                   stack<char> stack;
           for (const auto &item: s) {
               if (item == '[' || item == '(' || item == '{') {
                   stack.push(item);
               } else if (item == ']' || item == ')' || item == '}'){
                   if(stack.empty()){
                       return false;
                   }//防止栈区为empty，还取出top
                   if(item==']'){
                       if(stack.top()!='['){
                           return false;
                       }
                       stack.pop();
                   }else if(item==')'){
                       if(stack.top()!='('){
                           return false;
                       }
                       stack.pop();
                   }else if(item=='}'){
                       if(stack.top()!='{'){
                           return false;
                       }
                       stack.pop();
                   }
               }
           }
           if(!stack.empty()){
               return false;//防止出现只有右开口符号的请情况
           }
           return true;
       }
       
   };

   改进代码

   class Solution {
   public:
       /**
        * 
        * @param s string字符串 
        * @return bool布尔型
        */
       bool isValid(string s) {
           // write code here
           stack<char> stack;
           for(const auto& item:s){
               if(item=='['){
                   stack.push(']');
               }else if(item=='{'){
                   stack.push('}');
               }else if(item=='('){
                   stack.push(')');
               } else if(stack.empty()){
                   //防止空取top
                   return false;
               } else if(item==stack.top()){
                   stack.pop();
               }else{//提高执行效率，如果不对应，就直接返回
                   return false;
               }
           }
           return stack.empty();
           //当true,则说明一一对应
       }
   };

2. 提示

   

3. 理解

   • 整体只会遍历一次，遇到开口向右的符号就存进stack，反之对比出栈

4. 问题

   • 为什么返回stack.empty()

     有且仅当，一一对应时才能返回