020_有效的括号

风扫地

1. /*
   
2. 给定一个[只包括] '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
   
3. 有效字符串需满足：
   
4.     左括号必须用相同类型的右括号闭合。
   
5.     左括号必须以正确的顺序闭合。
   
6. 注意空字符串可被认为是有效字符串。
   
7. 示例 1:
   
8. 输入: "()"
   
9. 输出: true
   
10. 示例 2:
    
11. 输入: "()[]{}"
    
12. 输出: true
    
13. 示例 3:
    
14. 输入: "(]"
    
15. 输出: false
    
16. 示例 4:
    
17. 输入: "([)]"
    
18. 输出: false
    
19. 示例 5:
    
20. 输入: "{[]}"
    
21. 输出: true
    
22. */

复制代码

1. #include<stack>
   
2. #include<string>
   
3. #include <iostream>
   
4. using namespace std;
   
5. class Solution {
   
6. public:
   
7.     bool isValid(string s) {
   
8.         stack<char> sk;
   
9.         char match      = 0;
   
10.         char temp       = 0;
    
11.         int  len        = s.length();
    
12.         for(int i = 0;i <len;i++)
    
13.         {
    
14.             temp = s.at(i);
    
15.             if(sk.empty()==true)
    
16.             {
    
17.                 sk.push(temp);
    
18.             }
    
19.             else
    
20.             {
    
21.                 match = 0;
    
22.                 switch(temp)
    
23.                 {
    
24.                     case ')':
    
25.                         if(sk.top()=='(')
    
26.                         {
    
27.                             match = 1;
    
28.                         }
    
29.                     break;
    
30.                     case '}':
    
31.                         if(sk.top()=='{')
    
32.                         {
    
33.                             match = 1;
    
34.                         }
    
35.                     break;
    
36.                     case ']':
    
37.                         if(sk.top()=='[')
    
38.                         {
    
39.                             match = 1;
    
40.                         }  
    
41.                     break;
    
42.                     default:
    
43.                         //match = 0;
    
44.                     break;
    
45.                 }
    
46.                
    
47.                 if(match == 1)
    
48.                 {
    
49.                     sk.pop();
    
50.                 }
    
51.                 else
    
52.                 {
    
53.                     sk.push(temp);
    
54.                 }
    
55.             }
    
56.         }
    
57.         return sk.empty();  
    
58.     }
    
59. };
    

复制代码

测试代码：

1. int main(void)
   
2. {
   
3.     Solution solution;
   
4.     string s("{[]}");
   
5.     cout << solution.isValid(s) << endl;
   
6.     return 0;
   
7. }

复制代码

提交结果：

1. 执行用时 : 8 ms, 在Valid Parentheses的C++提交中击败了97.02% 的用户
   
2. 内存消耗 : 8.7 MB, 在Valid Parentheses的C++提交中击败了68.92% 的用户
   
3. 76 / 76 个通过测试用例 状态：通过

复制代码

Nice.