CareerCup

Correcting some typos

correction to your code will make it work.
#include <iostream>
#include<stack>

using namespace std;

int main()
{
stack<char> stackobj;
char input[]="(( a + b ) * (( c + d )))";
int i=0;

while(input[i] != '\0')
{
if(input[i] == '(' || input[i] == '+' || input[i] == '*')
stackobj.push(input[i]);
if(input[i] == ')')
{
if(stackobj.top() == '+' || stackobj.top() == '*')
{
// pop till u find '('
while (stackobj.pop() != '(')
stackobj.pop();
}
else
{
cout << "duplicates parenthesis in the expression, position is " << i<< endl;
return 0;
}
stackobj.pop();
}
i++;
}

if(!stackobj.empty())
{
cout<<"bad input\n">>;
}
else
{
cout <<"No duplicates parenthesis in the expression";
}

return 1;

}

The logic is to find to mutual pairs of left and right bracket who are consecutive. We need a stack and some boolean variables to achieve that.

int findDuplicateParenthesis(string expr)
{
	bool isPrevLeftBracket = false;
	bool isPrevRightBracket = false;
	//bool noGapLeft = false;
	bool noGapRight = false;
	bool isNeighbourAbove = false;
	int length = expr.length();
	stack<ParenthesisType> parenthesisStack;

	for(int i = 0; i < length; i++)
	{
		char c = expr[i];
		if(isspace(c))
			continue;

		if(c == '(' && !isPrevLeftBracket)
		{
			isPrevLeftBracket = true;
			isPrevRightBracket = false;

			if(!parenthesisStack.empty())
			{
				ParenthesisType pt1 = parenthesisStack.top();
				if(pt1.isNeighbourAbove == true)
				{
					pt1.isNeighbourAbove = false;
					parenthesisStack.pop();
					parenthesisStack.push(pt1);
				}
			}

			ParenthesisType pt2;
			pt2.c = c;
			pt2.isNeighbourAbove = false;
			pt2.pos = i+1;
			parenthesisStack.push(pt2);
		}
		else if(c == '(' && isPrevLeftBracket)
		{
			//noGapLeft = true;
			ParenthesisType pt1 = parenthesisStack.top();
			pt1.isNeighbourAbove = true;
			parenthesisStack.pop();
			parenthesisStack.push(pt1);

			ParenthesisType pt2;
			pt2.c = c;
			pt2.isNeighbourAbove = false;
			pt2.pos = i+1;
			parenthesisStack.push(pt2);
		}
		else if(c == ')' && !isPrevRightBracket)
		{
			isPrevRightBracket = true;
			isPrevLeftBracket = false;
			parenthesisStack.pop();
		}
		else if(c == ')' && isPrevRightBracket)
		{
			//noGapRight = true;
			ParenthesisType pt = parenthesisStack.top();

			//condition for duplicate parenthesis
			if(pt.isNeighbourAbove == true)
				return pt.pos;

			parenthesisStack.pop();
		}
		else
		{
			isPrevLeftBracket = false;
			isPrevRightBracket = false;
		}
	}

	return -1;
}

bool hasDuplicateParenthesis(string s)
{
Stack<char> charStack = new Stack<char>();
foreach (char ch in s)
{
if(ch == ' ') continue;
if (ch == ')')
{
int index = charStack.ToList().IndexOf('(');
if (index == -1)
return false;
if (index == 0)
return true;
for (int i = 0; i <= index; i++)
charStack.Pop();
}
else
charStack.Push(ch);
}
return false;
}

Finding as in finding the position? Finding is easy with a stack. The position may vary with an extra ) or ( or both!

Correcting some typos

correction to your code will make it work.
#include <iostream>
#include<stack>

using namespace std;

int main()
{
stack<char> stackobj;
char input[]="(( a + b ) * (( c + d )))";
int i=0;

while(input[i] != '\0')
{
if(input[i] == '(' || input[i] == '+' || input[i] == '*')
stackobj.push(input[i]);
if(input[i] == ')')
{
if(stackobj.top() == '+' || stackobj.top() == '*')
{
// pop till u find '('
while (stackobj.pop() != '(')
stackobj.pop();
}
else
{
cout << "duplicates parenthesis in the expression, position is " << i<< endl;
return 0;
}
stackobj.pop();
}
i++;
}

if(!stackobj.empty())
{
cout<<"bad input\n">>;
}
else
{
cout <<"No duplicates parenthesis in the expression";
}

return 1;

}

1) take a stack S
2) Keep pushing chars from input in S, one by one
3) if charFromInput == ')' , bool check = true and while(S.pop() != '(');
4) if check == true && nextCharFromInput == ')' && S.pop() == '('
Double parantheses detected.

an o(n) without stack solution:
(assuming the input is well parenthized)
step 1:read character from left untill a '(' is found or input ends.
step 2:if input ends exit;
step 3:if '(' is found check if the next character is'(' ?
if false go to step 1;
else check for the duplicacy for the 2nd '(' recursively//"eg:..(((....)))"
if the the next char(suppose i) of 2nd's matching ')' is
another ')' report 1st '(' duplicate;
else go to next 1 with next symbol as i+1;

here each character is visited only once.so tc is o(n).

an o(n) without stack solution:
(assuming the input is well parenthized)
step 1:read character from left untill a '(' is found or input ends.
step 2:if input ends exit;
step 3:if '(' is found check if the next character is'(' ?
if false go to step 1;
else check for the duplicacy for the 2nd '(' recursively//"eg:..(((....)))"
if the the next char(suppose i) of 2nd's matching ')' is
another ')' report 1st '(' duplicate;
else go to next 1 with next symbol as i+1;

here each character is visited only once.so tc is o(n).

How about this jave code

public class RedundantBrackets {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "((a+b)*(c+d)*(e+f))";
		String t;
		int length = s.length();
		int count=1;
		int pos;
		int count1 =0;
		for(int i=0;i<length;i++){
			
			if(s.charAt(i)=='('){
				count++;
			}
			if(count == 2){
				pos = i;
				for(int j=i;j<length-1;j++){
					if(s.charAt(j) == ')'){
						if(s.charAt(j+1) == ')' && (j+1) != length-1){
						
							System.out.println("Redundant bracket present at pos : "+j);
							break;
						}
					}
				}
			}
		}

	}

}

I found a much elegant way to solve this problem


#include<iostream>
#include<stack>
#include<conio.h>

using namespace std;

int main()
{
stack<char> pstack;
stack<int> status;

int flag = 0;
char* expr = "(( a + b ) * (( c + d )))";
int i=0;
int pos;


while(expr[i]!='\0')
{
//cout<<"\n In Loop "<<i<<" : "<<expr[i];
if(expr[i] == ' ')
{
i++;
continue;
}
else if(expr[i]=='(')
{
pstack.push('(');
status.push(i);
status.push(0);

}
else if(expr[i] == ')')
{
flag = status.top();
status.pop();
pos = status.top();
status.pop();
pstack.pop();
if(flag == 0)
{
cout<<"Duplicate Paranthesis End Found at : "<<"("<<pos<<","<<i<<" ) ";
getch();
return 0;
}
}
else
{
status.pop();
status.push(1);
}

i++;

}

getch();
}

We can solve this problem using a single stack. We push open brackets and operators on to a stack. When we encounter a closing bracket, we pop till we reach an open bracket.

The trick is that when we encounter an open bracket and start popping, we MUST encounter at least 1 operator. If we don't, then we know that there is extra parentheses.

Let's go through several cases:


((a+b) * (c+d)) - No extra brackets

Reading from left to right:

1. Push '('
2. Push '('
3. Push '+'
4. Encountered ')', pop '+' and '(' - since we found an operator, this is acceptable.
5. Push '*'
6. Push '('
7. Push '+'
8. Encountered ')', pop '+' and '(' - since we found an operator, this is acceptable.
9. Encountered ')', pop '*' and '(' - since we found an operator, this is acceptable.

Now let's look at a case of extra parentheses:
((a+b) * ((c+d)))

You can dry run this yourself, but we will catch duplication, when we are popping the 2nd to last ')' off the stack, since we will not encounter any operator there !

def detectExtraParanthesis(expression):
    stack = list()
    check = False
    for char in expression:
        if (char != ')'):
            if (check):
                check = False
            stack.append(char)
        else:
            check = True
            #if (len(stack) == 0):
                #return False
            while(char != '(' and len(stack) != 0):
                popped = stack.pop()
                if (popped == '(' and check == True):
                    return False
                elif (popped == '(' and check == False):
                    break;
                else:
                    check = False
                

    if (len(stack) == 0):
        return True

exp = "((a+b)))"
result = detectExtraParanthesis(exp)
if (result):
    print("No Duplicate Paranthesis")
else:
    print("Duplicate Paranthesis")

what should be the output for input : () ?

import java.util.Stack;

public class Solution {

	public static void main(String[] args) {
		String str1 = "(a+b)*(a+c)";

		String str2 = "((a+b)+c)+d";
		String str3 = "((d*(a+c))+k)";
		String str4 = "((a+c))+((d+k))";
		String str5 = "((a+v)*(d*h)+c)";
		String str6 = "((((a+v)*(d*h)+c)))";

		System.out.println(str1 + ": " + getCountOfOuterBrackets(str1));
		System.out.println(str2 + ": " + getCountOfOuterBrackets(str2));
		System.out.println(str3 + ": " + getCountOfOuterBrackets(str3));
		System.out.println(str4 + ": " + getCountOfOuterBrackets(str4));
		System.out.println(str5 + ": " + getCountOfOuterBrackets(str5));
		System.out.println(str6 + ": " + getCountOfOuterBrackets(str6));

	}

	private static int getCountOfOuterBrackets(String str) {

		Stack<Character> brackets = new Stack<Character>(); // create one stack for entering '(' coming open brackets
		Stack<Character> otherCharacters = new Stack<Character>(); // create one stack for counting an alphabets and operator (Other char tha '(';
		
		/*
		 * Logic is :
		 * read a string character by character if it is '('  put it into stack::bracket
		 * if its an other character that '('  and ')' then put it into the stack::otherCharacters
		 * When We encountered the ')'   check  stack::otherCharacters is empty .. 
		 * if its empty it mean redundant barcet  has come  , Increase th count  and pop '(' one element from stack::bracket
		 * If stack::otherCharacters is not empty When ')' has encountered it means.. Its not an redundant bracket
		 * Pop one element from stack::bracket and  and clear the stack::otherCharacters stack 
		 *
		 */
		int count = 0;

		for (int i = 0; i < str.length(); i++) {

			char ch = str.charAt(i);

			if (ch == '(') {
				brackets.push(ch);
			} else if (ch == ')') {

				if (otherCharacters.isEmpty()) {
					count++;
					brackets.pop();
				} else {
					while (!otherCharacters.isEmpty()) {
						otherCharacters.pop();

					}
				}

			} else {
				otherCharacters.push(ch);
			}

		}
		return count;
	}

	
}

void FindDuplicateParethesis(char* input)
{
if(input == NULL)
return;

int len =strlen(input);
if(len == 0)
return;

std::stack<int> s;

for(int i = 0; i < len; ++i)
{
if(input[i] != ')')
{
s.push(i);
}
else
{
int index = s.top();
s.pop();
if(input[index] == '(')
{
printf("uncessary Parethesis at position %d and %d\n", index, i);
}
else
{
while(!s.empty())
{
index = s.top();
s.pop();
if(input[index] == '(')
break;
}
}
}
}

if(!s.empty())
{
printf("bad input\n");
}
}

We can do it by using stack.
if we found "(" we push it to the stack and if we found ")" we pop the "(" from stack. at the end if we have "(" on stack or ")" on the expression parenthesis does not match it have duplicate.

onestopinterviewprep.blogspot.com/2014/03/detect-duplicate-parentheses-in.html