Valid Parentheses.txt

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
 

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false
Example 4:

Input: s = "([)]"
Output: false
Example 5:

Input: s = "{[]}"
Output: true
 

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.










#include <bits/stdc++.h>
using namespace std;

unordered_map<char,int> symbols = {{'[',-1},{'(',-2},{'{',-3},{']',1},{')',2},{'}',3}};
string isBalanced(string s)
{
    stack <char> st;
    for(char bracket : s)
    {
        if(symbols[bracket] < 0)
        {
            st.push(bracket);
        }

        else
        {
            if(st.empty())
                return "NO";

            char top = st.top();
            st.pop();

            if(symbols[top] + symbols[bracket] != 0 )
                return "NO";
        }
    }

    if(st.empty())
    {
       return "YES";  
    }
    else
    {
      return "NO";  
    }
}


int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        cout << isBalanced(s) << endl;
    }
}








/*
#include <bits/stdc++.h>
using namespace std;

bool isBalanced(string s)
{
    stack<char> st;
    char x;
    for (int i = 0; i < s.size(); i++)
    {
        if(s.empty())
        {
            return false;
        }

        if (s[i] == '(' || s[i] == '[' || s[i] == '{')
        {
            st.push(s[i]);
            continue;
        }

        switch (s[i])
        {
        case ')':
            x = st.top();
            st.pop();

            if (x == ']' || x == '}')
                return false;
            break;

        case ']':
            x = st.top();
            st.pop();

            if (x == ')' || x == '}')
                return false;
            break;

        case '}':
            x = st.top();
            st.pop();

            if (x == ')' || x == ']')
                return false;
            break;
        }
    }
    if (st.empty())
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    string s;
    cout << "Enter a string : ";
    cin >> s;
    cout << isBalanced(s);
}
*/