【问题描述】

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.

问题来源：Valid Parentheses

【问题分析】

题意：有一字符串，只包含'('，')'，'{'，'}'，'['，']'这些符号，让我们判断输入字符串是否有效，有效指的是这些符号的闭合需按照正常顺序，例如"()"，"({})"这些都属于有效字符串，而"({)}"就属于无效字符串。 考虑使用栈这个容器，最近出现的左边符号必须被先闭合，而栈的属性是FILO，符合题意。 将这些符号分为两类'('，'{'，'['属于左边类符号，')'，'}'，']'属于右边类符号。 遍历字符串，出现左边类的符号时，将其压入栈；一旦出现右边类的符号时，将其与栈顶元素匹配，假如匹配正确，则将栈顶元素取出，继续遍历下一下字符；一旦匹配不正确，直接返回该字符串无效。遍历完字符串，以栈是否为空判断字符串是否有效，为空则有效。时间最多为遍历一次字符串，时间复杂度为O(N)。

【源代码】

class Solution { public: bool isValid(string s) { stack<char> mystack; for(int i = 0; i < s.length(); i++) { if (s[i] == '(' || s[i] == '{' || s[i] == '['){ mystack.push(s[i]); } else { if (mystack.empty()) return false; if (mystack.top() == '(' && s[i] != ')') return false; if (mystack.top() == '{' && s[i] != '}') return false; if (mystack.top() == '[' && s[i] != ']') return false; mystack.pop(); } } return mystack.empty(); } };