We are using two stacks here
i) to store the paranthesis (x) ii) to store the asterik (y)
-→ Whenever we encounter a open paranthesis or an asterick we push their indices to respective stacks
-→ If we encounter a closed paranthesis first we'll check if the paranthesis stack is empty or not
if not empty we'll pop the top element of stack . if not we'll check the asterik stack and do the same with it
-→ if both are empty and there is a closing paranthesis to match with we can return false
-→ What if there are no closing paranthesis in the given string
Ex : “( ( ( * * *”
-→ we push the indices into the stack and there are not empty
-→ that means even we iterate over the entire string , the stacks are not empty
-→ then we'll compare the indices lying on top of each stack,
if open paranthesis index is greater than closing one (matching with asterick here ) then we return false
-→ else we pop both stack's top
-→finally if the paranthesis stack is empty means our ans is true
else its false
#include<bits/stdc++.h>
bool checkValidString(string &s) {
stack<int> x;
stack<int> y;
for(int i=0;i<s.size();i++)
{
char c=s[i];
if(c=='(')
{
x.push(i);
}
else if(c=='*')
{
y.push(i);
}
else
{
if(!x.empty())
{
x.pop();
}
else if(!y.empty())
{
y.pop();
}
else
return false;
}
}
while(!x.empty() && !y.empty())
{
if(x.top() > y.top())
return false;
x.pop();y.pop();
}
return x.empty();
}