Valid Parentheses
最后更新于：2022-04-01 22:56:03
**一. 题目描述**
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。要求”()”、”[]”、”{}”必须成对使用，或者是像”({[]})”这种层层嵌套但保持对称的，也属于合法。
这一题是典型的使用压栈的方式解决的问题，解题思路如下：
1. 计数 i = 0
2. 根据字符指针取出括号字符串的当前字符，如果当前字符为空，跳到5
3. 如果当前字符是左括号( (]}这三种 )，直接压入栈
4. 如果当前字符是右括号( )]}这三种 )，从栈中弹出一个元素，弹出的元素如果和当前字符匹配，i++，回到2；否则，返回false
5. 如果栈为空，返回true；否则返回false。
**三. 示例代码**
~~~
#include
#include
#include
using namespace std;
class Solution
{
public:
bool isValid(string const& s)
{
if (s.size() == 0)
return false;
stack 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]);
else return false;
}
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)。
';