An expression is valid only if the various paranthesis { [ ( are matched and nested correctly
Write a function to see if they are matched
Solution
I used a stack to store the left facing symbols. If I detected the right facing symbols ), ] and } I checked the stack for the left facing symbols (, {, [
bool isValid(string s)
{
bool flag = true;
stack<char> sp;
for (int index = 0; index < s.length(); index++)
{
if ((s[index]=='[')||(s[index]=='{')||(s[index]=='('))
{
sp.push(s[index]);
}
if (s[index]==']')
{
if (sp.empty())
{
return false;
}
if ((!sp.empty()) && (sp.top() != '['))
{
return false;
}
if ((!sp.empty()) && (sp.top() == '['))
{
sp.pop();
}
}
if (s[index]=='}')
{
if (sp.empty())
{
return false;
}
if ((!sp.empty()) && (sp.top() != '{'))
{
return false;
}
if ((!sp.empty()) && (sp.top() == '{'))
{
sp.pop();
}
}
if (s[index]==')')
{
if (sp.empty())
{
return false;
}
if ((!sp.empty()) && (sp.top() != '('))
{
return false;
}
if ((!sp.empty()) && (sp.top() == '('))
{
sp.pop();
}
}
}
if (sp.empty() != true)
{
return false;
}
return flag;
}
No comments:
Post a Comment