Given
a sequence of parenthesis, check if the parenthesis are balanced and
make a valid expression. For example, an expression { [ ] }is
balanced and correct, where as an expression { [ } ] or { [ { } ] is
not balanced.
There
are three kinds of parenthesis - {}, [], (). One approach to solve
this problem is to use a stack. The idea is that a close parenthesis
is always preceded by an open parenthesis of the same type. When an
open parenthesis is encountered, it is pushed onto the stack. When a
close parenthesis is encountered, it should always pair up with the
open parenthesis on the top of the stack to make it a valid
expression. This pair is then discarded. When the entire expression
is traversed, an empty stack confirms that the input expression is
balanced and valid.
Consider
an expression { [ ( ) ] ( ) } as an example. Following shows the
step-by-step traversal: (the top of the stack is highlighted)
Input
character = {. Push it onto the stack.
-
{
Input
character = [. Push it onto
the stack.
-
[{
Input character
= (. Push it onto the stack.
-
([{
Input character
= ). Check it with the character on the top of
the stack, which is (. It makes a valid pair. Pop ( from the stack.
-
[{
Input character
= ]. Check it with the character on the top of
the stack, which is [. It makes a valid pair. Pop [ from the stack.
If the input character is a } instead of a ], it does not make a
valid pair and hence the parenthesis expression is not balanced.
-
{
Input character
= (. Push it onto the stack.
-
({
Input character
= ). Check it with the character on the top of
the stack, which is (. It makes a valid pair. Pop ( from the stack.
-
{
Input character
= }. Check it with the character on the top of
the stack, which is {. It makes a valid pair. Pop { from the stack.
The end of input
is reached and the stack is empty. Hence, the given input expression
is balanced.
Following is the
C++ code:
bool
IsBalanced(const
string&
expression_input) {
stack<char>
p;
int
i = 0;
int
expression_input_length = expression_input.length();
while(i
< expression_input_length) {
char
input = expression_input[i];
if(input
== '{' ||
input == '['
|| input == '(')
{
p.push(input);
}
else
if(input
== '}' ||
input == ']'
|| input == ')')
{
if(p.empty())
{ //stack is empty
return
false;
}
char
stack_top = p.top();
p.pop();
//does
not make a valid pair
if((stack_top
== '(' &&
input != ')')
|| (stack_top == '{'
&& input != '}')
||
(stack_top == '['
&& input != ']')
) {
return
false;
}
}
else
{ //a
character other than parenthesis is encountered
cout
<< "Invalid input character
encountered" << endl;
return
false;
}
++i;
}
if(p.empty())
{ //end of
input is reached; stack is empty
return
true;
}
return
false;
}
No comments:
Post a Comment