v 0. Pasted by slipstak2 as cpp at 2011-01-17 21:15:32 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 15.
  2. // 15F. Умножение многочленов [polymul]
  3. // ibelyaev: 17Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <string>
  9.  
  10. using namespace std;
  11. const int MAX_POW = 10 * 2 + 5;
  12.  
  13. typedef long long i64;
  14. typedef vector<i64> polynom;
  15.  
  16. void SkipSeps(char* &pos) {
  17.     while (*pos == ' ')
  18.         pos++;
  19. }
  20. bool isEnd(char* &pos) {
  21.     SkipSeps(pos);
  22.     return pos == 0;
  23. }
  24. bool isPlusOrMinus(const char* pos) {
  25.     return *pos == '+' || *pos =='-';
  26. }
  27. bool isDigit(char p) {
  28.     return '0' <= p && p <='9';
  29. }
  30. void ReadNumber(char * &pos, int &num) {
  31.     if (isEnd(pos)) return;
  32.     while (!isEnd(pos) && isDigit(*pos)) {
  33.         num = num*10 + *pos - '0';
  34.         pos++;
  35.     }
  36. }
  37. void ReadPower(char* &pos, int &pow) {
  38.     // <Степень> ::= "^"<Число>
  39.     if (isEnd(pos)) return;
  40.     if (*pos!='^') {
  41.         pow = 1;
  42.         return;
  43.     }else {
  44.         pos++;
  45.         pow = 0;
  46.         ReadNumber(pos, pow);
  47.     }
  48. }
  49. void ReadKoef(char* &pos, int &k) {
  50.     // <Коэффициент> ::= ("+" | "-")<Число>
  51.     if (isEnd(pos)) return;
  52.  
  53.     bool isNeg = false;
  54.     if (isPlusOrMinus(pos)){
  55.         isNeg = *pos == '-';
  56.         pos++;
  57.     }
  58.     if (isDigit(*pos)) {
  59.         k = 0;
  60.         ReadNumber(pos, k);
  61.     }
  62.     else
  63.         k = 1;
  64.     k *= isNeg ? -1 : 1;
  65. }
  66. void ReadMonomial(char* &pos, int &k, int &pow) {
  67.     if (isEnd(pos)) return;
  68.     // <Одночлен> ::= {<Коэффициент>}x{<Степень>}
  69.     ReadKoef(pos,k);
  70.     if (*pos == 'x') {
  71.         pos++; // x;
  72.         ReadPower(pos,pow);
  73.     }
  74.     else
  75.         pow = 0;
  76. }
  77. void ReadPolynom(char* &pos, polynom &p) {
  78.  // <Многочлен> ::= <Одночлен> {("+"|"-") <Одночлен>}
  79.     do
  80.     {
  81.         int k, pow;
  82.         ReadMonomial(pos, k, pow);
  83.         p[pow] += k;
  84.  
  85.     } while (!isEnd(pos) && isPlusOrMinus(pos));
  86.  
  87. }
  88. void input(polynom &a, polynom &b) {
  89.     string str;
  90.     cin>>str;
  91.     char *buf = (char*)str.c_str();
  92.     ReadPolynom(buf,a);
  93.    
  94.     cin>>str;
  95.     buf = (char*)str.c_str();
  96.     ReadPolynom(buf,b);
  97.  
  98. }
  99. void mul(const polynom &a, const polynom &b, polynom &res) {
  100.     for (int i=0; i < MAX_POW; i++) {
  101.         for (int j=0; j<MAX_POW; j++) {
  102.             if (i+j < MAX_POW)
  103.                 res[i+j] += a[i] * b[j];
  104.         }
  105.     }
  106. }
  107. void output (const polynom &p) {
  108.     bool isEmpty = true;
  109.     for (int i=0;i<p.size();i++) isEmpty &= !p[i];
  110.     if (isEmpty) {
  111.         cout<<0;
  112.         return;
  113.     }
  114.     bool isFirst = true;
  115.     for (int i=MAX_POW-1;i>=0;i--) {
  116.         if (p[i]) {
  117.             if (!isFirst && p[i] > 0) cout<<"+";
  118.  
  119.             if (i == 0) {
  120.                 cout<<p[i];
  121.             }else {
  122.                 if (p[i] == -1)
  123.                     cout<<"-";
  124.                 else if (p[i] != 1)
  125.                     cout<<p[i];
  126.             }
  127.  
  128.             if (i != 0)
  129.                 cout<<"x";
  130.             if (i > 1)
  131.                 cout<<"^"<<i;
  132.  
  133.             if (isFirst) isFirst = !isFirst;
  134.         }
  135.     }
  136. }
  137. int main() {
  138.     freopen("input.txt","r",stdin);
  139.     freopen("output.txt","w",stdout);
  140.  
  141.     polynom a(MAX_POW), b(MAX_POW), res(MAX_POW);
  142.     input(a,b);
  143.     mul(a,b,res);
  144.     output(res);
  145.     return 0;
  146. }


Editing is locked.