works/solutions/leetcode/cpp/20.cpp


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
44
45
46
47
48
49
50
51
52
53
54
55

#include <string>

using std::string;

#include <stack>

class Solution
{
public:
    inline static char get_companion(char c)
    {
        switch (c)
        {
        case ')':
            return '(';
        case ']':
            return '[';
        default:
            return '{';
        }
    }

    bool isValid(string s)
    {
        std::stack<char> stack;

        for (const auto c : s)
        {
            switch (c)
            {
            case '(':
            case '[':
            case '{':
            {
                stack.push(c);
                break;
            }
            case ')':
            case ']':
            default:
            {
                if (stack.empty())
                    return false;
                const auto top = stack.top();
                const char companion = get_companion(c);
                if (top != companion)
                    return false;
                stack.pop();
            }
            }
        }

        return stack.empty();
    }
};