Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Beautiful Bracket String

Last Updated on December 13, 2022 by Prepbytes

Concepts Used:

Stack

Difficulty Level:

Medium.

Problem Statement :

Find the minimum number of replacements required to make the given string of braces balanced.

See original problem statement here

Example:

Input:
}{
{}{}{}
{{{}

Output:
1. 2
2. 0
3. 1

Solving Approach:

  1. This is very similar to the problem where we had to check where the given string of braces is balanced.

  2. This question is just a modification of it.

  3. Unlike that problem,here you have to push the closing brace ‘}’ also to the stack if the top of the stack of the stack already contains a closing brace.

  4. Once done with traversing the entire list, traverse the stack until it’s empty.

  1. If the two topmost elements are same, add 1 to the counter ,for example – ({,{); (},}).

  2. If the two topmost elements are different, add 2 to the counter if the combination is {,}. because this gives an unbalanced string and both the braces need to be replaced.

  3. If the two topmost elements are different, add 0 to the counter if the combination is },{ because it is already balanced.

Solutions:

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
int get(char a,char b){
    if(a == b)
        return 1;
    if(a == '{' && b == '}')
        return 2;
    return 0;
    }
    int main(int argc, char const *argv[])
    {
    char s[100005];
    int c, k = 1;
    while(1)
    {
        scanf("%s",s);

        if(s[0] == '-')
            return 0;

        printf("%d. ",k++);
        c = 0;
        char ch;
    int n=strlen(s);
        char stack[100005];int top=-1;

        for(int i = 0; i < n; i++)
        {
            if(top==-1 || s[i] == '{')
                stack[++top]=s[i];
            else
            {
                if( stack[top] == '{' )
                    top--;
                else
                    stack[++top]=s[i];
            }
        }

        while(top!=-1)
        {
            ch = stack[top];
            top--;
            c += get(ch, stack[top]);   
            top--;
        }
        printf("%d\n",c);
    }
    return 0;
}
#include <bits stdc++.h="">
using namespace std;
int get(char a,char b){
    if(a == b)
        return 1;
    if(a == '{' and b == '}')
        return 2;
    return 0;
}
int main(int argc, char const *argv[]){
    string s;
    int c, k = 1;
    while(1)
    {
        cin>>s;

        if(s[0] == '-')
            return 0;

        cout<<k++<<". ";="" c="0;" char="" ch;="" stack<char=""> q;

        for(int i = 0; i < s.length(); i++)
        {
            if(q.empty() || s[i] == '{')
                q.push(s[i]);
            else
            {
                if( q.top() == '{' )
                    q.pop();
                else
                    q.push(s[i]);
            }
        }

        while(!q.empty())
        {
            ch = q.top();
            q.pop();
            c += get(ch, q.top());  
            q.pop();
        }
        cout<<c<<endl; 

}
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);

              int j=1;

    while( j>0){

          String str=sc.next();
          if(str.charAt(0)=='-'){
          break;
          }
          else{
         System.out.print(j+". ");

          beauty_Bracket(str);

          }
          j++; 
          System.out.println("");
    }
    }

    static void beauty_Bracket(String str){
        int count=0;  
       Stack<Character> stk = new Stack<>();
       int n= str.length();
      for(int i=0;i<n;i++)
      {
          if(str.charAt(i)=='{'){
              stk.push(str.charAt(i));
          }
          else if(str.charAt(i)=='}'){
              if(!stk.empty())
              stk.pop();

              else{
              count++;
              stk.push('{');
              }
          }
      }
     if(stk.size()!=0)
        {
            count+=stk.size()/2;
        }

    System.out.print(count);

     }
}
# your code goes here
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    st = []
    ans = 0

    for i in range(n - 1, -1, -1):

        while len(st) and st[-1][0] >= a[i]:
            st.pop()

        if len(st):
            ans = (ans + (st[-1][1] - i + 1)) % 1000000007

        st.append([a[i], i])

    print(ans)

[forminator_quiz id="1860"]

This article tried to discuss Stack. Hope this blog helps you understand and solve the problem. To practice more problems on Stack you can check out MYCODE | Competitive Programming.

Leave a Reply

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