Compile Code

Concepts Used:

Stacks.

Difficulty Level:

Medium.

Problem Statement :

Given a string of open angular bracket ‘<‘ and closed bracket ‘>’. The task is to find the length of longest balanced prefix.
Example: <<><< , >><< will give compilation error, while <>,
<><><>, <<<>>> will not.

See original problem statement here

Example:

Input:
4
<<>>
2
><
4
<>>>

Output:
4
0
2

Explanation:
Case-1:
The whole string is error-free. So, the longest prefix is the string itself.

Case-2:
There is no prefix which is error-free.

Case-3:
<> longest prefix is valid. So, 2 is answer.

Solving Approach:

  1. Every time we encounter a '<', we push it onto the stack and increment open counter. according to fundamentals of data structures in c++.
  2. For every '>' encountered, we pop a '<' from the stack and increment close counter.
  3. If '<' isn't available on the stack for popping at anytime or if stack contains some elements after processing complete substring, the substring of parentheses is invalid,hence we exit.

Solutions:

#include <stdio.h>
int main()

    {

    // write your code here

    int t,n,i;

    scanf("%d",&t);

     while(t--){

    scanf("%d",&n);

    char str[n+1];

    scanf("%s",str);

    int stack[n],top=-1;

    for(i=0;i<n;i++){

      if(str[i]=='<'){

        stack[++top]=i;

      }

      else{

        if(top==-1){

          printf("%d\n",i);

          break;

        }

        else{

          top--;

        }

      }

    }

    if(i==n){

      if(top==-1){

        printf("%d\n",n);

      }

      else{

        printf("%d\n",stack[0]);

      }

    }

    }

    return 0;

    }
#include<iostream>
using namespace std;
int top = -1;
void push(string stack[],char value,int n){
    if(top==n-1){
        cout<<"overflow"<<endl;
        return;
    }
    top++;
    stack[top] = value;
}
int find_res(string stack[],int n){
    int open = 0;
    int close = 0;
    int res = 0;
    for(int i=0;i<n;i++){
        if(open==close && stack[i]== ">")
            return res;
        else if(stack[i]=="<"){
            open++;
        }
        else{
            close++;
            if(open==close)
                res = close*2;
        }
    }
    return res;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string stack[n];
        char value;
        for(int i=0;i<n;i++){
            cin>>value;
            push(stack,value,n);
       }
        int res = find_res(stack,n);
        cout<<res<<endl;
        top = -1;
    }
    return 0;
}
import java.util.*;
class solution{

  static int top = -1;

    public static void push(String stack[],char value,int n){
    if(top==n-1){
        System.out.println("overflow");
        return;
    }
    top++;
    stack[top] = Character.toString(value);
    }

    public static int find_res(String stack[],int n){
    int open = 0;
    int close = 0;
    int res = 0;
    for(int i=0;i<n;i++){
        if(open==close && stack[i]== ">")
            return res;
        else if(stack[i]=="<"){
            open++;
        }
        else{
            close++;
            if(open==close)
                res = close*2;
        }
    }
    return res;
    }

     public static void main (String[] args) {
       Scanner sc=new Scanner(System.in);
       int t=sc.nextInt();

       while(t-->0){
        int n=sc.nextInt();
        String stack[]=new String[n];
        char value;
        for(int i=0;i<n;i++){
            value=sc.next().charAt(0);
            push(stack,value,n);
       }
        int res = find_res(stack,n);
        System.out.println(res);
        top = -1;
    }
    }
}
Previous post Edge Divide(C, JAVA CODE NOT INCLUDED)
Next post Print first Non-repeating character in a string

Leave a Reply

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