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.

C++:
01 bool isValid(string s) {
02        stack <char> p;
03        int n=s.size();
04        for(int i=0;i<n;i++){
05            if((s[i]==‘(‘)||(s[i]==‘[‘)||(s[i]==‘{‘))
06                p.push(s[i]);
07            else{
08                if(p.empty())
09                    return false;
10                else{
11                        if((s[i]==‘)’)&&(p.top()==‘(‘))
12                            p.pop();
13                        else if((s[i]==‘]’)&&(p.top()==‘[‘))
14                            p.pop();
15                        else if((s[i]==‘}’)&&(p.top()==‘{‘))
16                            p.pop();
17                        else
18                            return false;
19                }
20            }
21        }
22        if(p.empty())
23            return true;
24        else
25            return false;
26 }
Advertisements
This entry was posted in Stack and Queue. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s