View Code of Problem 229

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[100];
int b[100],op[30],xans[100];
int bn,ans,apos,opos,bpos;
bool po;
void space()
{
    while(a[apos]==' ') apos++;
}
int compute();
int bracket()
{
    int sum;
    if(b[bpos]==-1)
    {
        bpos++;
        sum=compute();
        bpos++;
    }
    else sum=b[bpos++];
    return sum;
}
int compute()
{
    int sum=bracket();
    while(b[bpos]==-3||b[bpos]==-4||b[bpos]==-5)
    {
        int fuhao=b[bpos++];
        int ret=bracket();
        switch(fuhao)
        {
            case -3:sum*=ret;break;
            case -4:sum+=ret;break;
            case -5:sum-=ret;break;
        }
    }
    return sum;
}
void backtrack(int dep)
{
    if(po) return;
    if(dep==opos)
    {
        bpos=0;
        int iright=compute();
        if(iright==ans)
        {
            po=true;
            for(int i=0;i<bn;i++) xans[i]=b[i];
        }
        return;
    }
    b[op[dep]]=-4;backtrack(dep+1);
    b[op[dep]]=-5;backtrack(dep+1);
    b[op[dep]]=-3;backtrack(dep+1);
}
int main()
{
    int t=0;
    while(gets(a)&&strchr(a,'='))
    {
        t++;
        po=false;
        for(int i=0;i<90;i++)
            b[i]=-10;
        apos=0;
        sscanf(a,"%d",&ans);
        while(a[apos]&&isdigit(a[apos])) apos++;
        space();
        apos++;
        bn=0;
        opos=0;
        while(space(),a[apos])
        {
            if(a[apos]=='(')
            {
                b[bn++]=-1;
                apos++;
                continue;
            }
            if(a[apos]==')')
            {
                b[bn++]=-2;
                apos++;
            }
            else
            {
                sscanf(a+apos,"%d",&b[bn++]);
                while(a[apos]&&isdigit(a[apos])) apos++;
            }
            space();
            if(a[apos]&&a[apos]!=')')
            {
                op[opos++]=bn;
                b[bn++]=-6;
            }
        }
        backtrack(0);
        cout<<"Equation #"<<t<<":"<<endl;
        if(!po) cout<<"Impossible"<<endl;
        else
        {
            cout<<ans<<"=";
            for(int i=0;i<bn;i++)
            {
                switch(xans[i])
                {
                    case -1:cout<<"(";break;
                    case -2:cout<<")";break;
                    case -3:cout<<"*";break;
                    case -4:cout<<"+";break;
                    case -5:cout<<"-";break;
                    default:cout<<xans[i];
                }
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}