@rahul
Algo for identifying the exact set of parenthesis to be removed would
be:
Take a stack named 'IndStk' to hold the indices of opening
parenthesis. When a '(' parenthesis is encountered push it onto the
stack and if a ')' parenthesis is encountered then pop from the top of
the stack ( i.e the corresponding '(' parenthesis will be removed).
Take 2 arrays or stacks (say, ROpen and RClose ) to basically store
the indices of the duplicate '(' and ')' to be removed from the
expression..
Say, the expression is stored in an array of Expr[N] ...
Now,
i = 0;
While (i < N - 1)
{
if ( Expr[i] == '(' )
IndStk.push(i);
else if ( Expr[i] == ')' )
{
if ( Expr[i-1] == ')' and Expr[IndStk.top() +1 ] == '(' )
{
ROpen.add(IndStk.top() +1);
RClose.add(i - 1);
}
IndStk.pop();
}
++i;
}
// Special case for matching opening brace at index 0 and
corresponding closing brace at index N-1...
// The below code could have been put in the above 'elseif' block but
it will have an additional overhead of checking for the special case
every time it hits the 'elseif' block...
if ( Expr[i] == ')' )
{
if ( Expr[i-1] == ')' and Expr[IndStk.top() +1 ] == '(' )
{
ROpen.add(IndStk.top() +1);
RClose.add(i - 1);
}
// Special case...
if (Expr[IndStk.top()] == 0)
{
ROpen.add(0);
RClose.add(N - 1);
}
IndStk.pop();
}
The above code is not checking for invalid expressions i.e. improper
usage of parenthesis.. If you want to handle that case all you need to
do is before accessing 'IndStk.top()' check if 'IndStk' is empty or
not. If empty, then the usage of parenthesis in the expression is
incorrect. You will also need to add the 'IndStk.IsEmpty()' check at
the end to ensure that no open parenthesis is left after the
expression has been completely parsed.
On Dec 11, 4:23 am, Lucifer <sourabhd2...@gmail.com> wrote:
> @rahul..
>
> there is one exception to the above rule and that is the case with
> unary minus operator..
> for ex : a + (-c) + d will need one parentheses,
> but a + ( -c + d ) will only need 1 instead of 2..
> But for the sake of unary minus u can assume that it will be enclosed
> within a parenthesis..
>
> On Dec 11, 4:07 am, Lucifer <sourabhd2...@gmail.com> wrote:
>
>
>
>
>
>
>
> > @rahul...
>
> > If you are plan to just find out the no. of duplicate parenthesis,
> > then that would be ( No. of open Parenthesis - No. of Operators + 1)
>
> > On Dec 10, 10:22 pm, rahul venkat <rahul911...@gmail.com> wrote:
>
> > > hi everyone,
>
> > > can u suggest an algorithm for finding the duplicate paranthesis in a
> > > given
> > > expression ?
>
> > > for example , the expression (( a + b ) * (( c + d ))) has a set of
> > > duplicate paranthesis.
>
> > > thanks in advance .
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
