C++ Code
#include
using namespace std;
bool match(const char exp[],const int s)
{
// declare a character array to perform stack operations
char stack[s];
// declare top and initialize to -1 and flag to 0
int top=-1,i,flag=0;
// visit all characters in the expression string
for(i=0;i {
// if the character is [ or ( or { then push it into stack
if(exp[i]=='[' || exp[i]=='(' || exp[i]=='{')
{
top++;
stack[top]=exp[i];
}
// if the character is ] or ) or } then check conditions
else if(exp[i]==']' || exp[i]==')' || exp[i]=='}')
{
// check stack is empty or not
if(top!=-1)
{
// check all possible failure conditions
if(exp[i]==')' && (stack[top] == '{' || stack[top]=='['))
{
flag = 1;
break;
}
else if(exp[i]==']' && (stack[top] == '{' || stack[top]=='('))
{
flag = 1;
break;
}
else if(exp[i]=='}' && (stack[top] == '(' || stack[top]=='['))
{
flag = 1;
break;
}
top--;
}
else
{
flag=1;
break;
}
}
}
// after visiting all characters of expression string check if stack is not empty and flag is 1. if any one of the condition is true return false. otherwise return true
if(top>=0 || flag==1)
return false;
else
return true;
}
int main()
{
// declare character array to store expression
char exp[10000];
cout<<"Enter an Expression"<
// read expression from user
cin.getline(exp, 10000);
int s=0;
// find the length of the expression string
for(int i=0;exp[i]!='\0';i++)
{
s++;
}
// call the match function
bool status = match(exp,s);
// print the result based on value returned by match() function
if(status == 1)
cout<<"true"< else
cout<<"false"<
}
Sample Input/Output is attached
#include
using namespace std;
bool match(const char exp[],const int s)
{
// declare a character array to perform stack operations
char stack[s];
// declare top and initialize to -1 and flag to 0
int top=-1,i,flag=0;
// visit all characters in the expression string
for(i=0;i {
// if the character is [ or ( or { then push it into stack
if(exp[i]=='[' || exp[i]=='(' || exp[i]=='{')
{
top++;
stack[top]=exp[i];
}
// if the character is ] or ) or } then check conditions
else if(exp[i]==']' || exp[i]==')' || exp[i]=='}')
{
// check stack is empty or not
if(top!=-1)
{
// check all possible failure conditions
if(exp[i]==')' && (stack[top] == '{' || stack[top]=='['))
{
flag = 1;
break;
}
else if(exp[i]==']' && (stack[top] == '{' || stack[top]=='('))
{
flag = 1;
break;
}
else if(exp[i]=='}' && (stack[top] == '(' || stack[top]=='['))
{
flag = 1;
break;
}
top--;
}
else
{
flag=1;
break;
}
}
}
// after visiting all characters of expression string check if stack is not empty and flag is 1. if any one of the condition is true return false. otherwise return true
if(top>=0 || flag==1)
return false;
else
return true;
}
int main()
{
// declare character array to store expression
char exp[10000];
cout<<"Enter an Expression"<
// read expression from user
cin.getline(exp, 10000);
int s=0;
// find the length of the expression string
for(int i=0;exp[i]!='\0';i++)
{
s++;
}
// call the match function
bool status = match(exp,s);
// print the result based on value returned by match() function
if(status == 1)
cout<<"true"< else
cout<<"false"<
}
Sample Input/Output is attached