Valid Expression

In programming and mathematics, expressions often contain various types of brackets, such as parentheses (), curly braces {}, and square brackets []. Ensuring these brackets are balanced is crucial for code syntax and equation validity.

In this post, we’ll explore a simple yet effective way to check if a given expression has balanced brackets using Java.

Problem Statement

Given an expression as a string, verify if it contains balanced parentheses, curly braces, and square brackets.

For instance:

• Input: "(a + b)" Output: True
• Input: "{a + [b - c]}" Output: True
• Input: "{a + [b - c)}" Output: False

Solution Approach

The most efficient way to approach this problem is by using a stack, a Last-In-First-Out (LIFO) data structure.

1. Iterate through each character in the expression.
2. When an opening bracket ((, {, or [) is encountered, push it onto the stack.
3. When a closing bracket (), }, or ]) is encountered:
   • If the stack is empty, return False.
   • Else, pop the topmost element from the stack and check if it matches the corresponding opening bracket. If not, return False.
4. After processing all characters, if the stack is not empty, return False. Otherwise, return True.

Java Code

import java.util.Stack;

public class BalancedBrackets {

    public static boolean areBracketsBalanced(String expr) {
        Stack<Character> stack = new Stack<>();

        for (char ch : expr.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) return false;
                char openBracket = stack.pop();
                if (!isMatchingPair(openBracket, ch)) return false;
            }
        }

        return stack.isEmpty();
    }

    private static boolean isMatchingPair(char openBracket, char closeBracket) {
        return (openBracket == '(' && closeBracket == ')') ||
               (openBracket == '{' && closeBracket == '}') ||
               (openBracket == '[' && closeBracket == ']');
    }

    public static void main(String[] args) {
        String expr1 = "{a + [b - c]}";
        System.out.println(areBracketsBalanced(expr1));  // Output: True

        String expr2 = "{a + [b - c)}";
        System.out.println(areBracketsBalanced(expr2));  // Output: False
    }
}

Note

This solution will work accurately even if the input string consists exclusively of parentheses (), curly braces {}, and square brackets [], without any other characters. e.g. (()[{}])

Summary

The stack-based approach is intuitive and efficient for checking balanced brackets. In this implementation, the time complexity is O(n), where n is the length of the expression.