问题描述

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.

解决方案

class Solution {
public:
    bool popAndTest( stack<char> &chStack, char ch ) {
        if( chStack.empty() ) {
            return false;
        }
        char top = chStack.top();
        chStack.pop();
        if( top != ch ) {
            return false;
        } else {
            return true;
        }
    }

    bool isValid(string s) {
        if( s.size() % 2 != 0 ) {
            return false;
        }
        
        stack<char> charStack;
        for( auto ch : s ) {
            if( ch == ')' ) {
                if( !popAndTest(charStack, '(') ) {
                    return false;
                }
            }
            else if( ch == ']' ) {
                if( !popAndTest(charStack, '[') ) {
                    return false;
                }
            }
            else if( ch == '}' ) {
                if( !popAndTest(charStack, '{') ) {
                    return false;
                }
            } else {
                charStack.push( ch );
            }
        }
        
        if( !charStack.empty() ) {
            return false;
        } else {
            return true;   
        }
    }
};

Valid Parentheses