20 Valid Parentheses
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.
- "([)]"
自己代码:
- class Solution {
- public: bool isValid(string s) {
- stack < char > parent;
- for (char c: s) {
- if (c == ‘ [‘ || c == ‘ (‘ || c == ‘ {‘) parent.push(c); //左括号进栈
- else if (parent.empty()) return false;
- else { //有右括号且与栈顶匹配,则栈顶元素出栈
- if (c == ‘]‘ && parent.top() == ‘ [‘) parent.pop();
- else if (c == ‘
- }‘ && parent.top() == ‘ {‘) parent.pop();
- else if (c == ‘)‘ && parent.top() == ‘ (‘) parent.pop();
- else return false;
- }
- }
- if (parent.empty()) return true;
- else return false;
- }
- };
巧妙的方法,discussion区发现:
遇到左括号,则使对应右括号进栈,例如:遇到“{”,进栈“}”。遇到“[”,进栈“]”。遇到“(”,进栈“)”。
非右括号,则看它是否与栈顶元素相等,相等即匹配。
- public boolean isValid(String s) {
- Stack < Character > stack = new Stack < Character > ();
- for (char c: s.toCharArray()) {
- if (c == ‘ (‘) //遇到左右括号,使括号进栈
- stack.push(‘)‘);
- else if (c == ‘ {‘) stack.push(‘
- }‘);
- else if (c == ‘ [‘) stack.push(‘]‘);
- else if (stack.isEmpty() || stack.pop() != c) //遇到非右括号,若栈空,返回false。否则弹出栈顶元素,看其是否与当前元素相等,否则错误
- return false;
- }
- return stack.isEmpty();
- }
用switch语句写:
- bool isValid(string s) {
- stack<char> paren;
- for (char& c : s) {
- switch (c) {
- case ‘(‘:
- case ‘{‘:
- case ‘[‘: paren.push(c); break;
- case ‘)‘: if (paren.empty() || paren.top()!=‘(‘) return false; else paren.pop(); break;
- case ‘}‘: if (paren.empty() || paren.top()!=‘{‘) return false; else paren.pop(); break;
- case ‘]‘: if (paren.empty() || paren.top()!=‘[‘) return false; else paren.pop(); break;
- default: ; // pass
- }
- }
- return paren.empty() ;
- }
来源: http://www.bubuko.com/infodetail-2392493.html