Beautiful Bracket String

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 *