ANARCO9A HELP

editorial
1

Question - SPOJ.com - Problem ANARC09A

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    while(1){
    string a;
    cin>>a;
   // cout<<a<<endl;
    if(a[0]=='-')
    break;
    stack<int> s;
    for(int i = 0;a[i]!='\0';i++)
    {
        if(a[i]=='{')
        s.push(1);
        else 
        {
            if(s.size()==0)
            s.push(-1);
            else
            {
                if(s.top()==1)
                s.pop();
                else
                s.push(-1);
            }
                }


    }
    int right = 0,left = 0;
    while(!s.empty())
    {
        if(s.top()==1)
        right++;
        else
        left++;
        s.pop();
    }
    if(left == 0)
    cout<<right/2<<endl;
    else if(right == 0)
    cout<<left/2<<endl;
    else
    cout<<left+right<<endl;
   // cout<<endl;
    }
    return 0;
}

What’s my approach is

  1. Remove the “{}” like group in the string so we only have a string with unbalanced
  2. Count ‘{’ in the string and ‘}’ also
  3. If the string does not contain ‘{’ then answer is count of ‘}’/2 and vice- versa 4. If string contain both then answer is count of both… What is wrong in this approach
2

It fails on }}}{{{
but how to solve it using STACK

3

Finally!! I solve there is another way using stack!!! thanks

2 Likes
4

Can you share your stack AC solution?