CC-14 : Check if parentheses pairs are duplicate.

Description:

Given a String expression containing only parentheses, check if duplicate pairs (un-necessary pairs) of brackets are present.

Test cases and expected outputs:

Input Parameters	Expected outputs
Expression: ((x+y))+z	Are parentheses duplicate: true
Expression: (x+y)	Are parentheses duplicate: false
Expression: ((x+y)+((z)))	Are parentheses duplicate: true

Pseudocode:

Initialize a Deque based stack for processing purposes.

If input String length is less than 3, return false, as duplicate pairs of parentheses are not possible.

For each character in input String:

If current character is not ‘)‘, add it to the stack.

Else if top element of stack is ‘(‘, return true.

Else while top character of stack is not ‘(‘, remove it from the stack.

Pop top element of the stack.

Return false from the program.

Code:

public boolean duplicateChecker(String str) throws Exception{
	Deque<Character> stack=new LinkedList<Character>();	
	if (str.length()<=3) { return false;}
	char[] chr=str.toCharArray();
	char c;
	for (int idx=0;idx < chr.length; idx++) {
		c=chr[idx];
		if (c != ')') {
			stack.offerFirst(c);
		} else {
			if (stack.peekFirst()=='(') {
				return true;
			}
			while (stack.peekFirst()!='(') {
				stack.pollFirst();
			}
		stack.pollFirst();
		}
	}
	return false;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Deque;
import java.util.LinkedList;

public class StackParenthesesDuplicateChecker {	

public boolean duplicateChecker(String str) throws Exception{
	Deque<Character> stack=new LinkedList<Character>();	
	if (str.length()<=3) { return false;}
	char[] chr=str.toCharArray();
	char c;
	for (int idx=0;idx < chr.length; idx++) {
		c=chr[idx];
		if (c != ')') {
			stack.offerFirst(c);
		} else {
			if (stack.peekFirst()=='(') {
				return true;
			}
			while (stack.peekFirst()!='(') {
				stack.pollFirst();
			}
		stack.pollFirst();
		}
	}
	return false;
}
 	
public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	try {
	StackParenthesesDuplicateChecker checker=new StackParenthesesDuplicateChecker();
	boolean retVal;
	System.out.println("\n\nExpression: ((x+y))+z");
	retVal=checker.duplicateChecker("((x+y))+z");
	System.out.print("Are parantheses duplicate: "+ retVal);
	
	System.out.println("\n\nExpression: (x+y)");
	retVal=checker.duplicateChecker("(x+y)");
	System.out.print("Are parantheses duplicate: "+ retVal);
	
	System.out.println("\n\nExpression: ((x+y)+((z)))");
	retVal=checker.duplicateChecker("((x+y)+((z)))");
	System.out.print("Are parantheses duplicate: "+ retVal);
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}
	
}