Check if a given string has balanced Parenthesis

Balanced parentheses refer to the proper and consistent use of opening and closing parentheses, brackets, and curly braces in a piece of code or text. A set of parentheses, brackets, or curly braces is considered balanced if the opening and closing symbols match up correctly. For example, (), {}, and [] are all examples of balanced parentheses.

More complex expressions like ({}[]) and [{()}] are also balanced, as the opening and closing symbols are properly paired. On the other hand, expressions like (], {[}], [(]), and {(})are considered unbalanced, as the opening and closing symbols do not match up correctly. Maintaining balanced parentheses is important for ensuring the proper structure and readability of code and other written materials.

Here are some examples of balanced and unbalanced parentheses:

Balanced parentheses:

()
{}
[]
({}[])
[{()}]

Unbalanced parentheses:

(]
{[}]
[(])
{(})
(()

To check if a given string has balanced parentheses, we can use a stack data structure. The basic idea is to iterate through the string and push each opening bracket onto the stack. When we encounter a closing bracket, we check if the top of the stack contains the corresponding opening bracket. If it does, we pop the opening bracket from the stack. If it doesn’t, the parentheses are not balanced.

Below is how the algorithm looks like in different programming languages:


def is_balanced(word):
  # Initialize an empty stack
  stack = []
  
  # Iterate through each character in the input string
  for current_char in word:
    # If the character is an opening bracket, push it onto the stack
    if current_char in ['(', '{', '[']:
      stack.append(current_char)
    # If the character is a closing bracket
    else:
      # If the stack is empty, the string is not balanced
      if not stack:
        return False
      
      # Pop the top element from the stack
      last_char = stack.pop()
      
      # Check if the last character and the current character is correct pair
      if last_char == '(':
        if current_char != ')':
          return False
      if last_char == '{':
        if current_char != '}':
          return False
      if last_char == '[':
        if current_char != ']':
          return False
  
  # If the stack is not empty, the string is not balanced
  if stack:
    return False
  
  # If the stack is empty, all the characters are matched
  # So the string is balanced
  return True

print(is_balanced('()')) # True
print(is_balanced('{}[]')) # True
print(is_balanced('(]')) # False
print(is_balanced('{[}]')) # False


#include <iostream>
#include <stack>
#include <string>

bool is_balanced(std::string word) {
  // Initialize an empty stack
  std::stack<char> stack;

  // Iterate through each character in the input string
  for (char current_char: word) {
    // If the character is an opening bracket, push it onto the stack
    if (current_char == '(' || current_char == '{' || current_char == '[') {
      stack.push(current_char);
    }
    // If the character is a closing bracket
    else {
      // If the stack is empty, the string is not balanced
      if (stack.empty()) {
        return false;
      }

      // Pop the top element from the stack
      char last_char = stack.top();
      stack.pop();

      // Check if the last character and the current character is correct pair
      if (last_char == '(') {
        if (current_char != ')') {
          return false;
        }
      }
      if (last_char == '{') {
        if (current_char != '}') {
          return false;
        }
      }
      if (last_char == '[') {
        if (current_char != ']') {
          return false;
        }
      }
    }
  }

  // If the stack is not empty, the string is not balanced
  if (!stack.empty()) {
    return false;
  }

  // If the stack is empty, all the characters are matched
  // So the string is balanced
  return true;
}

int main() {
  std::cout << is_balanced("()") << std::endl; // True
  std::cout << is_balanced("{}[]") << std::endl; // True
  std::cout << is_balanced("(]") << std::endl; // False
  std::cout << is_balanced("{[}]") << std::endl; // False
  return 0;
}


// Function to check if a given string is balanced
function isBalanced(word) {
  // Initialize an empty stack
  let stack = [];

  // Iterate through each character in the input string
  for (let currentChar of word) {
    // If the character is an opening bracket, push it onto the stack
    if (['(', '{', '['].includes(currentChar)) {
      stack.push(currentChar);
    }
    // If the character is a closing bracket
    else {
      // If the stack is empty, the string is not balanced
      if (stack.length === 0) {
        return false;
      }

      // Pop the top element from the stack
      let lastChar = stack.pop();

      // Check if the last character and the current character is correct pair
      if (lastChar === '(') {
        if (currentChar !== ')') {
          return false;
        }
      }
      if (lastChar === '{') {
        if (currentChar !== '}') {
          return false;
        }
      }
      if (lastChar === '[') {
        if (currentChar !== ']') {
          return false;
        }
      }
    }
  }

  // If the stack is not empty, the string is not balanced
  if (stack.length !== 0) {
    return false;
  }

  // If the stack is empty, all the characters are matched
  // So the string is balanced
  return true;
}

console.log(isBalanced('()')); // true
console.log(isBalanced('{}[]')); // true
console.log(isBalanced('(]')); // false
console.log(isBalanced('{[}]')); // false


import java.util.Stack;

public class Main {
  // Function to check if a given string is balanced
  public static boolean isBalanced(String word) {
    // Initialize an empty stack
    Stack<Character> stack = new Stack<>();

    // Iterate through each character in the input string
    for (char currentChar : word.toCharArray()) {
      // If the character is an opening bracket, push it onto the stack
      if (currentChar == '(' || currentChar == '{' || currentChar == '[') {
        stack.push(currentChar);
      } 
      // If the character is a closing bracket
      else {
        // If the stack is empty, the string is not balanced
        if (stack.isEmpty()) {
          return false;
        }

        // Pop the top element from the stack
        char lastChar = stack.pop();

        // Check if the last character and the current character is correct pair
        if (lastChar == '(') {
          if (currentChar != ')') {
            return false;
          }
        } 
        if (lastChar == '{') {
          if (currentChar != '}') {
            return false;
          }
        } 
        if (lastChar == '[') {
          if (currentChar != ']') {
            return false;
          }
        }
      }
    }

    // If the stack is not empty, the string is not balanced
    return stack.isEmpty();
  }

  public static void main(String[] args) {
    System.out.println(isBalanced("()")); // True
    System.out.println(isBalanced("{[]}")); // True
    System.out.println(isBalanced("(]")); // False
    System.out.println(isBalanced("{[}]")); // False
  }
}

Here’s the breakdown of how the above code works:

The is_balanced function first initializes an empty stack. The stack will be used to keep track of the opening brackets encountered during the process which are not yet balanced by a matching closing bracket.
The function then iterates through each character in the input string word.
- If the current character is an opening bracket (, {, or [, it is pushed onto the stack.
- If the current character is a closing bracket, the function checks the following:
  - If the stack is empty, it means there is no corresponding opening bracket, so the string is not balanced, and the function returns False.
  - Otherwise, the function pops the top element from the stack (the last opening bracket encountered) and checks if it matches the current closing bracket. If the pair is not correct (e.g., ( with ), { with }, or [ with ]), the function returns False.
After iterating through all the characters in the input string, the function checks if the stack is empty or not.
- If the stack is not empty, it means there are unmatched opening brackets, so the string is not balanced, and the function returns False.
- If the stack is empty, it means all the opening brackets have been matched with their corresponding closing brackets, so the string is balanced, and the function returns True.