Expression

ACCEPTED !! Another good one from Dhaka regionals 2006/07
____________________________________________________________________
Question: Expression
____________________________________________________________________

#include "iostream.h>
#include "stack"
using namespace std;

template 
void exchange(T *arr, int a, int b) {
   T temp = arr[a];
   arr[a] = arr[b];
   arr[b] = temp;
}

int main()
{
   int n;
   cin >> n;
   for(int i = 1; i <= n; i++) {
       char expr[200], digits[200];
       cin >> expr >> digits;
       int explen = strlen(expr);
       int dlen = strlen(digits);

       int signarr[dlen];
       int prod = 1, sign = 1;
       stack s;
       int index = 0;
       for(int j = 0; j < explen; j++) {
           if(expr[j] == '+') sign = 1;
           else if(expr[j] == '-') sign = -1;
           else if(expr[j] == '(') {
               prod *= sign;
               s.push(sign);
               sign = 1;
           }
           else if(expr[j] == ')') {
               prod *= s.top();
               s.pop();
           }
           else if(expr[j] == '#') signarr[index++] = prod * sign;
       }

       index--;
       int count = 0;
       int parr[dlen];
       for(int j = explen - 1; j >= 0; j--) {
           if(expr[j] == '#') {
               parr[index] = signarr[index] * ++count;
               index--;
           }
           else count = 0;
       }

       int indexarr[dlen];
       for(int j = 0; j < dlen; j++) indexarr[j] = j;

       int fordarr[dlen];
       for(int j = 0; j < dlen; j++) {
           int s1 = parr[j], x1 = j;
           int s2 = digits[j], x2 = j;
           for(int k = j+1 ; k < dlen; k++) {
               if(parr[k] < s1 || (parr[k] == s1 && indexarr[k] < indexarr[x1])) {
                   s1 = parr[k];
                   x1 = k;
               }
               if(digits[k] < s2) {
                   s2 = digits[k];
                   x2 = k;
               }
           }
           exchange(parr, j, x1);
           exchange(indexarr, j, x1);
           exchange(digits, j, x2);
           fordarr[indexarr[j]] = digits[j];
       }

       cout << "Case " << i << ":\n";

       index = 0;
       long long int sum = 0;
       for(int j = 0; j < explen; j++) {
           long long int val = 0;
           while(expr[j] == '#') {
               cout << char(fordarr[index]);
               int c = fordarr[index] - '0';
               val = val * 10 + signarr[index] * c;
               index++;
               j++;
           }
           if(j < explen) cout << expr[j];
           sum += val;
       }
       cout << endl;
       cout << sum << endl;
   }
   return 0;
}

____________________________________________________________________