LeetCode Valid Parentheses: Stack

Overview

LeetCode Valid Parentheses: use a stack to match the open and close brackets, if we find unmatched parentheses or there are unmatched parentheses left, it fails

LeetCode Valid Parentheses

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 and Precautions: Stack

use a stack to match the open and close brackets. Whenever encountering an open bracket,  just push it into the stack, and when encountering a close bracket, just pop out the stack to check whether these two are matched or not. If when pop the stack, there is no elements in that stack, it fails (invalid), if then finish passing through the given string, there are still elements left in the stack, it fails (invalid).

The following code implements this idea and is accepted by LeetCode OJ to pass this Valid Parentheses problem:

class Solution {
    public:

        bool isValid(string s) {
            stack<char> stk;
            for (char c : s) {
                if ('(' == c || '[' == c || '{' == c)
                    stk.push(c);
                else if (')' == c)  {
                    if (stk.empty() || stk.top() != '(') 
                        return false ;
                    else  
                        stk.pop();
                }
                else if (']' == c) {
                    if (stk.empty() || stk.top() != '[')
                        return false ;
                    else
                        stk.pop();
                }
                else if ('}' == c) {
                    if (stk.empty() || stk.top() != '{') 
                        return false ;
                    else 
                        stk.pop();
                }
            }
            return stk.empty();
        }
};

Summary

LeetCode Valid Parentheses: use a stack to match the open and close brackets, if we find unmatched parentheses or there are unmatched parentheses left, it fails

Written on April 27, 2013