CODEWITHSUNDEEP
stringalgorithmdata-structuressegment-treerange-query
Prashant Bhanarkar
Prashant Bhanarkar

Reputation: 960

check if string of parenthesis is balanced by doing certain operation on string

Given string of parenthesis we have to do 2 kinds of operation:

  1. flip- changes the i-th parenthesis into the opposite one(left->right , right->left)
  2. check- if the string is a balanced parenthesis expression

length of the string is at max 30000.

No of operation to be performed is at max 100000.

what kind of data structure should one use to solve this kind of problem?

Is Segment Tree a suitable data structure?

If yes how should one use it?

Example

string = ()((

no of operation=4

  1. flip 4 {new string is ()()}
  2. check {string is balanced}
  3. flip 2{new string becomes ((()}
  4. check{string is not balanced}

Upvotes: 1

Views: 728

Answers (2)

user2512323
user2512323

Reputation:

Let every ( be a +1 and every ) be a -1. Then a string of parenthesis is balanced iff sum for entire string is zero and sum for every range [0, k] is non-negative.

Let us define two functions for substring [i,j], sum and min. sum is obvious, and min(i,j) defined as minimum from all sum(i,k) where k <= j.

So

sum(i,k) = sum(i,j) + sum(j+1, k)

And

min(i,k) = MIN( min(i,j), sum(i,j) + min(j + 1, k) )

Now we can build a binary tree, where leafs are +1's and -1's, and root is an entire range [0, N-1]. For every node we keep min and sum.

Query for balance is obvious: we check for root.min >= 0 and root.sum == 0, so O(1).

Flip is done by updating leaf node and propagating changes to the root. No more than log(N)+1 nodes are updated, and every update is O(1), so O(logN).

Upvotes: 1

user2464424
user2464424

Reputation: 1616

A function that checks whether a string is balanced is easily made. Stepping through the string, increment a zero-initialized value if a "(" character is met and decrement it if ")" is met. If the result is 0 and it never went below 0 during the run, the string is balanced. Flipping the parenthesis at nth position of the string is trivial.

Here's a simple implementation in javascript that flips a random character of the string in a loop and checks the validity of the resulting string after each flip.

http://jsbin.com/vagalijoca/edit?html,console

function checkbalanceness(str){
  var res = 0;
  for(i=0;i<str.length;i++) {
    str[i]=="(" ? res++ : res--;
    if (res < 0) break;
  }
  return res == 0;
}

function flipp(str, i){
  if (i >= str.length) return str;
  return str[i]=="(" ?
    str.substr(0,i) + ")" + str.substr(i+1) :
    str.substr(0,i) + "(" + str.substr(i+1) ;
}

//initial string
var curr = "()(())";
//operations to be executed
var ops = 40;

console.log('initial string: ' + curr + ' ' + checkbalanceness(curr));
console.log('operations: ' + ops);
console.log('start');
var ii;
var chartoflip;
for(ii=0;ii<ops;ii+=2){
  chartoflip = (ii/2)%(curr.length);
  curr = flipp(curr, chartoflip);
  console.log((ii) + ' - flip char ' + chartoflip + ': ' + curr);
  console.log((ii+1) + ' - checking ' + curr + ' ' + checkbalanceness(curr));
}
console.log('end');

Upvotes: 0

Related Questions