Valid Parentheses

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.

My solution: make use of a stack


#include<iostream>
#include<string>
#include<stack>
#include<map>

using namespace std;
class Solution{
public:
    bool isValid(string s){
        map<char,char> par_map;
        par_map['(']=')';
        par_map['[']=']';
        par_map['{']='}';
        stack<char> mystack;
        

        if(s.size()==0){return true;}
        char c;
        for(int i=0;i<s.size();i++){  
            c=s[i];
            if (c=='(' || c=='[' || c== '{')
                mystack.push(c);
            if (c==')'|| c==']' || c== '}'){
                if(mystack.empty()) return false;
                else{
                if (par_map[mystack.top()]!=c)
                {return false;}
                else{
                    mystack.pop();
                }
                }
            }
        }
        
          return mystack.empty();
          return true;

}
};

int main()
{
   Solution sl;
   cout<<sl.isValid("([])(){[}")<<endl;
}

 

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s