aboutsummaryrefslogtreecommitdiff
path: root/valid_parentheses.cpp
blob: 9bab0821b4a8eaf1092c60bbda596eb9d7b0c616 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 20. Valid Parentheses
#include "leetcode.h"

/*
 * given a string 's' containing just the characters '(, ), {, }, [, ]',
 * determine if the input string is valid. a input string is valid if open
 * brackets must be closed by the same type of brackets. open brackets must be
 * closed in the correct order. every close bracket has a corresponding open
 * bracket of the same type.
 */

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

int main() {
  Solution obj;
  printf("%d\n", obj.isValid("()"));     // expect: 1
  printf("%d\n", obj.isValid("()[]{}")); // expect: 1
  printf("%d\n", obj.isValid("(]"));     // expect: 0
}