> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/stack-and-queue/applications/valid-parentheses.md).

# 3.Valid Parentheses

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

An input string is valid if:

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

```
Example 1:
Input: "()[]{}"
Output: true

Example 2:
Input: "(]"
Output: false

Example 3:
Input: "([)]"
Output: false
```

**Solution:-**

```cpp
class Solution
{
public:
    bool isValid(string s)
    {

        if (s.length() == 0)
        {
            return true;
        }
        
        int x = 0;
        stack<int> k;
        bool res = true;
        for (int i = 0; i < s.length(); i++)
        {

            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            {
                k.push(s[i]);
            }
            else if(!k.empty())
            {
                if (s[i] == ')' && k.top() == '(')
                {
                    k.pop();
                }
                else if (s[i] == '}' && k.top() == '{')
                {
                    k.pop();
                }
                else if (s[i] == ']' && k.top() == '[')
                {
                    k.pop();
                }
                else
                {
                    x = 1;
                    res = false;
                    break;
                }
            }
            else{
                x = 1;
                res = false;
                break;
            }
        }

        if (x == 0 && !k.empty())
        {
            res = false;
        }

        return res;
    }
}
```