Write a program to validate whether the brackets in the given input string are balanced or not.
Examples:
Input : {[()]}
Output : Valid
Input :{{(}}[]
Output : Invalid
Explanation:
This problem is a very common application of stacks in data structures. An opening bracket may be ‘{‘,'[‘,'(‘ and their corresponding closing brackets are ‘}’,’]’,’)’. The brackets are said to be balanced if and only if for each opening bracket there is exactly one closing bracket, without any incomplete pair of brackets.
This problem can easily using stack implementation. Stack is a data structure that follows the Last In First Out Concept. Push the upcoming opening brackets in the stack, if any closing bracket occurs then check in stack if it’s corresponding opening bracket occurs. If it exists then pop the opening bracket.
If the value of top is greater than 0 then it is invalid.
C++ code implementation :
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char stack[100];
int top=-1,j,flag=0;
string s;
getline(cin,s);
int i=s.size();
for(j=0;j<i;j++)
{
if(s[j]=='{' || s[j]=='(' || s[j]=='[')
{
top++;
stack[top]=s[j];
}
if(s[j]=='}' || s[j]==']' || s[j]==')')
{
if(s[j]==')' && stack[top]=='(')
{
top--;
}
if(s[j]=='}' && stack[top]=='{')
{
top--;
}
if(s[j]==']' && stack[top]=='[')
{
top--;
}
}
}
if(top<0)
cout<<"Valid";
else
cout<<"Invalid";
return 0;
}
Output:
Input : {[()]}
Output : Valid
Input :{{(}}[]
Output : Invalid
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.