Last Updated on March 21, 2022 by Ria Pathak
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:
- Every time we encounter a ‘<‘, we push it onto the stack and increment open counter. according to fundamentals of data structures in c++.
- For every ‘>’ encountered, we pop a ‘<‘ from the stack and increment close counter.
- 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;
}
}
}
# your code goes here
def find_res(stack, n):
open, close, res = 0, 0, 0
for i in range(n):
if open == close and stack[i] == ">":
return res
elif stack[i] == "<":
open += 1
else:
close += 1
if open == close:
res = close * 2
return res
for _ in range(int(input())):
n = int(input())
stack = [0 for i in range(n)]
s = input()
for i in range(n):
value = s[i]
stack[i] = value
res = find_res(stack, n)
print(res)
[forminator_quiz id=”1868″]
So, in this blog, we have tried to explain the concept of stacks. If you want to solve more questions on Stacks, which are curated by our expert mentors at PrepBytes, you can follow this link stacks.