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

def parenthesis_checker(parenthesis_expression):
    stack = []

    parenthesis_pairs = { '(': ')',
                          '{': '}',
                          '[': ']' }

    # traversing the string expression
    for parenthesis in parenthesis_expression:

        if parenthesis in ["(", "{", "["]:
            # push the closing parenthesis in the stack
            stack.append(parenthesis_pairs[parenthesis])

        # If current character is not opening
        # parenthesis, then it is a closing one.
        # and the stack cannot be empty at this point.
        elif not stack:
            return False

        elif parenthesis != stack.pop():
            return False

    # see if stack has any values
    if stack:
        return False

    return True


if __name__ == "__main__":
    parenthesis_expression = "{[()]}"

    if parenthesis_checker(parenthesis_expression):
        print("expression is balanced")
    else:
        print("expression is not balanced")

C++

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

bool parenthesis_checker(string parenthesis_expression) {
    stack<char> stack1;
    for (int i = 0; i < parenthesis_expression.size(); i++) {
        if (
            parenthesis_expression[i] == '(' || 
            parenthesis_expression[i] == '{' || 
            parenthesis_expression[i] == '['
        ) {
            stack1.push(parenthesis_expression[i]);
        } else {
            if (!stack1.empty()) {
                char top = stack1.top();
                if (top == '(' && parenthesis_expression[i] == ')' || 
                    top == '{' && parenthesis_expression[i] == '}' || 
                    top == '[' && parenthesis_expression[i] == ']'
                ) {
                    stack1.pop();
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    }
    if (stack1.empty())
        return true;
    else
        return false;
}


int main() {

    string parenthesis_expression = "{[()]}";

    if(parenthesis_checker(parenthesis_expression))
        cout << "expression is balanced";
    else
        cout << "expression is not balanced";

    return 0;
}

Java

import java.util.*;
class Solution {
    public static boolean parenthesis_checker(String parenthesis_expression) {
        Stack<String> stack = new Stack<>();

        for (int i = 0; i < parenthesis_expression.length(); i++) {
            String parenthesis = String.valueOf(parenthesis_expression.charAt(i));
            if ("(".equals(parenthesis) || 
                "{".equals(parenthesis) || 
                "[".equals(parenthesis) ) {

                stack.push(parenthesis);
                continue;
            }

            if (stack.empty()) {
                return false;
            }

            if (")".equals(parenthesis)) {
                if ("(".equals(stack.pop())) {
                    continue;
                } else {
                    return false;
                }
            }

            if ("}".equals(parenthesis)) {
                if ("{".equals(stack.pop())) {
                    continue;
                } else {
                    return false;
                }
            }

            if ("]".equals(parenthesis)) {
                if ("[".equals(stack.pop())) {
                    continue;
                } else {
                    return false;
                }
            }
        }

        if (stack.empty()) {
            return true;
        } else {
            return false;
        }
    }
    public static void main(String[] args) {

        String parenthesis_expression = "{[()]}";

        if(parenthesis_checker(parenthesis_expression))
            System.out.println("expression is balanced");
        else
            System.out.println("expression is not balanced");
    }
}

Output

expression is balanced

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

def is_match(a, b):

    parenthesis_pairs = { '(': ')',
                          '{': '}',
                          '[': ']' }
    try:
        if parenthesis_pairs[a] == b:
            return True
    except:
        pass
    return False


def parenthesis_checker(parenthesis_expression):

    parenthesis_expression = list(parenthesis_expression)

    top = -1

    for i in range(len(parenthesis_expression)):

        if top < 0 or not is_match(parenthesis_expression[top], parenthesis_expression[i]):
            top += 1
            parenthesis_expression[top] = parenthesis_expression[i]
        else:
            top -= 1

    return top == -1


parenthesis_expression = "{[()]}"

if parenthesis_checker(parenthesis_expression):
    print("expression is balanced")
else:
    print("expression is not balanced")

C++

#include <iostream>
using namespace std;
bool is_match(char a, char b) {
    if (a == '(' && b == ')')
        return true;
    if (a == '[' && b == ']')
        return true;
    if (a == '{' && b == '}')
        return true;
    return false;
}

bool parenthesis_checker(string parenthesis_expression) {
    int top = -1;
    for (int i = 0; i < parenthesis_expression.length(); i++) {
        if (top < 0 || !is_match(parenthesis_expression[top], parenthesis_expression[i])) {
            ++top;
            parenthesis_expression[top] = parenthesis_expression[i];
        }
        else
            --top;
    }
    return top == -1;
}

int main() {

    string parenthesis_expression = "{[()]}";

    if(parenthesis_checker(parenthesis_expression))
        cout << "expression is balanced";
    else
        cout << "expression is not balanced";

    return 0;
}

Java

class Main{

    static boolean is_match(char a, char b) {
        if (a == '(' && b == ')')
            return true;
        if (a == '[' && b == ']')
            return true;
        if (a == '{' && b == '}')
            return true;
        return false;
    }

    static boolean parenthesis_checker(String string_expression) {
        int top = -1;

        char parenthesis_expression[] = new char[string_expression.length()];

        for (int i = 0; i < string_expression.length(); i++) {
            parenthesis_expression[i] = string_expression.charAt(i);
        }

        for (int i = 0; i < string_expression.length(); i++) {
            if (top < 0 || !is_match(parenthesis_expression[top], parenthesis_expression[i])) {
                top++;
                parenthesis_expression[top] = parenthesis_expression[i];
            } else {
                top--;
            }
        }

        return top == -1;
    }

    public static void main(String[] args) {

        String parenthesis_expression = "{[()]}";

        if (parenthesis_checker(parenthesis_expression))
            System.out.println("expression is balanced");
        else
            System.out.println("expression is not balanced");
    }
}

Output

expression is balanced

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.

Conclusion

In this article we have understood:

• A Parenthesis checker is a parenthesis balance checking algorithm.
• The use cases of input and output examples for parenthesis checker.
• Two approaches for implementing parenthesis checker: Stack-based approach and Pointer-based approach.
• Wrote code implementation using C++, Python, and Java for both approaches.
• In stack based approach the time complexity is $O(n)$ and the space complexity is $O(n)$ since we create a stack.
• In the pointer-based approach, the time complexity is $O(n)$ and the space complexity is $O(1)$ since only one single pointer is used.