Compilers and parsers Codechef Solution

Lira is now very keen on compiler development. ūüôā

She knows that one of the most important components of a compiler, is its parser.

A parser is, in simple terms, a software component that processes text, and checks it’s semantic correctness, or, if you prefer, if the text is properly built.

As an example, in declaring and initializing an integer, in C/C++, you can’t do something like:

int = x ;4

as the semantics of such statement is incorrect, as we all know that the datatype must precede an identifier and only afterwards should come the equal sign and the initialization value, so, the corrected statement should be:

int x = 4;

Today, Lira is concerned with an abstract instruction which is composed of the characters “<” and “>” , which she will use on the design of her language, L++ :D.

She is using it as an abstraction for generating XML code Tags in an easier fashion and she understood that, for an expression to be valid, a “<” symbol must always have a corresponding “>” character somewhere (not necessary immediately) after it. Moreover, each “>” symbol should correspond to exactly one “<” symbol.

So, for instance, the instructions:

<<>>

<>

<><>

are all valid. While:

>>

><><

are not.

Given some expressions which represent some instructions to be analyzed by Lira’s compiler, you should tell the length of the longest prefix of each of these expressions that is valid, or 0 if there’s no such a prefix.

Input

Input will consist of an integer T denoting the number of test cases to follow.

Then, T strings follow, each on a single line, representing a possible expression in L++.

Output

For each expression you should output the length of the longest prefix that is valid or 0 if there’s no such a prefix.

Constraints

1 ‚ȧ T ‚ȧ 5001 ‚ȧ The length of a single expression ‚ȧ 106The total size all the input expressions is no more than 5*106

Example

Input:
3
<<>>
><
<>>>
Output:
4
0
2

Compilers and parsers РCodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner s=new Scanner(System.in);
		int t=s.nextInt();
		while(t-->0)
		{
		    String s1=s.next();
		    char[] c=s1.toCharArray();
		    if(c[0]=='>')
		    {
		        System.out.println(0);
		        continue;
		    }
		    int temp=0,count=0,sum=0;
		    for(int i=0;i<c.length;i++)
		    {
		        if(c[i]=='<')
		        {
		            temp++;
		            count++;
		        }
		        if(c[i]=='>')
		        {
		            count--;
		            temp++;
		        }
		        if(count<0)
		        {
		            break;
		        }
		        if(count==0)
		        {
		            sum+=temp;
		            temp=0;
		        }
		    }
		    System.out.println(sum);
		}
	}
}

Compilers and parsers- CodeChef Solution in CPP

#include<iostream>
#include<string.h>
using namespace std;

int main(){
	
	int n;
	cin>>n;
	while(n--)
	{
		string chrAr;
		cin>>chrAr;
		long top=0,cnt=0,tmpCnt=0;
		for(long long i=0;i<chrAr.size();i++)
		{
			if(chrAr.at(i)=='<')
				top++;
			else
			{
				top--;
				if(top<0)
					break;
				tmpCnt++;
				if(top==0)
				{
					cnt=tmpCnt;
				}	
			}
		}	
		cout<<cnt*2<<endl;
	}
	
return 0;
}

Compilers and parsers -CodeChef Solution in Python

for i in range(int(input())):
    s=input()
    c=0
    m=0
    for j in range(0,len(s)):
        if(s[j]=="<"):
            c+=1
        if(s[j]==">"):
            c-=1
        if(c==0):
            m=max(m,j+1)
        if(c<0):
            break
            
    print(m)

Disclaimer: The above Problem (Compilers and parsers) is generated by CodeChef but the solution is provided by Codeworld19.This tutorial is only for Educational and Learning purpose.

Leave a Reply

Your email address will not be published. Required fields are marked *