top-interview-questions/easy/others/05_valid_parentheses.cc


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

class Solution {
public:
    char matchingChar(char c) {
        switch (c) {
            case ')': return '(';
            case '}': return '{';
            case ']': return '[';
            default: throw;
        }
    }

    bool isValid(string s) {
        // ([])  -- valid
        // ([)]  -- invalid
        std::stack<char> st;
        for (char c : s) {
            switch (c) {
                case '(':
                case '{':
                case '[': {
                    st.push(c);
                    break;
                }
                case ')':
                case '}':
                case ']': {
                    const char expected = matchingChar(c);
                    if (st.empty() ||
                        (st.top() != expected)) {
                        return false;
                    }
                    st.pop();
                    break;
                }
                default:
                    throw;
            }
        }
        return st.empty();
    }
};