Brackets matching using BIT

Question

edit: I was trying to solve a spoj problem. Here is the link to the problem : http://spoj.pl/problems/BRCKTS

I can think of two possible data structures for solving the problem one using segment tree and the other using a BIT. I have already implemented the solution using a segment tree. I have read about BIT but i can't figure out how to do a particular thing with it(which i have mentioned below)

I am trying to check if brackets are balanced in a given string containing only ('s or )'s. I am using a BIT(Binary indexed tree) for solving the problem. The procedure i am following is as follows:

I am taking an array of size equal to the number of characters in the string. I am assigning -1 for ) and 1 for ( to the corresponding array elements.

Brackets are balanced in the string only if the following two conditions are true.

The cumulative sum of the whole array is zero.
Minimum cumulative sum is non negative. i.e the minimum of cumulative sums of all the prefixes of the array is non-negative.

Checking condition 1 using a BIT is trivial. I am facing problem in checking condition 2.

There is a much easier solution that uses a stack. If this is homework and you are required to use a BIT, please tag it as such. — IVlad
– IVlad, Commented Feb 27, 2010 at 20:55
You can do this without a BIT by iterating over the string with a counter. Add 1 for every (, subtract 1 for ), check that the counter doesn't go below zero and check if it is equal to zero at the end. (Thanks Mad) — Otto Allmendinger
– Otto Allmendinger, Commented Feb 27, 2010 at 21:01
True that works, and can be derived from the stack solution: when you read a ), remove the topmost ( from the stack. If there is none, there's no solution. When you read a ( push it on the stack. At the end, the stack has to be empty. This can easily be extended to work if you can have [ and ] as well. — IVlad
– IVlad, Commented Feb 27, 2010 at 21:18
No its not a homework. I am trying solve of the problems with a Online judge. As per the problem statement, using a stack would surely make my solution run out of time. I have solved the problem using a segment tree. Can i post the link to the problem?? — amitkarmakar
– amitkarmakar, Commented Feb 28, 2010 at 5:05

IVlad · Accepted Answer · 2010-02-27 21:01:14Z

3

Here is a very good tutorial on Binary Indexed trees: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees and here is one that's more direct but less comprehensive: http://programmersdream.com/data-structure/binary-indexed-tree/

answered Feb 27, 2010 at 21:01

IVlad

43.6k13 gold badges115 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Brackets matching using BIT

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related