Duplicate Parenthesis Problem in Java
The Duplicate Parenthesis Problem is a computational problem that emerges while parsing and analyzing mathematical equations, particularly ones including parentheses. The task is to determine whether an expression contains duplicate pairs of parentheses. Duplicate parentheses are cases in which there are unneeded or redundant pairs of opening and closing parenthesis that do not influence the expression's evaluation but may confuse or complicate the parsing procedure. Parentheses are commonly used in expressions involving arithmetic, functions, or logical operations to specify operation in order to group subexpressions.
Example 1:
Input
((x+y))+z
Output
True
Explanation
Duplicate () found in subexpression ((x+y))
Example 2:
Input
A/(B+C)*D
Output
False
Explanation
No duplicate parenthesis found.
Approach 1: Using a Stack
The approach of using a stack to solve the Duplicate Parenthesis Problem is a common and efficient technique employed in computer science and programming. This method leverages the stack data structure to keep track of opening parentheses encountered while traversing through the expression. As the traversal progresses, each closing parenthesis encountered is checked against the stack to ensure that it matches the most recent opening parenthesis.
Algorithm
Step 1: Take input as a string expression representing a mathematical expression. Initialize Stack: Create an empty stack stack to store opening parentheses encountered during the traversal of the expression.
Step 2: Traverse Expression Characters: Iterate through each character c in the expression from left to right.
Step 3: Process Each Character: If c is an opening parenthesis ('('), push it onto the stack.
Step 4: If c is a closing parenthesis (')'): If the stack is empty or the top of the stack is not an opening parenthesis, return true indicating duplicate parentheses. Otherwise, pop the top element from the stack.
Step 5: Check for Remaining Unmatched Parentheses: After processing the entire expression, if the stack is not empty, return true indicating duplicate parentheses.
Step 6: If no duplicate parentheses are found during the traversal and the stack is empty, return false, indicating that the expression does not contain duplicate parentheses.
Filename: DuplicateParenthesisChecker.java
import java.util.*;
public class DuplicateParenthesisChecker {
public static boolean hasDuplicateParentheses(String expression) {
Stack<Character> stack = new Stack<>();
// Iterate through each character in the expression
for (char c : expression.toCharArray()) {
// If the character is an opening parenthesis, push it onto the stack
if (c == '(') {
stack.push(c);
}
// If the character is a closing parenthesis
else if (c == ')') {
// If the stack is empty or the top of the stack is not an opening parenthesis, return true
if (stack.isEmpty() || stack.peek() != '(') {
return true; // Duplicate parenthesis found
}
// Otherwise, pop the top element from the stack
stack.pop();
}
}
// If there are remaining elements in the stack, it means there are unmatched opening parentheses
return !stack.isEmpty();
}
public static void main(String[] args) {
String expression1 = "(a + (b * c)))";
String expression2 = "((a + b) + ((c + d)))";
String expression3 = "((a + b) + c)";
System.out.println("Expression 1 has duplicate parentheses: " + hasDuplicateParentheses(expression1));
System.out.println("Expression 2 has duplicate parentheses: " + hasDuplicateParentheses(expression2));
System.out.println("Expression 3 has duplicate parentheses: " + hasDuplicateParentheses(expression3));
}
}
Output:
Expression 1 has duplicate parentheses: true
Expression 2 has duplicate parentheses: false
Expression 3 has duplicate parentheses: false
Time Complexity
The time complexity of the solution is O(n), where n is the length of the input expression. This is because the solution traverses through each character in the expression exactly once. All operations within the loop, such as pushing and popping elements from the stack, checking if the stack is empty, and accessing the top element of the stack, are constant-time operations.
Space Complexity
The space complexity of the algorithm is also O(n), where n is the length of the input expression. In the worst-case scenario, if all opening parentheses in the expression are unmatched, the stack could contain up to n/2 elements (where n is the length of the expression), resulting in O(n) space complexity.
Approach 2: Counting Approach
The Counting Approach is a simple yet effective method for detecting duplicate parentheses in an expression. Instead of using additional data structures like stacks or hash maps, this approach relies on counting the number of consecutive opening or closing parentheses encountered while traversing the expression. By comparing these counts, the presence of duplicate parentheses can be determined.
Algorithm
Step 1: Initialize two integer variables openCount and closeCount to zero. These variables will keep track of the count of consecutive opening and closing parentheses encountered, respectively.
Step 2: Iterate through each character c in the expression string expression: If c is an opening parenthesis ('('): Increment the openCount variable by 1 to indicate the presence of a consecutive opening parenthesis.
Step 3: If c is a closing parenthesis (')'): Increment the closeCount variable by 1 to indicate the presence of a consecutive closing parenthesis.
Step 4: During each iteration, check if either openCount or closeCount exceeds 1, indicating consecutive parentheses: If either openCount or closeCount is greater than 1: Return true, indicating that duplicate parentheses are present in the expression.
Step 5: If a non-parenthesis character is encountered during the iteration: Reset both openCount and closeCount to zero.
Step 6: After processing the entire expression: If no duplicate parentheses are detected during traversal: Return false, indicating that the expression does not contain duplicate parentheses.
Filename: DuplicateParenthesisCheckerCP.java
public class DuplicateParenthesisCheckerCP {
public static boolean hasDuplicateParentheses(String expression) {
int openCount = 0; // Count of consecutive opening parentheses
int closeCount = 0; // Count of consecutive closing parentheses
// Iterate through each character in the expression
for (char c : expression.toCharArray()) {
if (c == '(') {
// Increment the count of consecutive opening parentheses
openCount++;
} else if (c == ')') {
// Increment the count of consecutive closing parentheses
closeCount++;
}
// Check for duplicate parentheses
if (openCount > 1 || closeCount > 1) {
return true; // Duplicate parentheses found
}
// Reset counts if characters other than parentheses are encountered
if (c != '(' && c != ')') {
openCount = 0;
closeCount = 0;
}
}
// If no duplicate parentheses found after processing the entire expression
return false;
}
public static void main(String[] args) {
String expression1 = "(a + (b * c))";
String expression2 = "(a + b) + (c + d)";
String expression3 = "((a + b) + c)";
System.out.println("Expression 1 has duplicate parentheses: " + hasDuplicateParentheses(expression1));
System.out.println("Expression 2 has duplicate parentheses: " + hasDuplicateParentheses(expression2));
System.out.println("Expression 3 has duplicate parentheses: " + hasDuplicateParentheses(expression3));
}
}
Output:
Expression 1 has duplicate parentheses: true
Expression 2 has duplicate parentheses: false
Expression 3 has duplicate parentheses: true
Time Complexity
The time complexity of the algorithm is O(n), where n is the length of the input expression. It is because the algorithm iterates through each character in the expression exactly once, performing constant-time operations such as character comparisons and incrementing counts.
Space Complexity
The space complexity of the algorithm is O(1). This is because the algorithm uses only a constant amount of extra space, primarily to store the counts of consecutive opening and closing parentheses (openCount and closeCount variables). Regardless of the size of the input expression, the amount of additional memory used remains constant.
Approach 3: Using a HashMap
The approach of using a hash map to solve the Duplicate Parenthesis Problem offers a more generalized solution that can detect not only duplicate parentheses but also other types of imbalanced parentheses. In this approach, a hash map is utilized to store the count of opening and closing parentheses encountered while traversing the expression. By maintaining separate counts for opening and closing parentheses, duplicate parentheses can be identified if the counts exceed certain thresholds.
Algorithm
Step 1: Create a hash map to store the counts of opening and closing parentheses encountered. The keys of the hash map represent the types of parentheses ('(' for opening and ')' for closing), and the corresponding values represent their counts.
Step 2: Traverse the Expression: Iterate through each character in the expression from left to right. For each character encountered: If the character is an opening parenthesis ('('), increment the count of opening parentheses in the hash map.
Step 3: If the character is a closing parenthesis (')'), increment the count of closing parentheses in the hash map.
Step 4: Check for Duplicate Parentheses: After processing the entire expression, compare the counts of opening and closing parentheses stored in the hash map.
Step 5: If the counts are unequal, or if either count exceeds 1 (indicating multiple occurrences of the corresponding parentheses), duplicate parentheses are present.
Step 6: Based on the comparison result, return true if duplicate parentheses are detected, and false otherwise.
Filename: DuplicateParenthesisCheckerHM.java
import java.util.HashMap;
public class DuplicateParenthesisCheckerHM {
public static boolean hasDuplicateParentheses(String expression) {
// Create a hash map to store the counts of opening and closing parentheses
HashMap<Character, Integer> parenCounts = new HashMap<>();
// Iterate through each character in the expression
for (char c : expression.toCharArray()) {
if (c == '(' || c == ')') {
// Increment the count of the corresponding parentheses in the hash map
parenCounts.put(c, parenCounts.getOrDefault(c, 0) + 1);
}
}
// Check for duplicate parentheses
int openCount = parenCounts.getOrDefault('(', 0);
int closeCount = parenCounts.getOrDefault(')', 0);
return openCount > 1 || closeCount > 1;
}
public static void main(String[] args) {
String expression1 = "(a + (b * c))";
String expression2 = "((a + b) + ((c + d)))";
String expression3 = "(a + b) + c";
System.out.println("Expression 1 has duplicate parentheses: " + hasDuplicateParentheses(expression1));
System.out.println("Expression 2 has duplicate parentheses: " + hasDuplicateParentheses(expression2));
System.out.println("Expression 3 has duplicate parentheses: " + hasDuplicateParentheses(expression3));
}
}
Output:
Expression 1 has duplicate parentheses: true
Expression 2 has duplicate parentheses: true
Expression 3 has duplicate parentheses: false
Time Complexity
The time complexity of the algorithm is O(n), where n is the length of the input expression. This is because the algorithm iterates through each character in the expression exactly once, performing constant-time operations such as updating counts in the hash map.
Space Complexity
The space complexity of the algorithm is O(1) for a fixed set of parentheses. Although a hash map is used to store the counts of opening and closing parentheses, the size of the hash map is constant and independent of the size of the input expression.
Approach 4: Using Two Stacks
The approach of using two stacks to solve the Duplicate Parenthesis Problem provides an efficient and straightforward solution by keeping track of both opening parentheses and their corresponding indices. By maintaining two separate stacks—one for opening parentheses and another for their indices—this approach ensures that each closing parenthesis is matched with the correct opening parenthesis.
Algorithm
Step 1: Create two stacks: one to store opening parentheses (openStack) and another to store their corresponding indices (indexStack).
Step 2: Iterate through each character in the expression from left to right. For each character encountered: If the character is an opening parenthesis ('('), push it onto the openStack and push its index onto the indexStack.
Step 3: If the character is a closing parenthesis (')'): Pop the top element from both stacks (openStack and indexStack). If the popped element from openStack is not an opening parenthesis, it indicates a mismatch, and thus, a duplicate parenthesis.
Step 4: If the popped element from indexStack does not match the current index, it also indicates a mismatch. If both stacks are empty after popping, it indicates an unmatched closing parenthesis.
Step 5: Check for Duplicate Parentheses: If a mismatch occurs during processing or if both stacks are not empty after traversing the entire expression, duplicate parentheses are present.
Step 6: Based on the processing results, return true if duplicate parentheses are detected, and false otherwise.
Filename: DuplicateParenthesisCheckerTS.java
import java.util.Stack;
public class DuplicateParenthesisCheckerTS {
public static boolean hasDuplicateParentheses(String expression) {
Stack<Character> openStack = new Stack<>(); // Stack to store opening parentheses
Stack<Integer> indexStack = new Stack<>(); // Stack to store indices of opening parentheses
// Traverse the expression
for (int i = 0; i < expression.length(); i++) {
char currentChar = expression.charAt(i);
// If the current character is an opening parenthesis
if (currentChar == '(') {
openStack.push('('); // Push '(' onto openStack
indexStack.push(i); // Push its index onto indexStack
}
// If the current character is a closing parenthesis
else if (currentChar == ')') {
// If both stacks are not empty
if (!openStack.isEmpty() && !indexStack.isEmpty()) {
// Pop the top elements from both stacks
char topOpen = openStack.pop();
int topIndex = indexStack.pop();
// Check for matching parentheses
if (topOpen != '(' || topIndex != i) {
return true; // Duplicate parentheses found
}
} else {
return true; // Unmatched closing parenthesis found
}
}
}
// If both stacks are empty after processing the entire expression
return openStack.isEmpty() && indexStack.isEmpty();
}
public static void main(String[] args) {
String expression1 = "(a + (b * c))";
String expression2 = "((a + b) + ((c + d)))";
String expression3 = "((a + b) + c)";
System.out.println("Expression 1 has duplicate parentheses: " + hasDuplicateParentheses(expression1));
System.out.println("Expression 2 has duplicate parentheses: " + hasDuplicateParentheses(expression2));
System.out.println("Expression 3 has duplicate parentheses: " + hasDuplicateParentheses(expression3));
}
}
Output:
Expression 1 has duplicate parentheses: true
Expression 2 has duplicate parentheses: true
Expression 3 has duplicate parentheses: true
Time Complexity
The time complexity of the algorithm is O(n), where n is the length of the input expression. This is because the algorithm iterates through each character in the expression exactly once, performing constant-time operations such as stack push, pop, and comparisons.
Space Complexity
The space complexity of the algorithm is O(n), where n is the length of the input expression. This is because the algorithm utilizes two stacks (openStack and indexStack) to store opening parentheses and their corresponding indices, respectively.