i already mentioned the link where i got this approach..
//from spoj forum
I have tried this problem with the following approach:-
1. any expression can be expressed as ))...)+a_correct_expression+((...(
2.at each node i am storing 1.no_of ')' at start and 2.no_of '(' at end of
expression that the node is holding (ignoring the correct part)......
3.whenever u r merging two nodes to form its parent, it looks like
following:-
left_child[))...)((..(]++right_child[))..)((..(]
=))...)++((..())..)++((..(
=[))..)++))..)]++((..( OR, ))..)++[((..(++((..(]
i.e. comparing the no_of '(' in the left and no_of ')' in the right , u can
recalculate the no_of ')' and no_of '(' for the parent node)
4.for the leaf node, if the character is '(' =>no_of '('=1 and no_of ')'=0,
otherwise just the opposite case
5.finally, if the whole expression is correct , there will be 0,0 entry in
the root node, otherwise whole expression is not correct...
i guess it explains all.. :)
On Sat, Mar 26, 2011 at 6:32 PM, sukhmeet singh <[email protected]>wrote:
> Bharath can u tell me how u came with the combine function ??? I can't
> understand the logic behind it ... do reply
>
> On Wed, Mar 16, 2011 at 10:24 PM, Bharath 2009503507 CSE <
> [email protected]> wrote:
>
>> i am new to segment trees..i tried this problem in spoj..
>> http://www.spoj.pl/problems/BRCKTS
>> am getting WA..
>> pls help...
>>
>> code:
>>
>> #include<iostream>
>> #include<vector>
>> #include<cstdio>
>> #include<cmath>
>> #include<string>
>> using namespace std;
>> class pi
>> {
>> public:
>> int a,b;
>> pi() {a=0;b=0;}
>> pi(int x,int y) {a=x;b=y;}
>> };
>> vector<pi> tree;
>> string str;
>> pi combine(pi a,pi b)
>> {
>> pi x;
>> if(a.b==b.a)
>> {
>> x.a=a.a;
>> x.b=b.b;
>> }
>> else if(a.b > b.a)
>> {
>> x.a=a.a;
>> x.b=a.b-b.a+b.b;
>> }
>> else
>> {
>> x.b=b.b;
>> x.a=b.a-a.b+a.a;
>> }
>> return x;
>> }
>> void build(int node,int b,int e)
>> {
>> if(b==e)
>> {
>> if(str[b]=='(')
>> {
>> tree[node].a=0;
>> tree[node].b=1;
>> }
>> else
>> {
>> tree[node].a=1;
>> tree[node].b=0;
>> }
>> return;
>> }
>> // cout<<node<<"\n";
>> int mid=(b+e)/2;
>> build(node*2,b,mid);
>> build(node*2+1,mid+1,e);
>> tree[node]=combine(tree[node*2],tree[node*2+1]);
>> }
>> void update(int node,int b,int e,int index)
>> {
>> if(index < b || index >e) return;
>> if(b==e)
>> {
>> if(tree[node].a==1)
>> tree[node].a=0;
>> else
>> tree[node].a=1;
>> if(tree[node].b==1)
>> tree[node].b=0;
>> else
>> tree[node].b=1;
>> return;
>> }
>> int mid=(b+e)/2;
>> update(node*2,b,mid,index);
>> update(node*2+1,mid+1,e,index);
>> tree[node]=combine(tree[node*2],tree[node*2+1]);
>> }
>> main()
>> {
>> for(int test=1;test<=10;test++)
>> {
>> printf("Test %d:\n",test);
>> int n;
>> scanf("%d",&n);
>> if(!n) continue;
>> int size=(1<<(int(log10(n)/log10(2))+2));
>> // cout<<size<<"\n";
>> vector<pi> temp(size);
>> tree=temp;
>> temp.clear();
>> string s;
>> cin>>s;
>> str=s;
>> s.clear();
>> build(1,0,str.size()-1);
>> int x;
>> scanf("%d",&x);
>> while(x--)
>> {
>> int k;
>> scanf("%d",&k);
>> if(k==0)
>> {
>> if(!tree[1].a && !tree[1].b)
>> printf("Yes\n");
>> else
>> printf("No\n");
>> }
>> else
>> update(1,0,str.size()-1,k-1);
>> }
>> }
>>
>> }
>>
>> Thanks in advace..
>> Bharath..
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
