[LeetCode] Valid Parentheses

This is a classic problem of the application of stacks. The idea is, each time we meet a (, { or[, we push it to a stack. If we meet a ), } or ], we check if the stack is not empty and the top matches it. If not, return false; otherwise, we pop the stack. Finally, if the stack is empty, returntrue; otherwise, return false.

The code is as follows, very straight-forward.

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         stack<char> paren;
 5         for (int i = 0; i < s.length(); i++) {
 6             if (s[i] == '(' || s[i] == '{' || s[i] == '[')
 7                 paren.push(s[i]);
 8             else if (s[i] == ')' || s[i] == '}' || s[i] == ']') {
 9                 if (paren.empty()) return false;
10                 if (!match(paren.top(), s[i])) return false;
11                 paren.pop();
12             }
13         }
14         return paren.empty();
15     }
16 private:
17     bool match(char s, char t) {
18         if (t == ')') return s == '(';
19         if (t == '}') return s == '{';
20         if (t == ']') return s == '[';
21     }
22 };