poj 1100 Dreisam Equations

poj 1100 Dreisam Equations

#include <iostream>#include <stdio.h>#include <sstream>#include <string.h>#include <vector>using namespace std;#define NIL        (unsigned)-1#define MAX        12typedef vector <int> VI;typedef unsigned int UI;int cas, N, F;int equ, tmp_num[MAX], UFS[MAX];VI num, prio, pos, opr, v0, v1;string expr;stringstream ss;char opr_sign[3] ={ '+', '-', '*' };int (*opr_f[3])(int a, int b);int inline add(int a, int b){    return a+b;}int inline sub(int a, int b){    return a-b;}int inline mul(int a, int b){    return a*b;}class Disjoint{   public:       int parent[12];       Disjoint()       {for (int i = 0; i < 12; parent[ i ] = i, i++)    ;       }       int Find(int x)       {if (parent[x] == x)    return x;else    parent[x] = Find(parent[x]);return parent[x];       }       void inline Union(int a, int b)       {parent[Find(b)] = Find(a);       }};int inline cast(string s){       int tmp;       ss.clear();       ss << s;       ss >> tmp;       return tmp;}string fix(string s){       int eq, sign;       eq = s.find('=', 0);     if (s[eq+1] != ' ')         s.insert(s.begin()+eq+1, ' ');    if (s[eq-1] != ' ')        s.insert(s.begin()+eq, ' ');    while ((sign = s.find(")(", 0)) != -1)         s.insert(s.begin()+sign+1, ' ');    while ((sign = s.find("( ", 0)) != -1)        s.erase(sign+1, 1);     while ((sign = s.find(" )", 0)) != -1)         s.erase(sign, 1);     s.insert(s.begin()+s.length(), ' ');   for (UI i = s.find('=', 0); i < s.length(); i++)     {        if (s[ i ] == '(') if (s[i-1] != ' ' && s[i-1] != '(')    s.insert(s.begin()+i, ' ');       if (s[ i ] == ')')if (s[i+1] != ' ' && s[i+1] != ')')     s.insert(s.begin()+i+1, ' '), i++;     }     s.erase(s.length()-1);    for (UI i = 1; i < s.length(); i++)        if (s[i-1] == ' ' && s[ i ] == ' ')s.erase(i, 1), i--;    return s;}int expression_r(string s) {   string tmp;  int blank, lastblank, p, pp;    int lp, rp;     Disjoint ufs;    num.clear();     prio.clear();      pos.clear();     opr.clear();     v0.clear();     v1.clear();    lp = rp = 0;     s = fix(s);    blank = s.find(' ', 0);     tmp = s.substr(0, blank);    equ = cast(tmp);    blank = s.find(' ', blank+1);     expr = s = s.substr(blank+1, s.length()-blank-1);     blank = -1;    do    {        lastblank = s.find(' ', blank+1);         tmp = s.substr(blank+1, (lastblank == -1 ? s.length() : lastblank)      -blank);         blank = lastblank;        pos.push_back(blank);         while (tmp.find('(', 0) != NIL)  tmp.erase(0, 1);         while (tmp.find(')', 0) != NIL)   tmp.erase(tmp.length()-1, 1);       num.push_back(cast(tmp));     } while (blank != -1);     for (UI i = 0, p = 0; i < s.length(); i++)    {        if (s[ i ] == '(') p++, lp++;         else if (s[ i ] == ')') p--, rp++;         else if (s[ i ] == ' ')  prio.push_back(p);    }     while (p != -1)     {        p = -1, pp = 0;         for (UI i = 0; i < prio.size(); i++) if (prio[ i ]> p)     p = prio[ i ], pp = i;         if (p == -1) break;         for (UI i = pp; i < prio.size(); i++)  if (prio[ i ] == p)     v0.push_back(i), prio[ i ] = -1;  else      break;     }    for (UI i = 0; i < v0.size(); i++)    {       v1.push_back(ufs.Find(v0[ i ]));        v1.push_back(ufs.Find(v0[ i ]+1));        ufs.Union(v0[ i ], v0[ i ]+1);     }    for (UI i = 0; i < prio.size(); i++)         opr.push_back(0);    if (lp != rp)          return 0;     return num.size(); } int check() {     int a, b;     for (int i = 0; i < N; i++)        tmp_num[ i ] = num[ i ];    for (int i = 0; i < N - 1; i++)     {        a = v1[i*2], b = v1[i*2+1];         tmp_num[a] = (*opr_f[opr[v0[ i ]]])(tmp_num[a], tmp_num[b]);    }    return tmp_num[0]; } void print(string s) {    cout << equ <<'=';    for (int i = 0; i < N - 1; i++)         s[pos[ i ]] = opr_sign[opr[ i ]];     cout << s << endl;} void dfs(int k){     if (F)         return;     if (k == N - 1)    {         if (check() == equ)  print(expr), F = 1;        return;    }     for (int i = 0; i < 3; i++)     {        opr[k] = i;        dfs(k+1);     }}int main(){     opr_f[0] = add;     opr_f[1] = sub;     opr_f[2] = mul;     cas = 1;     while (getline(cin, expr) && expr != "0")     {         N = expression_r(expr);         printf("Equation #%d:n", cas++);         if (N == 1)         { if (equ == num[0])      print(expr); else      cout << "Impossible" << endl;        }        else        {F = 0;  dfs(0);if (!F)     cout << "Impossible" << endl;         }        cout << endl;    }     return 0; }