一. 题目描述
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.
二. 题目分析
输入一串括号字符串，仅仅包含 (]} 这三种括号。判断输入的括号字符串是不是合法的，合法的输出true，不合法输出false。要求”()”、”[]”、”{}”必须成对使用，或者是像”({[]})”这种层层嵌套但保持对称的，也属于合法。
这一题是典型的使用压栈的方式解决的问题，解题思路如下：
三. 示例代码
;class Solution{public:bool isValid(string const& s){if (s.size() == 0)return false;stack<char> temp;for (size_t i = 0; i < s.size(); ++i){if (s[i] == ‘)’ || s[i] == ‘]’ || s[i] == ‘}’){if (temp.empty())return false;else{char k = temp.top();temp.pop();if ((k == ‘(‘ && s[i] != ‘)’) || (k == ‘[‘ && s[i] != ‘]’) || (k == ‘{‘ && s[i] != ‘}’))return false;}}else if (s[i] == ‘(‘ || s[i] == ‘[‘ || s[i] == ‘{‘)temp.push(s[i]);;}return temp.empty(); // 只有当最后栈为空时才说明输入字符串是有效的}};
简单的测试代码：
#include “ValidParentheses.h”int main(){cout << “Please input a string (only the characters ‘(’, ’)’, ’{’, ’}’, ’[’ and ’]’): ” << endl;string input;cin >> input;Solution s;bool result = s.isValid(input);cout.setf(ios::boolalpha);cout << “The result is: ” << result << endl;system(“pause”);return 0;}
四. 小结
这道题需要对括号字符串的每个字符都遍历一遍，因此时间复杂度是O(n)。
，我想一个人旅行，背上简单的行囊，踏上行程，
