給多項式,輸出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(); }
No comments:
Post a Comment