Problem
Duplicate parenthesis means: ((c+d))
. Here ()
is extra which is duplicate.
Examples:
((a+b))
can reduced to(a+b)
, this duplicate(a+(b)/c)
can reduced to(a+b/c)
because b is surrounded by()
which is duplicate(a+b*(c-d))
doesn’t have any duplicates or multiple brackets
You can use stack:
- start to
push
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.
Complexity Analysis
Implementation
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();
}
}
}
}
}