CareerCup

You can use stack, start pushing each character from input string till you not hit close parenthesis. When you hit close parenthesis, start pop the element till you not hit open parenthesis. If the immediate pop hit open parenthesis than that is duplicate parenthesis.
Note: this algo will fail, if one put false parenthesis in string like: () .... Code as:

public void FindDuplicateparenthesis(string input)
        {
            Stack<char> inputStack = new Stack<char>();
            foreach (char inputChar in input.ToCharArray())
            {
                if (inputChar != ')')
                {
                    inputStack.Push(inputChar);
                }
                else
                {
                    char popChar = inputStack.Pop();
                    if (popChar == '(')
                        Console.WriteLine("Duplicate Find ");
                    else
                    {
                        while (popChar != '(')
                        {
                            popChar = inputStack.Pop();
                        }
                    }
                }
            }
        }

bool DuplicateBraces(const char * exp, int len)
{
	stack<int> braceIndices;
	int lastPop = 0;
	int prevIndex = -1;

	for (int i = 0; i < len; i++)
	{
		if (exp[i] == ' ')
			continue;

		if (exp[i] == '(')
		{
			braceIndices.push(i);
			lastPop = 0;
		}
		else if (exp[i] == ')')
		{
			int topIndex = braceIndices.top();
			if (((prevIndex - topIndex) == 1) && lastPop == 1)
				return true;
			braceIndices.pop();
			prevIndex = topIndex;
			lastPop = 1;
		}
		else
		{
			lastPop = 0;
		}
	}

	return false;
}

public class Parenthesis{

     public static void main(String []args){
        System.out.println("Parenthesis valid : " 
                            + hasValidParenthesis("abcd"));
     }
     
     
    public static boolean hasValidParenthesis(String s) {
        
        // negative conditions
        if( null == s ) return false;
        if( s.isEmpty() ) return false;
        if( s.indexOf('(') == -1 && s.indexOf(')') == -1 ) return false;
        
        // to track matching Parenthesis
        int count = 0;
        // to track each char
        int index = 0;
        // array to know if there is content between two parenthesis
        boolean[] contentArray = new boolean[50];

        for(char c : s.toCharArray()) {
             
            if( c == '(') {
                count++;
                
            } else if ( c == ')') {
                
                if( count == 0 ) {  
                    // ')' encountered without any prior '(' 
                    return false;
                }
                // if content is not present between ( and ), then 
                // treat them as a duplicate entry
                if( false == contentArray[count-1] ) {
                    return false;
                }
                contentArray[count-1] = false;
                    
                 // decrement Parenthesis count
                 count --;
            } else if( count > 0 ) {
                // store the content between parenthesis
                if(!contentArray[count-1])
                    contentArray[count-1] = true;
            }
            // increment index
            index++;
        }
         
        return (count == 0);
     }
}

Hi,can you describe what "duplicate" here means? I am understanding it means more than one ")" or "(" or "}" or "{"

public static int FindDuplicateParnth(string s)
        {
            s = s.Replace(" ", "");

            Stack<Parenth> stack = new Stack<Parenth>();
            char c;
            int lastOpen = - 1, lastClose = -1;

            for (int i = 0; i < s.Length; i++)
            {
                c = s[i];
                if (c != '(' && c != ')')
                    continue;
                
                if (c == '(')
                {
                    stack.Push(new Parenth(c, i));
                    continue;
                }

                if(c == ')')
                {
                    if(stack.Peek().position + 1 == lastOpen && i - 1 == lastClose)
                    {
                        return lastOpen;
                    }
                    lastOpen = stack.Pop().position;
                    lastClose = i;
                    continue;
                }
            }

            return -1;
        }

If white spaces are removed, then for any two pairs of parenthesis in the expression, there are 5 kinds of cases we need to take care of:
1.((exp)) such as ((a+b))
2.(exp(exp)) such as (a-(b+c))
3.((exp)exp) such as ((a+b)*c)
4.(exp(exp)exp) such as (a/(b-c)+d)
5.(exp)exp(exp) such as (a+b)/(c*d)
Only the first kind has redundant outside parenthesis, so all we need to do is find out the ocurrances of two pairs of parenthesis like the first kind.
Following is code in C++11:

#include <cctype>
#include <stack>
#include <vector>
#include <string>
#include <utility>
#include <iostream>
#include <unordered_map>
using namespace std;

void buildMapOfStringWithoutSpaces(string& s, unordered_map<int,int>& positionMap, const string& src)
{
	for(int k = 0, i = 0, len = src.size(); i < len; ++i){
		if(isspace(src[i])) continue;
		s.push_back(src[i]);
		positionMap[k++] = i;
	}
}
void remap(vector<pair<int,int> >& v, unordered_map<int,int>& positionMap)
{
	for(int i = 0, n = v.size(); i < n; ++i){
		v[i].first  = positionMap[v[i].first];
		v[i].second = positionMap[v[i].second];
	}
}
void findRedundantParenthesis(vector<pair<int,int> >& v, const string& exp)//exp has no spaces
{
	v.clear();
	if(exp.empty()) return;

	stack<int> st;
	for(int i = 0, len = exp.size(); i < len; ++i){
		if(exp[i] == '('){
			if(!st.empty() && exp[st.top()] == ')'){//previous right's pair has no reduntant
				st.pop();
				st.pop();
			}
			st.push(i);
		}
		else if(exp[i] == ')'){
			if(exp[st.top()] == ')'){//check if this pair is redundant
				int preRight = st.top();
				st.pop();
				int preLeft = st.top();
				st.pop();
				if(i == preRight + 1 && st.top() == preLeft - 1){//this pair is redundant
					v.push_back(make_pair(st.top(), i));
				}
			}
			st.push(i);
		}
	}
}

int main()
{
    vector<pair<int,int> > v;
    string expWithoutSpaces;
    unordered_map<int,int> positionMap;

    buildMapOfStringWithoutSpaces(expWithoutSpaces, positionMap, "((( a + b ) * (( c - d ))))");
    findRedundantParenthesis(v, expWithoutSpaces);
    if(!v.empty()){
        remap(v, positionMap);
        cout << "redundant parenthesis are at:\n";
        for(int i = 0; i < v.size(); ++i){
            cout << "(" << v[i].first << ", " << v[i].second << ")\n";
        }
    }

    return 0;
}

time complexity O(n), space complexity O(n)

a naive approach is traverse the string, left to right, for occurrence of )) and replace then with some unicode char(which is not part of string). Traverse again in string from right to left to find occurrence of (( again replacing consequent pair with same unicode.
Then we can just check the balance using a stack. If its balanced we have duplicates.
let me know loopholes, as I am not entirely sure about this approach

From my understanding of the question, regexp are much more easier and should do too. Or am I ignoring something?

String inputData = "(( a + b ) + (( c + d )))";
inputData = inputData.replaceAll("\\(+", "\\(");
inputData = inputData.replaceAll("\\)+", "\\)");

expressionString = (( a + b ) + (( c + d )))

Step1 : In the expression look for "((" and store in a string - subStr
Step2: Look for the next occurrence of ')' and store its index
Step3: Look for the character at index+1
if(expressionString.charAt(index+1) == ')'){
print("expression contains duplicate parenthesis ");
break;
}
else{
subStr = " ";
}

@Miral and @Sehs -
For finding duplicate parenthesis... this simple means your statement would be having "((" i.e., two starting parenthesis... once you find this.. find the next closing parenthesis.. ')' and if the next character in the string is also ')' then this means duplicate parenthesis exist...

package com.sample;

import java.util.ArrayList;
import java.util.List;

public class Sample1 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String x = "(( a + b )) + (( c + d )))";
		List list = new ArrayList();
		for(int i=0;i<x.length();i++){
			if(x.charAt(i)=='(' && x.charAt(i+1)!=')' && x.charAt(i+1)!='(' && i != x.length()-1){
				list.add(i);
			}
			if(x.charAt(i)==')' && x.charAt(i-1)!=')' && x.charAt(i-1)!='(' && i!=0){
				list.add(i);
			}
		}
		System.out.println(list);
		for(int i=0;i<list.size();i=i+2){
			if(Integer.valueOf(list.get(i).toString())!=0 &&
					x.charAt(Integer.valueOf(list.get(i).toString())-1)=='('&&
					x.charAt(Integer.valueOf(list.get(i+1).toString())+1)==')'){
				System.out.println("Duplicate braces found at starting position "+
					(Integer.valueOf(list.get(i).toString())-1)+" and ending position "+
						(Integer.valueOf(list.get(i+1).toString())+1));
			}
		}
		

	}

}

public static void removeDuplicate(String exp){		
		int end = exp.length() - 1 ;
		char [] chs = exp.toCharArray() ;
		Stack<Character> stack = new Stack<Character>(); 
		for (int i = 0 ; i <= end ; ++i){
			if (chs[i] == '('){
				if (!stack.isEmpty() && stack.peek() == '('){
					System.out.println("find " + stack.peek() + chs[end--]);
					stack.pop();
				}
			
			}
			stack.push(chs[i]);
		}
		
		for (Character c : stack){
			System.out.print(c);
		}

}

public static void removeDuplicate(String exp){		
		int end = exp.length() - 1 ;
		char [] chs = exp.toCharArray() ;
		Stack<Character> stack = new Stack<Character>(); 
		for (int i = 0 ; i <= end ; ++i){
			if (chs[i] == '('){
				if (!stack.isEmpty() && stack.peek() == '('){
					System.out.println("find " + stack.peek() + chs[end--]);
					stack.pop();
				}
			
			}
			stack.push(chs[i]);
		}
		
		for (Character c : stack){
			System.out.print(c);
		}

}

There's a duplicate version of this question, could not post a link to the original post since careercup.com does not allow links in comments but the Question ID is 12011927.

Here's my version in C#:

// Iterate through the string and for each character,
        // if the character is a '(' or any of the operators
        // push it to the stack
        // If the character is a ')', then pop any operators and the 
        // matching '('. However when you try to pop if you only find a '('
        // then this means it is a duplicate paranthesis.
        static int GetNumberOfDuplicateParanthesis(string input)
        {
            int countOfDuplicates = 0;

            input = input.Replace(" ", "");

            Stack<char> chars = new Stack<char>();

            for (int i = 0; i < input.Length; i++)
            {
                if ((input[i] == '(') ||
                    (input[i] == '+') ||
                    (input[i] == '*') ||
                    (input[i] == '-') ||
                    (input[i] == '/'))
                {
                    chars.Push(input[i]);
                }
                else if (input[i] == ')')
                {
                    if (chars.Peek() == '(')
                    {
                        countOfDuplicates++;
                        Console.WriteLine("Duplicate paranthesis found at {0}", i);
                    }
                    else
                    {
                        bool done = false;
                        while (!done)
                        {
                            if (chars.Peek() == '(')
                            {
                                done = true;
                            }

                            chars.Pop();
                        }
                    }
                }
            }

            return countOfDuplicates;
        }

bool DuplicateBraces(const char * exp, int len)
{
	stack<int> braceIndices;
	int lastPop = 0;
	int prevIndex = -1;

	for (int i = 0; i < len; i++)
	{
		if (exp[i] == ' ')
			continue;

		if (exp[i] == '(')
		{
			braceIndices.push(i);
			lastPop = 0;
		}
		else if (exp[i] == ')')
		{
			int topIndex = braceIndices.top();
			if (((prevIndex - topIndex) == 1) && lastPop == 1)
				return true;
			braceIndices.pop();
			prevIndex = topIndex;
			lastPop = 1;
		}
		else
		{
			lastPop = 0;
		}
	}

	return false;
}

bool DuplicateBraces(const char * exp, int len)
{
	stack<int> braceIndices;
	int lastPop = 0;
	int prevIndex = -1;

	for (int i = 0; i < len; i++)
	{
		if (exp[i] == ' ')
			continue;

		if (exp[i] == '(')
		{
			braceIndices.push(i);
			lastPop = 0;
		}
		else if (exp[i] == ')')
		{
			int topIndex = braceIndices.top();
			if (((prevIndex - topIndex) == 1) && lastPop == 1)
				return true;
			braceIndices.pop();
			prevIndex = topIndex;
			lastPop = 1;
		}
		else
		{
			lastPop = 0;
		}
	}

	return false;
}

((a+b)) in this example one operator is there so there should be only one open braces should present, ((a)) in this case zero, ((a*b)+(a-b)) in this case three.

So just find out the count of open braces and number of operators.If they equal no duplicates, if not duplicates are present.
if it is wrong please correct me.
thanks.

push the open parenthesis and the operators and check the top element on seeing a closing parenthesis. If it is open one we have duplicate.

int check(char s[])
{
    int i=0;
    char ch;
    while(s[i]!='\0')
    {
       if(s[i]=='(' || s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')
          push(s[i]);
       else if(s[i]==')')
       {
            ch=pop();
            if(ch=='(')
               return 1;
            while((ch=pop())!='(')
                ;
       }
       i++;
    }
    return 0;
}

Here is a working version in Python.

def find_duplicate(expr):
  stack=[]
  char_in_between = 0
  for i in range(0, len(expr)):
    if expr[i] == '}' or expr[i] == ')':
      pair = '{' if expr[i] == '}' else '('
      pop=''
      while(len(stack) > 0 and pop != pair):
        pop = stack.pop()
        if (pop != '{' and pop != '('): char_in_between +=1
      if char_in_between == 0:
        print "duplicate parenthesis!!"
        break
      char_in_between = 0
    else:
      stack.append(expr[i])

Step 1: Run through the code
Step 2: Search for the brackets
Step 3: search for a '( )' pair
Step 3a: If there is another opening bracket just before '(' and if there is a closing bracket just after ')' ;then there is a duplicate
Step 3b : Else; replace the section '(.....)' by some characters say 'XYZ..'.
Step 4: Repeat from step 3 until u reach the outermost bracket .

Am i correct??

package misc;


import java.util.*;

public class RemoveDupeBrackets2 {

    public static void main(String[] args) {
        String expression = "(((a+b)+c))";
        new RemoveDupeBrackets2().removeDupes(expression);
    }

    private void removeDupes(String expression) {
        char[] chars = expression.toCharArray();
        LinkedList<BracketPair> pairs = new LinkedList<BracketPair>();

        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            if (aChar == '(') {
                BracketPair pair = new BracketPair();
                pair.leftIdx = i;
                pairs.add(pair);
            } else if (aChar == ')') {
                ListIterator<BracketPair> iterator = pairs.listIterator(pairs.size());
                while (iterator.hasPrevious()) {
                    BracketPair pair = iterator.previous();
                    if (pair.rightIdx == null) {
                        pair.rightIdx = i;
                        break;
                    }
                }
            }
        }

        for (BracketPair pair : pairs) {
            System.out.println(pair);
        }

        HashSet<BracketPair> set = new HashSet<BracketPair>(pairs);
        for (BracketPair next : set) {
            BracketPair possibleDupe = new BracketPair();
            possibleDupe.leftIdx = next.leftIdx - 1;
            possibleDupe.rightIdx = next.rightIdx + 1;

            if (set.contains(possibleDupe)) {
                System.out.println("Dupe pair : " + possibleDupe);
                chars[possibleDupe.leftIdx] = ' ';
                chars[possibleDupe.rightIdx] = ' ';
            }
        }

        System.out.println(String.valueOf(chars));

    }

    class BracketPair {
        Integer leftIdx = null;
        Integer rightIdx = null;

        BracketPair() {
        }

        @Override
        public String toString() {
            return "BracketPair{" +
                    "leftIdx=" + leftIdx +
                    ", rightIdx=" + rightIdx +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            BracketPair that = (BracketPair) o;
            return this.leftIdx.equals(that.leftIdx) && this.rightIdx.equals(that.rightIdx);
        }

        @Override
        public int hashCode() {
            int result = leftIdx != null ? leftIdx.hashCode() : 0;
            result = 31 * result + (rightIdx != null ? rightIdx.hashCode() : 0);
            return result;
        }
    }
}

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) ) "));
	}
}

public class FindDuplicateParenthesis {
 
    public static void main(String[] args) {
        String str = "(( a + b ) ()+ ( c + d ))";
        System.out.println(findduplicateparenthe(str));
    }

    public static boolean findduplicateparenthe(String str){
        Stack st = new Stack();
        int counter = 0;
        char arr[] = str.toCharArray();
        
        for (int i=0; i< str.length();i++){
            if(arr[i] == '('){
                st.push(arr[i]);
   //             System.out.println(arr[i]);
                counter++;
                if(arr[i] == '(' && arr[i] == '\0'){
                    System.out.println("false1");
                    return false;} 
            }
        
            if(arr[i] == ')'){
                st.pop();
   //             System.out.println(arr[i]);
            counter--;
                if(arr[i] == '\0') {
                    System.out.println("true1");
                return true;
                }
            }
        }
        
        if(counter == 0){
        return true;}
        else{
        return false;}
    }
}

Here is the algorithm and implementation in Objective-C
Stacks is implemented using NSMutableArray
1.if ( --> check if lastObject in ORStacks is ( ; then append ( to String or push ( to ORStacks
2.if operator/operand append to String
3.if ) --> check if lastObject in ORStacks is ( ;then push ) to String,pop ORStacks if ORStacks is not empty;else move to the next one

//Eliminate duplicate parantheses in expression
#import<Foundation/Foundation.h>
#import<UIKit/UIKit.h>
@interface DuplicateParantheses
@property(nonatomic)NSMutableArray *stacks;
@property(nonatomic)NSString *output;
-(NSString*)removeDuplicateFromExpression:(NSString*)expression;
@end
@implementation DuplicateParantheses
-(NSMutableArray*)stacks
{
if(!_stacks)
{
_stacks = [[NSMutableArray alloc]init];
}
return _stacks;
}
-(NSString*)output
{
if(!_output)
{
_output = [[NSString alloc]init];
}
return _output;
}
-(NSString*)removeDuplicateFromExpression:(NSString*)expression
{
for(int i=0;i< expression.length-1;i++)
{
 NSString *item = [NSString stringFromChar:[expression characterAtIndex:i]];
 if([item isEqualToString@"("] && [[self.stacks lastObject]isEqualToString:@"("])
     [self.output appendStringFromString:item];
    elseif([item isEqualToString@"("]) [self.stacks addObject:item];
    elseif([item isEqualToString@")"]&& [[self.stacks lastObject]isEqualToString:@"("])
    {
    [self.output appendStringFromString:item];
    if([self.stacks length])[self.stacks removeLastObject];
    }
    else
    {
    [self.output appendStringFromString:item];
    }
}
return output;
}

@end

While doing infix to postfix conversion. If we get a ")" we pop the stack until we get a "(" . Now we see that we immediately encounter a "(" for a right parenthesis it indicates that it is a duplicate parenthesis.

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

int main()
{
	string expr;
	char prev='0';
	int count_at_suspect_duplicate;
	cin >>expr;
	int count=0;
	for(int i=0; i<expr.length(); i++)
	{
		if (expr[i] == '(') 
		{
			if (prev == '(') //assumption that string has had whitespace removed
				count_at_suspect_duplicate=count;
			count++;
		}
		if (expr[i] ==')')
		{
			if (prev==')')
				if (count_at_suspect_duplicate==count)
					cout<< "location "<<i+1<<" contains duplicate\n";
		}
		count--;
		prev=expr[i];
	}
}

As far as I understand this is parenthesis matching problem:
1- If you just want to check if all parenthesis are matching, you can do that in O(n) time and O(1) space. Loop over all chars in the string, whenever you find "(" increase a counter and whenever you find ")" decrease the counter and the final result must equal to 0. Here is a sample C# code:

bool CheckMatchingParenthesis(string expression)
{
	int count = 0;
	for(int I=0; I < expression.Length; I++)
	{
		if( expression[I] == '(' )
			count++;
		else if (expression[I] == ')' )
			count--;
		if(count < 0)
			return false; //Closing ')' that is not matched
	}
	return count == 0;
}

2- If you want the index of all unmatched parenthesis, you need two stacks: one for opening '(' (say S1) and one for unmatched closing ')' (Say S2). Whenever you find an opening ( you add its index to the stack S1, whenever you find a closing ')' you remove the top element from S1, if S1 was already empty (unmatched closing tag), then add index of ')' to S2. Here is a sample code

int[] GetUnMatchedParenthesis(string expression)
{
	Stack opening = new Stack();
	Stack closing = new Stack();
	for(int I=0; I < expression.Length; I++)
	{
		if( expression == '(' )
		{
			opening.Push(I);
		}
		if( expression == ')' )
		{
			if(opening.IsEmpty())
			{
				closing.Push(I);
			}
			else
			{
				opening.Pop();
			}
		}
	}
	int[] res = new int[0];
	Array.AddRange(res, opening.ToArray());
	Array.AddRange(res, closing.ToArray());
	return res;
}

This will take O(n) time and worst case of O(n) space (if all parenthesis are opening or closing)