Parenthesis Checker

Problem Statement

A string expression of parenthesis with the letters "(", ")", "{", "}", "[", "]" is supplied to you.

The expression is called balanced with respect to the parenthesis if the same type of closing brackets )", "}", "]" is used to close open brackets "(", "{", "[".

The correct sequence in which they appear must be followed when closing open brackets. Verify whether or not the supplied statement is balanced.

Example

Consider the expression string {[()]} here as we can see there are three nested parenthesis and each opening parenthesis has a corresponding closing parenthesis. Hence the output from our parenthesis checker must be giving a valid parenthesis expression.

Consider another expression string {{{[(() here as we can see there are multiple opening parenthesis but only one parenthesis has a corresponding closing parenthesis. Hence the output from our parenthesis checker should say an invalid parenthesis expression.

Example Explanation

Let us consider the case of input expression string {[()]}. The expression contains six characters: {, [, (, ), ], }.

Traversing the string from the first character we see that for the first character { the corresponding closing parenthesis is on the sixth character }, for the second character [ the corresponding closing parenthesis is on the fifth character ], and for the third character ( the corresponding closing parenthesis is on the fourth character ).

Thus we observe that for each opening parenthesis there is a corresponding closing parenthesis present, moreover, the closing parentheses are in the exact same sequence as that of the opening parenthesis. Thus the string satisfies the requirements of a valid parenthesis expression.

If the given string had more characters like the sequence of ({[ opening parenthesis without any closing parenthesis then the expression would have been termed as *not valid parenthesis expression.

Input/Output

Sample A

Input string: "{}[](){}{([{()}])}"

Output: expression is balanced

Sample B

Input string: "{}[]("

Output: expression is not balanced

Constraints

The constraints can be put on the input expression, those being:

1. The input must be a string only.
2. The input expression must consist of parenthesis only ()[]{}.
3. The input expression cannot be an empty string (as that is always a valid parenthesis expression).
4. The input string should be of limited ($10^4$ characters max) length.

Algorithm 1 - Using Stack

In this approach, the parenthesis checker is implemented using a stack data structure.

Algorithm

The algorithm has the following steps:

1. We traverse the string starting from the first character to the last sequentially. For each character:
   1. Any open symbol, such as (,{ or[ that is encountered, is placed onto the stack
   2. Any one of the below cases is executed if an end symbol (i.e.,),},]) is encountered.
      1. If the close symbol that was encountered while traversing matches its corresponding open symbol, the open symbol that is at the Top Of the Stack (TOS) is popped out. (OR)
      2. The TOS (Top Of Stack) is verified, and if the close symbol encountered does not match the open symbol, False is returned since no matching symbol was found. Thus, the string is not a valid parenthesis expression. (OR)
      3. If the stack is empty, the TOS (Top Of Stack) is checked, and if it is, False is returned since there isn't an open symbol in the stack. Thus the string is not a valid parenthesis expression.
2. If the string traversal is complete.
   1. If the stack is empty, it means the string is a valid parenthesis expression, and True is returned.
   2. If the stack is not empty, it means some open parentheses are not closed. Hence the string is not a valid parenthesis expression and False is returned.

Code Implementation

Python

C++

Java

Output

Time Complexity

The time complexity of the parenthesis checker implementation using stack is O(n) where n is the length of the input expression, as we are traversing the string character by character using for loop.

Space Complexity

The space complexity of the parenthesis checker implementation using stack is O(n) where n is the length of the input expression, as we are storing the opening parenthesis characters in a stack.

Algorithm 2 - Pointer Based Approach

In this approach, the parenthesis checker is implemented using a pointer to last unmatched open parenthesis.

Algorithm

The algorithm has the following steps:

1. Set pointer top to -1 at initialization.
2. Traverse through the input string expression character by character.
   1. Increase top by one, if top < 0 or the current character does not match the open bracket at the top index (as the current character is the most recently occurred open bracket).
   2. Else, decrement the top pointer by one, if the current character matches the open bracket at the top index ( now it is pointing to the open bracket that is not matched yet).
3. If the top pointer falls to -1 after iterating all characters, then all open brackets are matched with their corresponding closing bracket in the correct sequence ( i.e., the string is a valid parenthesis expression)

Code Implementation

Python

C++

Java

Output

Time Complexity

The time complexity of the parenthesis checker implementation using stack is $O(n)$ where n is the length of the input expression, as we are traversing the string character by character using for loop.

Space Complexity

The space complexity of the parenthesis checker implementation using stack is $O(1)$, as we are using only one integer pointer.