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

Stack

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.