ACM: 126 - The Errant Physicist

給多項式，輸出x降冪y升冪排序後的多項式相乘結果。重點在於字串處理，要找到方法把輸入字串拆解出可以運算的係數及次方數。

TIPS

記得移除(不要輸出)合併同類項後係數為0的項

CODE

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

class term{
public:
  int coef; //coefficient
  int pow_x;
  int pow_y;
};

vector<term> poly[2], result;

void get_terms(int no, string s);
void multiply(term a, term b);
void sort_terms(int left, int right);
void comb_terms(void);
bool isbigger(int a, int b);
string atostring(int num);

int main(){
  int i, j, n;
  string s, line1, line2;
  
  while( cin >> s ){
    if( s[0] == '#' )
      break;
    
    get_terms(0, s);
    cin >> s;
    get_terms(1, s);
    
    result.clear();
    for(i=0; i<poly[1].size(); i++)
      for(j=0; j<poly[0].size(); j++)
        multiply(poly[1][i], poly[0][j]);
    
    sort_terms(0, result.size()-1); //sort
    comb_terms(); //combine like terms
    
    line1.clear();
    line2.clear();
    for(i=0; i<result.size(); i++){
      //sign
      if( i > 0 ){
        line1.append("   ");
        if( result[i].coef > 0 )
          line2.append(" + ");
        else
          line2.append(" - ");
      }
      //coefficient
      if( result[i].coef < 0 ){
        result[i].coef *= -1;
        if( i==0 ){
          line1.push_back(' ');
          line2.push_back('-');
        }
      }
      if( result[i].coef > 1 ){
        s = atostring(result[i].coef);
        line2.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line1.push_back(' ');
      }
      else if( result[i].coef == 1 && result[i].pow_x == 0 && result[i].pow_y == 0 ){
        line1.push_back(' ');
        line2.push_back('1');
      }
      //power of x
      if( result[i].pow_x >= 1 ){
        line1.push_back(' ');
        line2.push_back('x');
      }
      if( result[i].pow_x > 1 ){
        s = atostring(result[i].pow_x);
        line1.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line2.push_back(' ');
      }
      //power of y
      if( result[i].pow_y >= 1 ){
        line1.push_back(' ');
        line2.push_back('y');
      }
      if( result[i].pow_y > 1 ){
        s = atostring(result[i].pow_y);
        line1.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line2.push_back(' ');
      }
    }//i
    cout << line1 << endl << line2 << endl;
  }//while
  
  return 0;
}

void get_terms(int no, string s){
  poly[no].clear(); //initialize polynomial vector
  
  term temp;
  string number;
  int sign = 1;
  int size = s.size();
  char flag = '+';
  
  for(int i=0; i<=size; i++){
    if( i==0 || i == size || s[i] == '+' || s[i] == '-' ){
      //if end of term
      if( i > 0 ){
        if( flag == '+' || flag == '-' )
          temp.coef = atoi(number.c_str()) * sign;
        else if( flag == 'x' ){
          if( s[i-1] == 'x' )
            temp.pow_x = 1;
          else
            temp.pow_x = atoi(number.c_str());
        }
        else if( flag == 'y' ){
          if( s[i-1] == 'y' )
            temp.pow_y = 1;
          else
            temp.pow_y = atoi(number.c_str());
        }
        poly[no].push_back(temp);
      }
      //initialize term
      temp.coef = temp.pow_x = temp.pow_y = 0;
      sign = 1;
      flag = '+';
      number.clear();
      //new term
      if( i < size && s[i] == '-' ){
        sign = -1;
        flag = '-';
      }
    }//term break point
    
    if( s[i] == 'x' || s[i] == 'y' ){
      if( i == 0 )
        temp.coef = sign;
      else if( flag == '+' || flag == '-' ){
        if( s[i-1] == flag )
          temp.coef = sign;
        else
          temp.coef = atoi(number.c_str()) * sign;
      }
      else if( flag == 'x' ){
        if( s[i-1] == 'x' )
          temp.pow_x = 1;
        else
          temp.pow_x = atoi(number.c_str());
      }
      else if( flag == 'y' ){
        if( s[i-1] == 'y' )
          temp.pow_y = 1;
        else
          temp.pow_y = atoi(number.c_str());
      }
      flag = s[i];
      number.clear();
    }
    else if( s[i] >= '0' && s[i] <= '9' )
      number.push_back(s[i]);
  }//i
}

void multiply(term a, term b){
  term temp;
  temp.coef = a.coef * b.coef;
  temp.pow_x = a.pow_x + b.pow_x;
  temp.pow_y = a.pow_y + b.pow_y;
  result.push_back(temp);
}

void sort_terms(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    while(1){
      for(; i<=right && !isbigger(i, left); i++);
      for(; j>left && isbigger(j, left); j--);
      if( i >= j )
        break;
      swap(result[i], result[j]);
    }//while
    swap(result[j], result[left]);
    sort_terms(left, j-1);
    sort_terms(j+1, right);
  }
}

//return true when a>b, false when a<=b
bool isbigger(int a, int b){
  if( result[a].pow_x < result[b].pow_x )
    return true;
  if( result[a].pow_x > result[b].pow_x )
    return false;
  if( result[a].pow_y > result[b].pow_y )
    return true;
  return false;
}

void comb_terms(void){
  int i = 0;
  while( i < result.size() ){
    if( result[i].coef == 0 )
      result.erase(result.begin()+i);
    else if( i < (result.size()-1) && (result[i].pow_x == result[i+1].pow_x) && (result[i].pow_y == result[i+1].pow_y) ){
      result[i].coef += result[i+1].coef;
      result.erase(result.begin()+i+1);
    }
    else
      i++;
  }
}

string atostring(int num){
  stringstream ss;
  ss << num;
  return ss.str();
}