#include <iostream>#include <cstdio>#include <cstring>#include <ctype.h>const int left(-1), right(-2);const int mul(-3), add_(-4), sub(-5);const int OP(-6);const int none(-10);char oDate[100];int fEx[100] = {0};int ans[100] = {0};int op[30] = {0};int fExNum(0);int iLeft(0);int apos(0), bpos(0), opos(0);int possible(0);void space();//跳过空格int bracket();//计算括号内int compute();//计算表达式void backtrack(int dep);//回溯void print( int *);//输出int main() { int iCase(0); while ( gets(oDate) && strchr( oDate, '=' ) ) { possible = 0; int i(0); for ( ; i != 90; ++i ) { fEx[i] = none; } apos = 0; sscanf(oDate, "%d", &iLeft); while ( oDate[apos] && isdigit(oDate[apos]) ){ ++apos; } space(); ++apos; fExNum = 0; opos = 0; while ( space(), oDate[apos] ) { if ( '(' == oDate[apos] ) { fEx[fExNum++] = left; ++apos; continue; } if ( ')' == oDate[apos] ) { fEx[fExNum++] = right; ++apos; } else { sscanf( oDate + apos, "%d", &fEx[fExNum++] ); while ( oDate[apos] && isdigit(oDate[apos]) ) { ++apos; } } space(); if ( oDate[apos] && oDate[apos] != ')' ) { op[opos++] = fExNum; fEx[fExNum++] = OP; } } backtrack(0); ++iCase; printf("Equation #%d:n", iCase); if ( 1 == fExNum && iLeft == fEx[0] ) { printf("%d=%dn", iLeft, iLeft); } else if ( 0 == fExNum || !possible ) { printf("Impossiblen"); } else { print(ans); printf("n"); } printf("n"); } return 0;}void space() { while ( oDate[apos] && (' ' == oDate[apos]) ) { ++apos; }}int bracket() { int sum(0); if ( left == fEx[bpos]) { ++bpos; sum = compute(); ++bpos; } else { sum = fEx[bpos++]; } return sum;}int compute() { int sum = bracket(); while ( mul == fEx[bpos] || add_ == fEx[bpos] || sub == fEx[bpos] ) { int operation(fEx[bpos++]); int ret(bracket()); switch ( operation ) { case mul: sum *= ret; break; case add_: sum += ret; break; case sub: sum -= ret; break; } } return sum;}void backtrack(int dep) { if ( possible ) { return ; } if ( opos == dep ) { bpos = 0; int iRight(compute()); if ( iRight == iLeft ) { possible = 1; int j(0); for ( ; j != fExNum; ++j ) { ans[j] = fEx[j]; } } return ; } fEx[op[dep]] = mul; backtrack(dep + 1); fEx[op[dep]] = add_; backtrack(dep + 1); fEx[op[dep]] = sub; backtrack(dep + 1);}void print( int *p ) { printf("%d=", iLeft); int k(0); for ( ; k != fExNum; ++k ){ switch(p[k]) { case add_: printf("+"); break; case mul : printf("*"); break; case sub : printf("-"); break; case left: printf("("); break; case right: printf(")"); break; case OP : printf("?"); break; default : printf("%d", p[k]); break; } }}
