Balanced Expression with Replacement in Java
In Java, a balanced expression means the string which has its opening symbols (such as, parenthesis, bracket, or brace) closed in the right order with the same content. An instance of this sort can be that "((()))" and "{[()]}" are balanced expressions, whereas "(()" and "{[" are not. Mainly, this well-balanced expression checker with substitutions in Java is often based on the stack data structure, which is involved in safely tracking the opening symbols encountered in the expression, and in ensuring that each closing symbol matches the most recent opening symbol. If the operators pairing is not the same as given or there are dangling unclosed symbols at the end of the expression, the expression is considered to be unbalanced.
Example 1:
Input
S = "{(X[X])}
Output
Balanced
Explanation
The balanced expression after replacing X with suitable bracket is: {([[]])}.
Example 2:
Input
S = “[{X}(X)]”
Output
Not balanced
Explanation
No substitution of X with any bracket results in a balanced expression.
Approach 1: Recursive Bracket Matching Approach
The Recursive Bracket Matching approach leverages the principles of recursion and stack data structures to efficiently verify whether opening and closing brackets in an expression match in their correct order. Bracket matching is a critical task that ensures the syntactic correctness of expressions and plays a crucial role in parsing, syntax analysis, and language processing.
Algorithm
Step 1: Take input an expression: A string representing the expression to be checked for balance.
Step 2: Define Stack and Index Variables: Create an empty stack to track opening brackets encountered. Initialize an index variable to keep track of the current position while traversing the expression.
Step 3: If the index equals the length of the expression: If the stack is empty, return true (indicating the expression is balanced). Otherwise, return false (indicating the expression is unbalanced).
Step 4: Process Current Character: Retrieve the current character from the expression based on the index.
Step 5: Handle Opening Brackets: If the current character is an opening bracket ('{', '[', '('): Push it onto the stack. Recur by calling the isBalanced function with the updated index.
Step 6: If the current character is a closing bracket ('}', ']', ')'): If the stack is empty: Return false (indicating the expression is unbalanced since there's no matching opening bracket).
Step 7: Pop the top element from the stack. Check if the popped opening bracket matches the current closing bracket: If not, return false.
Step 8: Recur by calling the isBalanced function with the updated index. If the current character is 'X': Create a temporary stack and copy the elements from the original stack. Push 'X' onto the temporary stack.
Step 9: Recur by calling the isBalanced function with the temporary stack and the updated index.
Step 10: If the expression is balanced when considering 'X' as an opening bracket, return true. Otherwise, ignore 'X' and continue checking without it.
Step 11: Recur by calling the isBalanced function with the original stack and the index incremented by 1. Return the boolean value obtained from the recursive calls, indicating whether the expression is balanced or not.
Filename: RecursiveBracketMatching.java
import java.util.Stack; public class RecursiveBracketMatching { // Function to check if two brackets are matching or if 'X' acts as a placeholder static boolean isMatching(char opening, char closing) { return (opening == '{' && closing == '}') || (opening == '[' && closing == ']') || (opening == '(' && closing == ')') || (opening == 'X'); } // Recursive function to check if given expression is balanced static boolean isBalanced(String expression, Stackstack, int index) { // Base case: if the end of expression is reached if (index == expression.length()) { return stack.isEmpty(); // Check if stack is empty } char currentChar = expression.charAt(index); // Case 1: If current character is an opening bracket, push it onto the stack if (currentChar == '{' || currentChar == '[' || currentChar == '(') { stack.push(currentChar); } // Case 2: If current character is a closing bracket else if (currentChar == '}' || currentChar == ']' || currentChar == ')') { // If stack is empty, no matching opening bracket, expression is unbalanced if (stack.isEmpty()) { return false; } // Pop the top element from the stack char topElement = stack.pop(); // Check if the opening bracket matches the current closing bracket if (!isMatching(topElement, currentChar)) { return false; } } // Case 3: If current character is 'X', it can act as a placeholder else if (currentChar == 'X') { // Create a temporary stack with the current character pushed onto it Stack tempStack = new Stack<>(); tempStack.addAll(stack); tempStack.push(currentChar); // Check balance by including 'X' as an opening bracket if (isBalanced(expression, tempStack, index + 1)) { return true; // If balanced, return true } // If including 'X' as an opening bracket doesn't lead to balance, // ignore 'X' and continue checking without it } // Recur for the next character in the expression return isBalanced(expression, stack, index + 1); } // Main method to test the Recursive Bracket Matching approach public static void main(String[] args) { String expression = "{(X}[])"; Stack stack = new Stack<>(); // Check if the length of the expression is even before proceeding if (expression.length() % 2 == 0) { if (isBalanced(expression, stack, 0)) { System.out.println("Expression is balanced."); } else { System.out.println("Expression is not balanced."); } } else { System.out.println("Expression is not balanced."); } } }
Output:
Expression is not balanced.
Time Complexity
The time complexity of the Recursive Bracket Matching algorithm is O(n), where n is the length of the expression. It is because the algorithm processes each character of the expression exactly once, either pushing onto or popping from the stack, and performs a constant-time comparison for each character.
Space Complexity
The space complexity of the algorithm is also O(n), where n is the length of the expression. The space complexity arises due to the space required for the stack data structure used to store opening brackets encountered during the traversal of the expression and the stack's size can grow linearly with the length of the expression.
Approach 2: Iterative Stack Approach
The Iterative Stack Approach is similar to the Recursive Bracket Matching approach but implemented iteratively, making it suitable for scenarios where recursion is not preferred or feasible. The Iterative Stack Approach aims to determine whether an expression containing various types of brackets (such as parentheses, square brackets, and curly braces) is balanced or not.
Algorithm
Step 1: Take input an expression: A string representing the expression to be checked for balance.
Step 2: Initialization: Create an empty stack to track opening brackets encountered. Iterate through each character of the expression from left to right.
Step 3: For each character in the expression: If the character is an opening bracket ('{', '[', '('), push it onto the stack. If the character is a closing bracket ('}', ']', ')').
Step 4: If the stack is empty, return false (indicating an unbalanced expression since there is no matching opening bracket). Pop the top element from the stack and compare it with the current closing bracket.
Step 5: If they match according to the isMatching() function, continue to the next character. If they don't match, return false (indicating an unbalanced expression).
Step 6: If the character is 'X', continue to the next character without processing it further.
Step 7: After processing all characters: If the stack is empty, return true (indicating a balanced expression); otherwise, return false (indicating an unbalanced expression).
Filename: IterativeStackApproach.java
import java.util.Stack; public class IterativeStackApproach { static boolean isMatching(char opening, char closing) { return (opening == '{' && closing == '}') || (opening == '[' && closing == ']') || (opening == '(' && closing == ')') || (opening == 'X'); } static boolean isBalanced(String expression) { Stackstack = new Stack<>(); for (char ch : expression.toCharArray()) { if (ch == '{' || ch == '[' || ch == '(') { stack.push(ch); } else if (ch == '}' || ch == ']' || ch == ')') { if (stack.isEmpty()) { return false; // No matching opening bracket } char topElement = stack.pop(); if (!isMatching(topElement, ch)) { return false; // Mismatched brackets } } else if (ch == 'X') { // For 'X', ignore it and continue processing continue; } } return stack.isEmpty(); // Expression is balanced if stack is empty } public static void main(String[] args) { String expression = "{(X})[]"; if (isBalanced(expression)) { System.out.println("Expression is balanced."); } else { System.out.println("Expression is not balanced."); } } }
Output:
Expression is not balanced.
Time Complexity
The time complexity of the Iterative Stack Approach with 'X' Placeholder is O(n), where n is the length of the expression. It is because the algorithm iterates through each character of the expression exactly once to push onto or pop from the stack, resulting in a linear time complexity.
Space Complexity
The space complexity of the approach is O(n), where n is the length of the expression. It is due to the space required for the stack data structure, which can grow linearly with the length of the expression.
Approach 3: Counting Approach
The Counting Approach avoids the use of data structures like stacks or queues and instead relies solely on tracking the counts of opening and closing brackets. The Counting Approach aims to determine whether an expression containing various types of brackets is balanced or not by keeping track of the occurrences of opening and closing brackets. A balanced expression has matching opening and closing brackets in the correct order.
Algorithm
Step 1: Take input an expression: A string representing the expression to be checked for balance.
Step 2: Initialize counters for each type of bracket encountered in the expression. Initially, set all counters to zero. Iterate through each character of the expression from left to right.
Step 3: Counting Opening Brackets: For each character in the expression: If the character is an opening parenthesis '(': Increment the counter for open parentheses by 1.
Step 4: If the character is an opening square bracket '[': Increment the counter for open square brackets by 1. If the character is an opening curly brace '{': Increment the counter for open curly braces by 1.
Step 5: For each character in the expression: If the character is a closing parenthesis ')': Increment the counter for close parentheses by 1.
Step 6: If the character is a closing square bracket ']': Increment the counter for close square brackets by 1. If the character is a closing curly brace '}': Increment the counter for close curly braces by 1.
Step 7: Compare the counts of opening and closing brackets for each bracket type: Check if the count of open parentheses matches the count of close parentheses.
Step 8: Check if the count of open square brackets matches the count of close square brackets. Check if the count of open curly braces matches the count of close curly braces.
Step 9: If the counts match for all bracket types, set isBalanced to true (indicating a balanced expression); otherwise, set isBalanced to false (indicating an unbalanced expression).
Step 10: Return the boolean value isBalanced, indicating whether the expression is balanced or not.
Filename: CountingApproach.java
public class CountingApproach { static boolean isBalanced(String expression) { // Initialize counters for each type of bracket int openParenthesesCount = 0; int closeParenthesesCount = 0; int openBracketsCount = 0; int closeBracketsCount = 0; int openBracesCount = 0; int closeBracesCount = 0; // Iterate through each character of the expression for (char ch : expression.toCharArray()) { // Increment counters for opening brackets if (ch == '(') { openParenthesesCount++; } else if (ch == '[') { openBracketsCount++; } else if (ch == '{') { openBracesCount++; } // Decrement counters for closing brackets else if (ch == ')') { closeParenthesesCount++; } else if (ch == ']') { closeBracketsCount++; } else if (ch == '}') { closeBracesCount++; } } // Check if counts of opening and closing brackets match for each type boolean parenthesesMatch = openParenthesesCount == closeParenthesesCount; boolean bracketsMatch = openBracketsCount == closeBracketsCount; boolean bracesMatch = openBracesCount == closeBracesCount; // Expression is balanced if counts match for all bracket types return parenthesesMatch && bracketsMatch && bracesMatch; } public static void main(String[] args) { String expression = "{[()]}"; if (isBalanced(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 is O(n), where n is the length of the expression. It is because the algorithm iterates through each character of the expression exactly twice: once for counting opening brackets and once for counting closing brackets.
Space Complexity
The space complexity remains constant i.e, O(1) as the algorithm only requires space for a few integer counters to track bracket counts, regardless of the length of the expression.