# Leetcode 20: Valid Parentheses solution

In this tutorial, we will help you to understand how to solve Valid Parentheses problem of leet code 20 problem.

This problem is also known as check for balanced brackets in an expression using stack.

Suppose, you are given a string `str` having just the characters ‘`(`‘,  ‘`)`‘,  ‘`{`‘,  ‘`}`‘,  ‘`[`‘ and / or ‘`]`‘. You will have to verify whether the input string is valid or not.

An input string will be 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```

## Algorithm to solve the problem:

• Create the stack
• Iterate over the string
• Check If character of string belongs to either `[` or `{` or `(` .
• If it belongs to then push this character to stack
• If it doesn’t belong to then :
• Get the top value of stack
• If character of string is `(` then popped value of stack must be `)`. If they are not matching then return the false value.
• If character of string is `[` then popped value of stack must be `]`. If they are not matching then return the false value.
• If character of string is `{` then popped value of stack must be `}`. If they are not matching then return the false value.
• Pop the element from the stack.
• If all the condition are met then return true value.

### Code with valid parentheses in string:

```#include <iostream>
#include <stack>

using namespace std;

bool isValid(string s) {
stack<char> st;

for(int i = 0; i < s.length(); i++) {

// Check if character belongs to "( or { or ["
if(s[i] == '(' || s[i] == '{' || s[i] == '[') {
st.push(s[i]);
} else if(s[i] == ')' || s[i] == '}' || s[i] == ']') {
// Check whether stack is empty or not
if(st.empty())
return false;

// Get the top value of stack
char ch = st.top();

// Match the popped value with iterated character of string
if(s[i] == ')' && ch != '(') {
return false;
} else if(s[i] == '}' && ch != '{') {
return false;
} else if(s[i] == ']' && ch != '[') {
return false;
}
// Pop the value from stack
st.pop();
}
}
// After iterating over the string, It will return true if stack is empty else false.
return st.empty();
}

int main()
{
string s = "[{()}]";

cout<<isValid(s);

return 0;
}```

Output:

`Output: true`

### Code with invalid parentheses in string:

```#include <iostream>
#include <stack>

using namespace std;

bool isValid(string s) {
stack<char> st;

for(int i = 0; i < s.length(); i++) {

// Check if character belongs to "( or { or ["
if(s[i] == '(' || s[i] == '{' || s[i] == '[') {
st.push(s[i]);
} else if(s[i] == ')' || s[i] == '}' || s[i] == ']') {
// Check whether stack is empty or not
if(st.empty())
return false;

// Get the top value of stack
char ch = st.top();

// Match the popped value with iterated character of string
if(s[i] == ')' && ch != '(') {
return false;
} else if(s[i] == '}' && ch != '{') {
return false;
} else if(s[i] == ']' && ch != '[') {
return false;
}
// Pop the value from stack
st.pop();
}
}
// After iterating over the string, It will return true if stack is empty else false.
return st.empty();
}

int main()
{
string s = "[{()]})";

cout<<isValid(s);

return 0;
}```

Output:

`Output: false`

*** there can be many ways to solve this problem but the best way of valid parentheses solution is to solve by using stack.