CareerCup

What does duplicate parenthesis mean?
Do we need to find matching parenthesis pairs? Or find the extra parenthesis?

public static boolean hasDuplicateParenthesis(String exp){
		Stack<Character> st = new Stack<Character>();
		for(int i = 0; i < exp.length(); i++){
			char c = exp.charAt(i);
			if(c != ')' && c != '}'){
				st.push(c);
			}else{
				if(c == ')'){
					if(st.peek() == '('){
						return true;
					}
					while(st.peek() != '('){
						st.pop();
					}
					st.pop();
				}
				if(c == '}'){
					if(st.peek() == '{'){
						return true;
					}
					while(st.peek() != '{'){
						st.pop();
					}
					st.pop();
				}
			}
		}
		return false;
	}

bool has_duplicate_paranthesis(const std::string& strExpr)
{
	typedef std::pair <char, char> parPair;
	std::vector<parPair> knownPairs = { { '{', '}' }, { '(', ')' } };
	std::stack<parPair> exprStack;

	for each (auto var in strExpr)
	{
		for each (auto tocken in knownPairs)
		{
			if (tocken.first == var)
			{
				exprStack.push(tocken);
			}
			else if (tocken.second == var)
			{
				if (exprStack.empty())
					return false;

				auto exptr = exprStack.top();

				if (exptr.second != var)
				{
					return false;
				}
				exprStack.pop();
			}
		}
	}

	return exprStack.empty();
}

Implementation is pretty simple with pattern matcher..

Hi,

Here is my implementation with Java.

I assumed that :

1. Given expression is valid, which means all open brackets are closed.
2. Given expression can not be null.
3. Given expression does not contain negatives. (-a + b) negative a is not possible.

Here is the main class :

public class RemoveUselessBracketsInExpression {

	public String removeBrackets(String expression) {
		String cleanExpression = removeSpaces(expression);
		String result = remove(cleanExpression);
		return result;
	}

	private String remove(String expression) {
		Tree tree = createExpressionTree(expression);
		walkOnTreeAndRemoveBrackets(tree.head);
		return createExpressionFromNode(tree.head);
	}

	private Tree createExpressionTree(String expression) {
		Tree tree = new Tree();
		tree.head = trimBracketsAndCreateNode(expression);
		return tree;
	}

	private void walkOnTreeAndRemoveBrackets(Node node) {
		node.hasBrackets = false;
		hasInnerExpressionWithDifferentOperator(node);
	}

	private String createExpressionFromNode(Node node) {
		StringBuilder sb = new StringBuilder();

		if (node.hasBrackets) {
			sb.append("(");
		}
		if (node.operator != 0) {
			sb.append(createExpressionFromNode(node.left));
			sb.append(node.operator);
			sb.append(createExpressionFromNode(node.right));
		} else {
			sb.append(node.expression);
		}
		if (node.hasBrackets) {
			sb.append(")");
		}

		return sb.toString();
	}

	private void hasInnerExpressionWithDifferentOperator(Node node) {
		if (node.operator != 0) {
			if (node.operator == node.left.operator
					|| getPrecedence(node.operator) <= getPrecedence(node.left.operator)) {
				node.left.hasBrackets = false;
			}
			if (node.operator == node.right.operator
					|| getPrecedence(node.operator) <= getPrecedence(node.right.operator)) {
				node.right.hasBrackets = false;
			}
			hasInnerExpressionWithDifferentOperator(node.left);
			hasInnerExpressionWithDifferentOperator(node.right);
		}
	}

	private Node trimBracketsAndCreateNode(String expression) {
		boolean hasBrackets = false;
		boolean contuniue = true;
		String trimmedExpression = expression;

		while (contuniue) {
			hasBrackets = checkHasBrackets(trimmedExpression);
			if (hasBrackets) {
				trimmedExpression = trimmedExpression.substring(1, trimmedExpression.length() - 1);
			}
			if (!checkHasBrackets(trimmedExpression)) {
				contuniue = false;
			}
		}
		return createNode(trimmedExpression, hasBrackets);
	}

	private Node createNode(String expression, boolean hasBrackets) {
		System.out.println(expression);
		int operatorIndex = getOperatorIndex(expression);
		Node node = new Node();
		node.expression = expression;
		if (operatorIndex != -1) {
			node.operator = expression.charAt(operatorIndex);
		}
		if (operatorIndex == -1) {
			node.hasBrackets = false;
		} else {
			node.hasBrackets = hasBrackets;
		}
		if (operatorIndex != -1) {
			node.left = trimBracketsAndCreateNode(expression.substring(0, operatorIndex));
			node.right = trimBracketsAndCreateNode(expression.substring(operatorIndex + 1));
		}
		return node;
	}

	private boolean checkHasBrackets(String expression) {
		int openBrackets = 0;
		for (int i = 0; i < expression.length(); i++) {
			char c = expression.charAt(i);
			if (c == '(') {
				openBrackets++;
			}
			if (c == ')') {
				openBrackets--;
			}
			if (openBrackets == 0 && i < expression.length() - 1) {
				return false;
			}
		}
		return expression.charAt(0) == '(' && expression.charAt(expression.length() - 1) == ')';
	}

	private int getOperatorIndex(String expression) {
		int openBrackets = 0;
		for (int i = 0; i < expression.length(); i++) {
			char c = expression.charAt(i);
			if (c == '(') {
				openBrackets++;
			}
			if (c == ')') {
				openBrackets--;
			}
			if (openBrackets == 0) {
				if (c == '-' || c == '+' || c == '*' || c == '/') {
					return i;
				}
			}
		}
		return -1;
	}

	private String removeSpaces(String expression) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < expression.length(); i++) {
			char c = expression.charAt(i);
			if (c != ' ') {
				sb.append(c);
			}
		}
		return sb.toString();
	}

	private int getPrecedence(char operator) {
		switch (operator) {
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
			return 2;
		default:
			return -1;
		}
	}

	class Tree {
		Node head;
	}

	class Node {
		Node left;
		Node right;

		String expression;
		boolean hasBrackets;
		char operator;
	}
}

I tested this implementation with these cases :

(testing more than one case in a test is not practical, but I preferred to keep simple for this page)

public class RemoveUselessBracketsInExpressionTest {

	private RemoveUselessBracketsInExpression ru;

	@Before
	public void setup() {
		ru = new RemoveUselessBracketsInExpression();
	}

	@Test
	public void test01() {
		assertEquals("a", ru.removeBrackets("a"));
		assertEquals("a", ru.removeBrackets(" a   "));
		assertEquals("a+b", ru.removeBrackets(" (a + b)  "));
		assertEquals("a+b+c", ru.removeBrackets(" ( a + ( b + c ) )  "));
		assertEquals("a+b+c+d", ru.removeBrackets(" ( ( a + b ) + ( c + d ) ) "));
		assertEquals("(a+b)*(c+d)", ru.removeBrackets(" ( ( a + b ) * ( c + d ) ) "));
		assertEquals("a*(b+c)", ru.removeBrackets(" ( a * ( b + c ) ) "));
		assertEquals("a-b*(c+d)", ru.removeBrackets(" ( a - b * ( c + d ) ) "));
		assertEquals("a-b*c+d", ru.removeBrackets("a - b * c + d"));
		assertEquals("a-b*c*d", ru.removeBrackets("a - b * (c * d)"));
		assertEquals("a-b*c*d/e", ru.removeBrackets("a - b * c * (d / e)"));
		assertEquals("a-b*c*d/e", ru.removeBrackets("a - (b * c) * (d / e)"));
		assertEquals("a-(b+c)*d/e", ru.removeBrackets("a - (b + c) * (d / e)"));
		assertEquals("(a-b+c)*d/e", ru.removeBrackets("(a - b + c) * (d / e)"));
		assertEquals("(a-b+c)*d/e", ru.removeBrackets("(a - (b) + c) * (d / e)"));
		assertEquals("a+b-c+d/e", ru.removeBrackets("(a + (b - c) + (d / e))"));
		assertEquals("a+b-c+d/e", ru.removeBrackets("(a + ((b - c)) + (d / e))"));
		assertEquals("a+b-c*d/e", ru.removeBrackets("a + b - c * d / e"));
		assertEquals("(a*b-c)/(d-e)", ru.removeBrackets("((a * b) - c) / (d - e)"));
		assertEquals("(a-b+c)/d-e", ru.removeBrackets("((a - b) + (c)) / d - e"));
		assertEquals("(a+b*c)*d*f*j", ru.removeBrackets("(a + (b*c)) * (d * ( f * j) ) "));
	}
}

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

bool isClosing(char &a)
{
    if(a == ')' || a == '}' || a == ']')
        return true;
    return false;
}

bool isMatching(char &a,char &b)
{
    if(a == '(' && b == ')')
        return true;
    else if(a == '[' && b == ']')
        return true;
    else if(a == '{' && b == '}')
        return true;
    return false;
}

void findDuplicates(string &str)
{
    stack<int> s;
    int len = str.size();
    for(int i = 0;i<len;i++)
    {
        if(!isClosing(str[i]))
            s.push(i);
        else
        {
            if(isMatching(str[s.top()],str[i]))
                cout << "Duplicate at " << s.top() << " " << i << endl;
            else
            {
                while(!s.empty() && !isMatching(str[s.top()],str[i]))
                    s.pop();
            }
            s.pop();
        }
    }
}

int main()
{
    string str;
    cin >> str;
    
    findDuplicates(str);
    
    return 0;
}

String str = "{{ (( a + b ) * (( c + d ))) }}";

		Pattern pattern = Pattern.compile("\\(\\(|\\)\\)");

		Matcher matcher = pattern.matcher(str);
		char prevChar = ' ', currChar;
		while (matcher.find()) {
			currChar = str.charAt(matcher.start());
			if (currChar == ')' && prevChar == '(') {
				System.out.println("Duplicate Found");
			}
			prevChar = currChar;
		}