Balanced Parenthesis Checking using Stack

Balanced Parenthesis – What it is?

A string is said to have balanced parentheses when each opening parenthesis is followed by a comparable closing parenthesis that is placed in the appropriate location and vice versa. A string is said to have balanced parentheses if for every opening parenthesis, there is a corresponding closing parenthesis that appears later in the string, and for every closing parenthesis, there is a matching opening parenthesis that appears earlier in the string.

For instance, the following strings have parentheses that are evenly spaced:

  • “(((){[]}))”
  • “({})([])”
  • “(({})[]())”

On the other hand, the following strings do not have balanced parentheses:

  • “((( ))[ ]”
  • “(( ){ }”
  • “)({ })(“
Balanced Parenthesis
Balanced Parenthesis checking using Stack

Balanced Parenthesis – Why it is?

Balanced parentheses are essential in computer science because many programming languages employ parenthesis to signify function calls and control structures. A computer programme that contains parentheses that are not balanced might lead to syntax issues and might not be compiled or executed properly. As a result, it is essential to check that the ratio of open and closed parenthesis in a programme is appropriate in order to prevent problems.

Algorithm to Check Balanced Parenthesis

If you want to use a stack to determine whether or not a string of parentheses is balanced, you can do it by the following algorithm:

  1. To hold the opening parentheses, you should make a stack that is empty.
  2. Go through the string reading it from left to right.
  3. If the character that is now being displayed is an opening parenthesis (‘(‘, “, or ‘[‘), then you should put it onto the stack.
  4. If the currently shown character is a closing parenthesis (‘)’, “, or ‘]’), then the top element of the stack should be removed and checked to see if it is the same as the opening parenthesis that corresponds to it.
    1. The string is not balanced if the stack is empty or if the element that is popped does not match the closing parenthesis that is currently in use.
    2. If this is not the case, continue to scan the string.
  5. If the stack is empty after scanning the complete string, this indicates that the string is in a balanced state. If that is not the case, then it is not balanced.

Example:

String: ({}[()])

Stack:

Step 2: ‘(‘ is an opening parenthesis. Push it onto the stack.

Stack: (

Step 2: ‘{‘ is an opening parenthesis. Push it onto the stack.

Stack: ( {

Step 2: ‘}’ is a closing parenthesis. Pop ‘{‘ from the stack and check if it matches.

Stack: (

Step 2: ‘[‘ is an opening parenthesis. Push it onto the stack.

Stack: ( [

Step 2: ‘]’ is a closing parenthesis. Pop ‘[‘ from the stack and check if it matches.

Stack: (

Step 2: ‘(‘ is an opening parenthesis. Push it onto the stack.

Stack: ( (

Step 4: ‘)’ is a closing parenthesis. Pop ‘(‘ from the stack and check if it matches.

Stack: (

Step 5: End of string. The stack is not empty, so the string is not balanced.

In this example, the string is not balanced because the closing parenthesis ‘]’ does not match the opening parenthesis ‘(‘.

Note that this algorithm can be easily extended to handle other types of brackets, such as curly braces ‘{‘ and ‘}’, and square brackets ‘[‘ and ‘]’. Simply add the corresponding opening and closing brackets to the stack and check for matches accordingly.

Python Code

def is_balanced_parentheses(s):
    stack = []
    for c in s:
        if c in '({[':
            stack.append(c)
        elif c in ')}]':
            if not stack:
                return False
            elif c == ')' and stack[-1] == '(':
                stack.pop()
            elif c == '}' and stack[-1] == '{':
                stack.pop()
            elif c == ']' and stack[-1] == '[':
                stack.pop()
            else:
                return False
    return not stack


s = "([{}])"
print('{}  \t: {}'.format(s, is_balanced_parentheses(s)))

s = "([{])"
print('{}   \t: {}'.format(s, is_balanced_parentheses(s)))

s = "([]{})()"
print('{}  \t: {}'.format(s, is_balanced_parentheses(s)))

s = "([]{})()["
print('{} \t: {}'.format(s, is_balanced_parentheses(s)))

Output:

([{}])  	: True
([{])   	: False
([]{})()  	: True
([]{})()[ 	: False

In this implementation, we first create an empty stack.

We then iterate through the string s from left to right, and for each character, we check if it is an opening parenthesis or a closing parenthesis.

If the character is an opening parenthesis, we push it onto the stack.

If the character is a closing parenthesis, we check if the stack is empty. If it is, we return False because the closing parenthesis does not have a corresponding opening parenthesis. If it isn’t empty, we check the top of the stack to see if it contains the corresponding opening parenthesis. If it does, we pop the opening parenthesis from the stack. If it doesn’t, we return False because the closing parenthesis does not match the top of the stack.

After all characters have been processed, we check if the stack is empty. If it is, the string is balanced, so we return True. If it isn’t empty, the string is not balanced, so we return False.


YouTube Channel: CodeCrucks

Leave a Reply

Your email address will not be published. Required fields are marked *