COMPILER: Compilers and parsers

COMPILER: Compilers and parsers

Link for the problem: COMPILER

SOLUTION:

Let S be a valid substring of the given string. Then,
1.) '<'+S+'>' will be a valid substring.
2.) Similarly, if S1 is also a valid substring and S and S1 are connected then S+S1 will be a valid substring.
In order to solve the problem, first, we find all valid substring.
To find valid substring we use a stack.

i) If the s[i] is '<', then push its index in the string.
ii) If s[i] is '>' and stack is not empty, then substring from the top stack index to the current ith index will be a valid substring.
Implementing above with an array of length of the input string, where the initial value of each element will be '-1', and if there is a valid substring from index i to index j, then arr[i] =j.
As problem ask us to find longest prefix substring, we have to start from index i=0, as if arr[i]!=-1 then there is a valid substring from i to arr[i], Now we check for index i=a[i]+1 in similar manner.


CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        string s;
        cin>>s;
        stack <int> st;
        int i,j,k,l;
        l=s.size();
        int a[l]={-1};
        memset(a,-1,sizeof(a));
        for(i=0;i<l;i++)
        {
            if(s[i]=='<')
            {
                st.push(i);
            }
            else
            {
                if(st.size())
                {
                    a[st.top()]=i;
                    st.pop();
                }
            }
        }
        int sm=0;
        for(i=0;i<l;)
        {
            if(a[i]!=-1)
            {
                sm+=a[i]-i+1;
                i=a[i]+1;
            }
            else
            break;
        }
        printf("%d\n",sm);
    }
    return 0;

}