Monday, July 20, 2015

A program to detect if an expression is valid


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