2016.6.17——Valid Parentheses

Valid Parentheses

本题收获：

1.stack的使用

2.string和char的区别

　　题目：　　

　　Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

　　The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

　　注意题目中只是输入了一个字符串如：“{}（]” 而不是{“{}[”,"[]"}

　　思路：

　　leetcode:用stack，括号为左边压入栈，右边的和栈顶对比，所有的都匹配返回true,不匹配返回false

　　代码：

 1 bool isValid(string s) {
 2     stack<char> st;
 3     for(char c : s){
 4         if(c == '('|| c == '{' || c == '['){
 5             st.push(c);
 6         }else{
 7             if(st.empty()) return false;
 8             if(c == ')' && st.top() != '(') return false;
 9             if(c == '}' && st.top() != '{') return false;
10             if(c == ']' && st.top() != '[') return false;
11             st.pop();
12         }
13     }
14     return st.empty();

　　我的测试代码：

 1 class MyClass
 2 {
 3 public:
 4     bool isValid(string str)
 5     {
 6         stack<char> st;            //is <char> not<string>
 7         for (size_t i = 0; i < str.size(); i++)
 8         {
 9             if (str[i] == '(' || str[i] == '{' || str[i] == '[')
10             {
11                 st.push(str[i]);
12             }
13             else
14             {
15                 if (str[i] == ')' && st.top() != '(') return false;
16                 if (str[i] == ']' && st.top() != '[') return false;
17                 if (str[i] == '}' && st.top() != '{') return false;                //不写st.pop()有什么差别
18             }    
19         }
20         return true;                                                            //st.empty()
21     }
22 };

　　完整代码：

 1 // Valid Parentheses.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include "iostream"
 6 #include "stack"
 7 #include "stack"
 8 using namespace std;
 9 
10 class MyClass
11 {
12 public:
13     bool isValid(string str)
14     {
15         stack<char> st;            //is <char> not<string> 栈的定义，注意是string/char
16         for (size_t i = 0; i < str.size(); i++)
17         {
18             if (str[i] == '(' || str[i] == '{' || str[i] == '[')
19             {
20                 st.push(str[i]);
21             }
22             else
23             {
24                 if (str[i] == ')' && st.top() != '(') return false;
25                 if (str[i] == ']' && st.top() != '[') return false;　　　　　　　　　//st.top()，有括号“，”栈的.后面都有（）
26                 if (str[i] == '}' && st.top() != '{') return false;                //不写st.pop()有什么差别
27             }    
28         }
29         return true;                                                            //st.empty()
30     }
31 };
32 /*
33 class MyClass
34 {
35 public:
36     bool isValid(string str)
37     {
38         stack<char> st;            //is <char> not<string>
39         for (char c : str)
40         {
41             if (c == '(' || c == '{' || c == '[')
42             {
43                 st.push(c);
44             }
45             else
46             {
47                 if (c == ')' && st.top() != '(') return false;
48                 if (c == ']' && st.top() != '[') return false;
49                 if (c == '}' && st.top() != '{') return false;
50                 st.pop();
51             }
52         }
53         return st.empty();
54     }
55 
56 
57 };*/
58 
59 
60 int _tmain(int argc, _TCHAR* argv[])
61 {
62     string str = "({[]})";
63     int m = 0;
64     MyClass solution;
65     m = solution.isValid(str);
66     cout << m << endl;
67     system("pause");
68     return 0;
69 }