VietMX Staff asked 4 years ago
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
pusheach character from input string till you not hit close parenthesis. - when you hit close parenthesis, start
popthe element till you not hit open parenthesis. - If the immediate
pophit 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();
}
}
}
}
}