Andy's Blog

只是数据结构的作业而已，里面用了STL的set和list，放在这里主要是有高亮。
功能是计算两个多项式的和，输入格式是下x^3-6x^2+3这样最简单的字符串，不需要排序，也就是2+3-4+x^100-x^50这样的形式也是可以的。

/*
 * Language : c++
 * Compiler : Linux/gcc-g++ (GNU Compiler Chain)
 * Code by : Andy (Liu Yuxuan)
 * Date 2011-10-07
 */

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <list>
#include <string>
#include <set>
#include <fstream>

const int SORT_ORDER=1;
// 1 for ascending order
// 0 for descending order

struct monomial {
    int num;
    int exp;
} ;

int get_poly_numbers(std::string & str) {
    int _s=1;
    for (int i=0;i<str.length();i++) {
        if ((str[i] == '+') || (str[i] == '-')) _s++;
    }
    if ((str[0] == '+') || (str[0] == '-')) _s--;

    return _s;
}

void explict_opr_pos(std::string str,std::set<int> & _set) { // set '+' or '-' as seperator
    _set.clear();
    for (int i=0;i < str.length();i++) {
        if (!((str[0] == '+') || (str[0] == '-'))) _set.insert(0);
        if ((str[i] == '+') || (str[i] == '-')) _set.insert(i) ;
    }
}

int explict_num(std::string & poly_str) {
    using std::string;

    int num;

    int x_exist = 0,x_pos;
    for (int i=0;i<poly_str.length();i++) {
        if (poly_str[i] == 'x') {
            x_pos = i;
            x_exist = 1;
        }
    }

    if (x_exist) {
        string poly_num_str (poly_str.begin(),poly_str.begin()+x_pos);
        if ((poly_num_str.length() == 1) && (poly_num_str[0] == '+' || poly_num_str[0] == '-')) {
            if (poly_num_str[0] == '+') num = 1;
            if (poly_num_str[0] == '-') num = -1;
        }
        else {
            if (poly_num_str.length() == 0) num = 1;
            else num = atoi(poly_num_str.c_str());
        }
    }
    else {
        num = atoi(poly_str.c_str());
    }

    return num;
}

int explict_exp(std::string & poly_str) {
    using std::string;

    int exp,x_exist=0,exp_exist=0,exp_pos;
    for (int i=0;i<poly_str.length();i++) {
        if (poly_str[i] == 'x') x_exist=1;
        if (poly_str[i] == '^') {
            x_exist = 1;
            exp_exist = 1;
            exp_pos = i;
        }
    }

    if (x_exist == 0) exp=0;
    else if (exp_exist == 0) exp=1;
    else {
        string child (poly_str.begin()+exp_pos+1,poly_str.end());
        exp = atoi(child.c_str());
    }

    return exp;
}

void explict_str(std::string str,std::list<struct monomial> & poly_list,std::set<int> _set) {
    using std::set;
    using std::string;
    using std::list;

    poly_list.clear();
    set<int>::iterator set_it_begin,set_it_end;
    set_it_begin = _set.begin();
    set_it_end = ++set_it_begin;
    set_it_begin--;

    int num = get_poly_numbers(str);
    string::iterator str_begin_pos = str.begin();
    for (int i = 0;i<num-1;i++) {
        int begin_pos = *set_it_begin;
        int end_pos = *set_it_end;
        string child_str (str_begin_pos+begin_pos,str_begin_pos+end_pos);

        struct monomial mono;
        mono.exp = explict_exp(child_str);
        mono.num = explict_num(child_str);

        poly_list.insert(poly_list.begin(),mono);

        set_it_begin++;
        set_it_end++;
    }

    string child_str (str.begin()+*(set_it_begin),str.end());
    struct monomial mono;
    mono.exp = explict_exp(child_str);
    mono.num = explict_num(child_str);

    poly_list.insert(poly_list.begin(),mono);
}

void delete_zero_of_poly(std::list<struct monomial> & poly) {
    using std::list;
    list<struct monomial>::iterator _t;

    for (_t = poly.begin(); _t != poly.end(); _t++) {
        if (_t->num == 0) {
            poly.erase(_t);
            _t = poly.begin();
        }
    }
}

void add_poly_to_sum(std::list<struct monomial> & poly,std::list<struct monomial> & sum) {
    using std::list;

    int len = poly.size();
    for (int i=0;i<len;i++) {
        int _exp = (poly.begin())->exp;
        list<struct monomial>::iterator sum_t = sum.begin();
        while (_exp != sum_t->exp) sum_t++;
        sum_t->num += (poly.begin())->num;
        poly.erase(poly.begin());
    }
}

void output_poly(std::list<struct monomial> poly) {
    using std::list;
    using std::cout;

    cout << "n";
    if (poly.size() == 0) cout << "0";
    else {
        list<monomial>::iterator _t = poly.begin();
        for (int i=0;i<poly.size();i++)
        {
            int num = _t->num ;
            int exp = _t->exp ;

            if (i == 0) {
                if ((num == 1) && (exp > 0)) ;
                else if ((num == -1) && (exp > 0)) cout << "-";
                else cout << num;
            }
            else {
                if (num > 0) {
                    cout << "+";
                    if (num != 1) cout << num;
                }
                else /* num <0 */ {
                    cout << "-";
                    if (num != -1) cout << num;
                }
            }

            if (exp > 1) cout << "x^" << exp;
            else if (exp == 1) cout << "x";

            _t++;
        }
    }
    cout << "n";
}

int main(int argc, char **argv) {

    using namespace std;

    string str_1,str_2;
    int num_of_mono_1,num_of_mono_2;
    set <int> set_1,set_2; //store the positin of '+' or '-'
    set <int> exp_set; // store the exps
    set<int>::iterator set_t;
    list<string> p_str_1,p_str_2;
    list<struct monomial> polynomial_1,polynomial_2,polynomial_sum;
    list<struct monomial>::iterator _t;
    exp_set.clear();

    string choice;
    printf("Input from screen(s) or file(f)[s]:");
    getline(cin,choice);
    if (choice == "f") {
        string file_name;
        cout << "Input file name: ";
        getline(cin,file_name);
        ifstream fin;
        fin.open(file_name.c_str());
        getline(fin,str_1);
        getline(fin,str_2);
        fin.close();
    }
    else {
        cout << "Input the first polynomial of 'x':n";
        getline(cin,str_1);
        cout << "Input the second polynomial of 'x':n";
        getline(cin,str_2);
    }

    explict_opr_pos(str_1,set_1);
    explict_opr_pos(str_2,set_2);

    explict_str(str_1,polynomial_1,set_1);
    explict_str(str_2,polynomial_2,set_2);

    set_1.clear();  // num & exp have been already seperated.
    set_2.clear();  // clear the sets

    _t = polynomial_1.begin();
    for (int i=0;i<polynomial_1.size();i++) {
        exp_set.insert(_t->exp);
        _t++;
    }

    _t = polynomial_2.begin();
    for (int i=0;i<polynomial_2.size();i++) {
        exp_set.insert(_t->exp);
        _t++;
    }

    set_t = exp_set.begin();
    for (int i=0;i<exp_set.size();i++) {
        struct monomial _init_mono;
        _init_mono.exp = *(set_t++);
        _init_mono.num = 0;
        if (SORT_ORDER) polynomial_sum.insert(polynomial_sum.end(),_init_mono);
        else polynomial_sum.insert(polynomial_sum.begin(),_init_mono);
    }

    add_poly_to_sum(polynomial_1,polynomial_sum);
    add_poly_to_sum(polynomial_2,polynomial_sum);
    delete_zero_of_poly(polynomial_sum);
    output_poly(polynomial_sum);
    polynomial_sum.clear();

    return 0;
}