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.

Solution:

1. use stack, if you get ( [ {, push into the stack, if you get ) ] }, check if it matches the top of the stack then pop it. otherwise directly return false. At the end if the stack is empty, then all the parentheses are matched. otherwise return false.
2. Important thing! when the stack is empty you can not refer its top!!!!

class Solution {

public:

bool isValid\(string s\) {

    if \(s.length\(\) == 0\) return true;

    if \(s.length\(\) % 2 == 1\) return false;



    stack<char> p;

    for \(int i = 0; i < s.length\(\); i++\) {

        if \(s\[i\] == '\(' \|\| s\[i\] == '\[' \|\| s\[i\] == '{'\) {

            p.push\(s\[i\]\);

        } else if \(p.size\(\) == 0\) {

            return false;

        } else if \(s\[i\] == '\)' && p.top\(\) == '\('

                  \|\| s\[i\] == '\]' && p.top\(\) == '\['

                  \|\| s\[i\] == '}' && p.top\(\) == '{'\) {

            p.pop\(\);

        } else 

            return false;

    }

    if \(p.size\(\) == 0\)

        return true;

    else 

        return false;

}

};