by Stack is a data structure used for storing collection of data where order in which data is arriving is important. In Stack, insertion and deletion both happened from the same end which is known as “Top”.
The data which is arrived last will be deleted first in Stack. This data ordering is called as Last in First out or LIFO. Before going ahead have a look into Stack basics and Generic Stack Implementation.
Let’s have a look on basic class definition for Generic Stack.
template <typename T>
class StackGeneric
{
private:
int size;
int top;
T* elements;
public:
StackGeneric (int sz);
~StackGeneric ();
bool push (T value);
int pop ();
bool isEmpty ();
int maxSize ();
int entries ();
};
Balanced parentheses in an expression
This is a very generic problem in which we need to find out whether parentheses in an expression is balanced or not. In an expression following parentheses can be possible:
( )
{ }
[ ]
As we know, these parentheses should present in pairs (open and close both) in an expression. For eg:
[(A+B)C+{D(E-F)}-G]( — This expression is not balanced as there is an “)” braces missing.
[(A+B)C+{D(E-F)}-G]) — This expression is not balanced as there is an “(” braces missing.
[(A+B)C+{D(E-F)}-G] — This expression is balanced as all the braces are closed.
In this article, we are looking into the implementation of the same.
Algorithm to check Balanced parentheses in an expression
- Start from the left hand side of the expression and traverse through full expression symbol by symbol.
- If “(” or “{” or “[” symbol is encountered then push that symbol into stack.
- If “)” or “}” or “]” symbol is encountered then pop top element from the stack and it should be the corresponding left braces. If it’s not then parentheses are not balanced.
- Repeat above steps till all the symbols from the expression is traversed.
- If Stack is empty at the end then expression is balanced.
Few of the functions used below are explained in Generic Stack Implementation. Refer those before going ahead.
Let’s look into the sample code.
bool check_balanced_symbols (char* exp)
{
StackGeneric<char> s(100);
char* temp = exp;
while (*temp != '\0')
{
if (*temp == '{' || *temp == '(' || *temp == '[')
{
s.push(*temp);
}
else if (*temp == ')')
{
char x = s.pop();
if (x != '(')
{
cout << "Symbol is not balanced" << endl;
return false;
}
}
else if (*temp == '}')
{
char x = s.pop();
if (x != '{')
{
cout << "Symbol is not balanced" << endl;
return false;
}
}
else if (*temp == ']')
{
char x = s.pop();
if (x != '[')
{
cout << "Symbol is not balanced" << endl;
return false;
}
}
temp++;
}
if (s.entries() > 0)
{
cout << "Symbol is not balanced" << endl;
return false;
}
cout << "Symbol is balanced" << endl;
return true;
}
Let’s define a main function to use above methods.
int main ()
{
char expr[100] = "";
cout << "Enter the Expression" << endl;
cin >> expr ;
if (check_balanced_symbols (expr))
{
cout << "Expression " << expr << " is balanced " << endl;
}
else
{
cout << "Expression " << expr << " is not balanced " << endl;
}
}
Let’s analyze the output of this main function.
Enter the Expression
[(A+B)*C+{D*(E-F)}-G](
Symbol is not balanced
Expression [(A+B)*C+{D*(E-F)}-G]( is not balanced
Enter the Expression
[(A+B)*C+{D*(E-F)}-G])
StackGeneric empty, unable to POP !!!
Symbol is not balanced
Expression [(A+B)*C+{D*(E-F)}-G]) is not balanced
Enter the Expression
[(A+B)*C+{D*(E-F)}-G]
Symbol is balanced
Expression [(A+B)*C+{D*(E-F)}-G] is balanced
