Parenthesis Checker

Given an expression containing various types of brackets (parentheses) such as (), {}, and [], write a program to check whether the given expression has balanced parentheses. The parentheses are considered balanced if each opening bracket has a corresponding closing bracket and they are properly nested.

Input/Output Examples

plaintext
Example 1:
Input: "{[()]}"
Output: True
Explanation: The expression has balanced parentheses because each opening bracket has a corresponding closing bracket in the correct order.

Example 2:
Input: "({[}])"
Output: False
Explanation: The expression has unbalanced parentheses because the closing bracket } does not correspond to the last opened bracket [, making the expression invalid.

Approach for Parenthesis Checker

  1. Stack Data Structure:
    • The problem can be efficiently solved using a stack.
    • We push the opening brackets into the stack and for every closing bracket, check if it matches the top of the stack.
    • If it matches, pop the top element. If it doesn't match or the stack is empty when a closing bracket is encountered, the parentheses are unbalanced.
  2. Algorithm:
    • Traverse the expression character by character.
    • If an opening bracket is encountered ((, {, [), push it onto the stack.
    • If a closing bracket is encountered (), }, ]), check if the stack is non-empty and the top of the stack is the corresponding opening bracket.
    • If the stack is empty after processing the entire expression, the parentheses are balanced.
  3. Edge Cases:
    • If the expression contains only closing brackets without any opening brackets, it is unbalanced.
    • If there are extra opening brackets that are not closed by the end, the expression is unbalanced.

C++ Program to implement Parenthesis Checker

cpp
#include <iostream>
#include <stack>
using namespace std;

// Function to check if the given expression has balanced parentheses
bool areParenthesesBalanced(string expr) {
    stack<char> s;
    
    // Traverse the given expression
    for (char ch : expr) {
        // If the current character is an opening bracket, push it onto the stack
        if (ch == '(' || ch == '{' || ch == '[') {
            s.push(ch);
        }
        // If the current character is a closing bracket, check for a match
        else if (ch == ')' || ch == '}' || ch == ']') {
            if (s.empty()) return false; // Stack is empty, no matching opening bracket
            char top = s.top();
            s.pop();
            if ((ch == ')' && top != '(') ||
                (ch == '}' && top != '{') ||
                (ch == ']' && top != '[')) {
                return false; // Mismatched brackets
            }
        }
    }
    
    // If the stack is empty, parentheses are balanced
    return s.empty();
}

int main() {
    string expr = "{[()]}";
    if (areParenthesesBalanced(expr)) {
        cout << "The expression has balanced parentheses." << endl;
    } else {
        cout << "The expression does not have balanced parentheses." << endl;
    }
    return 0;
}

Java Program to implement Parenthesis Checker

java
import java.util.Stack;

public class ParenthesisChecker {

    // Function to check if the given expression has balanced parentheses
    public static boolean areParenthesesBalanced(String expr) {
        Stack<Character> stack = new Stack<>();
        
        // Traverse the given expression
        for (char ch : expr.toCharArray()) {
            // If the current character is an opening bracket, push it onto the stack
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            }
            // If the current character is a closing bracket, check for a match
            else if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) return false; // No matching opening bracket
                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == '}' && top != '{') ||
                    (ch == ']' && top != '[')) {
                    return false; // Mismatched brackets
                }
            }
        }
        
        // If the stack is empty, parentheses are balanced
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String expr = "{[()]}";
        if (areParenthesesBalanced(expr)) {
            System.out.println("The expression has balanced parentheses.");
        } else {
            System.out.println("The expression does not have balanced parentheses.");
        }
    }
}

Python Program to implement Parenthesis Checker

python
# Function to check if the given expression has balanced parentheses
def are_parentheses_balanced(expr):
    stack = []
    
    # Dictionary to map closing brackets to corresponding opening brackets
    matching_brackets = {')': '(', '}': '{', ']': '['}
    
    # Traverse the given expression
    for char in expr:
        # If the current character is an opening bracket, push it onto the stack
        if char in "({[":
            stack.append(char)
        # If the current character is a closing bracket, check for a match
        elif char in ")}]":
            if not stack or stack.pop() != matching_brackets[char]:
                return False
    
    # If the stack is empty, parentheses are balanced
    return len(stack) == 0

# Example usage
if __name__ == "__main__":
    expr = "{[()]}"
    if are_parentheses_balanced(expr):
        print("The expression has balanced parentheses.")
    else:
        print("The expression does not have balanced parentheses.")

Time Complexity:

  • O(n): The expression is traversed only once, where n is the length of the expression.

Space Complexity:

  • O(n): In the worst case, all opening brackets are pushed onto the stack, which takes space proportional to the length of the input expression.

DSA

7882

545

Related Articles