Valid Parentheses

The input string is considered as a balanced expression if

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

Note that an empty String is also considered valid.

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

Example 2:
Input: "()[]{}" → Output: true

Example 3:
Input: "({]" → Output: false

Example 4:
Input: "([)]" → Output: false

Example 5:
Input: "{[]}" → Output: true```

This solution is very useful for compilers to check if the parentheses are balanced or not. The expressions that we will deal with in this problem can consist of three different types of parenthesis:

• `()`,
• `{}` and
• `[]`

A `Stack` can be used to check whether the given expression has balanced parenthesis. The program will read one character at a time. If the character is an opening delimiter such as (, {, [ – then it is pushed into the `Stack`. When a closing delimiter is encountered like ), } or ] – then the stack is popped and compared against the opening delimiter. If they match then the parsing of the String continues. If they do not match, the program indicates that there is a mismatch of the delimiter. A linear-time algorithm based on the stack can be given as follows.

Algorithm:

• Create a `Stack`.
• Convert the input String into a `Character` array.
• While the end of the String is not reached, read one character at a time.
• If the character is an opening symbol `(, {, [ ` then push it into the `Stack`.
• If the character is a closing symbol `), }, ] ` then if the stack is empty then return `false`. Otherwise, pop the `Stack.`
• If the popped delimiter does not match with the corresponding character from the String then return `false`. If the current character in the loop is `'('` then the popped element must be `')'`.
• At the end of the loop if the `Stack` is still not empty then return `false`, which means there are unbalanced parentheses present in the String.

An interesting property about a valid parenthesis expression is that a sub-expression of a valid expression should also be a valid expression.

Following is the Java implementation of the algorithm:

```class Solution {
public boolean isValid(String s) {

if( s == null || s.isEmpty()){
return true;
}
Stack<Character> stack = new Stack<>();
int n = s.length();
int i = 0;
while( i < n){
char cur = s.charAt(i++);
if(cur == '(' || cur == '{' || cur == '['){
stack.push(cur);
}else{
// Closing parentheses found without
// a matching openning parentheses
//'')'' or ''}'' or '']'' found before a openning
if(stack.isEmpty()){
return false;
}

// Closing parentheses should also
// have a matching opening parentheses
if(cur == ')' && stack.peek() != '('){
return false;
}else if(cur == '}' && stack.peek() != '{'){
return false;
}else if(cur == ']' && stack.peek() != '['){
return false;
}

// openning and closing parentheses has matched
stack.pop();
}
}

// If there are unbalanced parentheses present in the String
if(!stack.isEmpty()){
return false;
}
return true;
}
}
```

Complexity analysis

• Time Complexity: `O(n)` because we simply traverse the given string one character at a time and push and pop operations on a stack take `O(1)` time.
• Space Complexity: `O(n)` as we push all opening brackets onto the stack and in the worst case, we will end up pushing all the brackets onto the stack. e.g. `{[{[(({{`.

Categories: Stack