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. 1Solving Approach:
This is very similar to the problem where we had to check where the given string of braces is balanced.
This question is just a modification of it.
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.
Once done with traversing the entire list, traverse the stack until it’s empty.
-
If the two topmost elements are same, add 1 to the counter ,for example – ({,{); (},}).
-
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.
-
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.