×

Search anything:

Make String Stable [using Stack]

Algorithms Stack

Indian Technical Authorship Contest starts on 1st July 2023. Stay tuned.

Given a string with opening and closing braces, our problem is to find the minimum number of operations to make the string stable. This can be solved efficiently using Stack. A string is stable based on the following rules:

• An empty string is stable.
• If S is stable, then {S} is also stable.
• If S and T are both stable, then the concatenation of S and T is stable (that is ST).
• All of these strings are stable: {}, {}{}, and {{}{}}
• These strings are not stable: }{, {{}{, nor {}{.

Two operations are allowed on the string:

• replace an opening brace with a closing brace
• replace an closing brace with a opening brace

This is the SPOJ Problem ANARC09A (Seinfeld).

Handling input

We are not given the number of test cases right infront of the input. Instead the input terminates with one or more '-' signs. To handle that we can use an infinite while loop and break out of it as soon as we get a '-' sign.

``````#include <bits/stdc++.h>
using namespace std;

int main() {
string S;
while(true) {
cin >> S;
if (S[0]=='-') break;
// main logic here
}
return 0;
}
``````

Handling Output

Also note that in output we need to print the line number corresponding to minimum number of operations. For that we can simply use a counter. We are storing operations in a variable named `op`.

``````#include <bits/stdc++.h>
using namespace std;

int main() {
string S;
int count = 1;
while(true) {
cin >> S;
if (S[0]=='-') break;
int op = 0;

// main logic here

cout << count++ << ". " << op << endl;
}
return 0;
}
``````

Notice how we are incrementing count by one each time while printing it on the same line.

Main Logic

We can iterate through the string use a stack to keep track of balanced expressions. Each time a `{` appears we push it to the stack and pop when a `}` appears.

If the stack is empty and a closing bracket appears, we can say that it is unbalanced (because there is no matching opening bracket corresponding to it) and convert it to an opening bracket.

Hence incrementing the number of operations (`op`) by one. We'll also need to push the push the converted bracket to the stack.

After completely iterating over the string we just convert half the remaining elements (`{`) of the stack into closing brackets and update `op` accordingly.

Notice that we are pushing only one type of entity in the stack (`{`). So instead we can just use a counter initially set to zero (empty condition). Incrementing it will denote pushing an element and decrementing will denote popping an element. Here we'll call our counter `bal` (short for balance). Here is the final code -

``````// Part of iq.OpenGenus.org
#include <bits/stdc++.h>
using namespace std;

int main()
{
string S;
int count = 1;
// While loop for taking input
while(true)
{
cin >> S;
if (S[0]=='-')
break;

// Main logic
int op = 0, bal = 0;
for (int i=0; i<S.size(); i++)
{
if(S[i]=='{')
bal++;
else
bal--;
if (bal<0)
{
op++;
bal += 2;
}
}
op += bal/2;
cout << count++ << ". " << op << endl;
}
return 0;
}
``````

Time & Space complexity

The time complexity is O(N)
The space complexity is O(1)

where

• N is the number of characters in the input string.

Note that the problem is tagged under dynamic programming on SPOJ. Do comment under this article if you want to share that approach. And check out our other articles on C++ STL and algorithms to get better ar problem solving. You can also implement the above logic in python as a fun exercise.

With this article at OpenGenus, you must have the complete idea of how to find the minimum number of operations to make a string stable.