算法与数据结构之栈(stack)

一.栈的简单运用

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> 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();
    }
};

还可以利用map的键与值的关系解题
代码如下

bool isValid(string s) {
    stack<char> temp;
    map<char, char> m = { {']','['},{')','('},{'}','{'} };
for (int i = 0; i < s.size(); i++) {
if (s[i] == '[' || s[i] == '(' || s[i] == '{')
            temp.push(s[i]);
else if (s[i] == ']' || s[i] == ')' || s[i] == '}')
        {
if (temp.empty()||temp.top() != m[s[i]]) return false;
else temp.pop();
        }
    }
return temp.empty();
}