当前位置：首页 - 正文

C++数据结构设计多项式运算有没有大神会做

发布网友发布时间：2023-07-13 05:40

共2个回答

热心网友时间：2024-11-04 17:23

#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <cmath>
#include <cctype>
using namespace std;
bool IsZero(double num){return fabs(num) < 0.0000001;}
class Polynomial
{
public:
    Polynomial();
    Polynomial(double coefs[], int exps[], int size);
    Polynomial(const Polynomial&);
    ~Polynomial();
    Polynomial& operator=(const Polynomial&);
    int degree() const;
    double evaluate(double x) const;
    Polynomial operator+(const Polynomial&) const;
    Polynomial operator-(const Polynomial&) const;
    Polynomial operator*(const Polynomial&) const;
    Polynomial& operator+=(const Polynomial&);
    Polynomial& operator-=(const Polynomial&);
    Polynomial& operator*=(const Polynomial&);
    ostream& doWrite(ostream&) const;
    int fromString(string&);
private:
    class Term{
    public:
        Term(double c, int e):coef(c), exp(e){}
        double coef;
        int exp;
    };
    list<Term> terms;
    void RemoveZeros();
};
ostream& operator<<(ostream& out, const Polynomial& poly)
{
    return poly.doWrite(out);
}
Polynomial::Polynomial()
{
    terms.push_back(Term(0, 0));
}
Polynomial::Polynomial(double coefs[], int exps[], int size)
{
    for(int i = 0; i < size; i++)
        terms.push_back(Term(coefs[i], exps[i]));
    if(size == 0)
        terms.push_back(Term(0, 0));
}
Polynomial::Polynomial(const Polynomial& poly)
{
    terms = poly.terms;
}
Polynomial::~Polynomial()
{
}
Polynomial& Polynomial::operator=(const Polynomial& poly)
{
    terms = poly.terms;
    return *this;
}
void Polynomial::RemoveZeros()
{
    list<Term>::iterator it;
    for(it = terms.begin(); it != terms.end();)
    {
        if(IsZero(it->coef))
            it = terms.erase(it);
        else
            ++it;
    }
    if(terms.empty())
    {
        terms.push_back(Term(0, 0));
    }
}
int Polynomial::degree() const
{
    return terms.front().exp;
}
double Polynomial::evaluate(double x) const
{
    double y = 0.0;
    list<Term>::const_iterator it;
    for(it = terms.begin(); it != terms.end(); it++)
    {
        y += it->coef * pow(x, it->exp);
    }
    return y;
}
Polynomial Polynomial::operator+(const Polynomial& b) const
{
    Polynomial c;
    list<Term>::const_iterator ai, bi;
    ai = this->terms.begin(), bi = b.terms.begin();
    while(ai != this->terms.end() && bi != b.terms.end())
    {
        if(ai->exp > bi->exp){
            c.terms.push_back(*ai);
            ai++;
        }
        else if(ai->exp < bi->exp){
            c.terms.push_back(*bi);
            bi++;
        }
        else{
            c.terms.push_back(Term(ai->coef + bi->coef, ai->exp));
            ai++, bi++;
        }
    }
    if(ai != this->terms.end())
    {
        for(; ai != this->terms.end(); ai++)
            c.terms.push_back(*ai);
    }
    else if(bi != b.terms.end())
    {
        for(; bi != this->terms.end(); bi++)
            c.terms.push_back(*bi);
    }
    c.RemoveZeros();
    return c;
}
Polynomial Polynomial::operator-(const Polynomial& b) const
{
    Polynomial c;
    list<Term>::const_iterator ai, bi;
    ai = this->terms.begin(), bi = b.terms.begin();
    while(ai != this->terms.end() && bi != b.terms.end())
    {
        if(ai->exp > bi->exp){
            c.terms.push_back(*ai);
            ai++;
        }
        else if(ai->exp < bi->exp){
            c.terms.push_back(Term(-bi->coef, bi->exp));
            bi++;
        }
        else{
            c.terms.push_back(Term(ai->coef - bi->coef, ai->exp));
            ai++, bi++;
        }
    }
    if(ai != this->terms.end())
    {
        for(; ai != this->terms.end(); ai++)
            c.terms.push_back(*ai);
    }
    else if(bi != b.terms.end())
    {
        for(; bi != this->terms.end(); bi++)
            c.terms.push_back(Term(-bi->coef, bi->exp));
    }
    c.RemoveZeros();
    return c;
}
Polynomial Polynomial::operator*(const Polynomial& b) const
{
    Polynomial c;
    list<Term>::const_iterator ai, bi;
    list<Term>::iterator ci;
    for(ai = this->terms.begin(); ai != this->terms.end(); ai++){
        for(bi = b.terms.begin(); bi != b.terms.end(); bi++){
            Term t(ai->coef * bi->coef, ai->exp + bi->exp);
            for(ci = c.terms.begin(); ci != c.terms.end();){
                if(t.exp > ci->exp)
                    ci++;
                else
                    break;
            }
            if(ci == c.terms.end())
                c.terms.push_back(t);
            else if(t.exp == ci->exp){
                ci->coef += t.coef;
            }
            else{
                c.terms.insert(ci, t);
            }
        }
    }
    c.terms.reverse();
    c.RemoveZeros();
    return c;
}
Polynomial& Polynomial::operator+=(const Polynomial& b)
{
    list<Term>::iterator ai;
    list<Term>::const_iterator bi;
    ai = this->terms.begin(), bi = b.terms.begin();
    while(ai != this->terms.end() && bi != b.terms.end())
    {
        if(ai->exp > bi->exp){
            ai++;
        }
        else if(ai->exp < bi->exp){
            this->terms.insert(ai, *bi);
            bi++;
        }
        else{
            ai->coef += bi->coef;
            ai++, bi++;
        }
    }
    if(bi != b.terms.end())
    {
        for(; bi != this->terms.end(); bi++)
            this->terms.push_back(*bi);
    }
    RemoveZeros();
    return *this;
}
Polynomial& Polynomial::operator-=(const Polynomial& b)
{
    list<Term>::iterator ai;
    list<Term>::const_iterator bi;
    ai = this->terms.begin(), bi = b.terms.begin();
    while(ai != this->terms.end() && bi != b.terms.end())
    {
        if(ai->exp > bi->exp){
            ai++;
        }
        else if(ai->exp < bi->exp){
            this->terms.insert(ai, *bi);
            bi++;
        }
        else{
            ai->coef -= bi->coef;
            ai++, bi++;
        }
    }
    if(bi != b.terms.end())
    {
        for(; bi != this->terms.end(); bi++)
            this->terms.push_back(*bi);
    }
    RemoveZeros();
    return *this;
}
Polynomial& Polynomial::operator*=(const Polynomial& b)
{
    *this = *this * b;
    return *this;
}
ostream& Polynomial::doWrite(ostream& out) const
{
    list<Term>::const_iterator it;
    if(terms.empty())
    {
        out << "0";
        return out;
    }
    for(it = terms.begin(); it != terms.end(); it++)
    {
        if(it != terms.begin() && it->coef > 0)
            out << "+";
        if(!IsZero(fabs(it->coef) - 1.0) || it->exp == 0)
            out << it->coef;
        if(IsZero(it->coef + 1.0) && it->exp != 0)
            out << "-";
        if(it->exp >= 1)
            out << "x";
        if(it->exp > 1)
            out << "^" << it->exp;
    }
    return out;
}
int Polynomial::fromString(string& str)
{
    const int ERR = -1, END = 0, NEWTERM = 1, COEFF = 2, XVAR = 3, POWOP = 4, EXP = 5;
    char ch;
    double a = 1.0;
    int b = 1, flag = 1;
    int state = NEWTERM;
    terms.clear();
    stringstream ss(str);
    while(ss.get(ch) && state != ERR)
    {
        if(isdigit(ch))
        {
            ss.putback(ch);
            if(state == NEWTERM){
                ss >> a;
                state = COEFF;
            }
            else if(state == POWOP){
                ss >> b;
                state = EXP;
            }
            else
                state = ERR;
        }
        else if(ch == '^')
        {
            if(state == XVAR)
                state = POWOP;
            else
                state = ERR;
        }
        else if(ch == 'x')
        {
            if(state == COEFF)
                state = XVAR;
            else if(state == NEWTERM)
                state = XVAR;
            else
                state = ERR;
        }
        else if(ch == '+' || ch == '-')
        {
            if(state == NEWTERM)
                state = NEWTERM;
            else if(state == COEFF){
                terms.push_back(Term(a * flag, 0));
                state = NEWTERM;
            }
            else if(state == XVAR){
                terms.push_back(Term(a * flag, 1));
                state = NEWTERM;
            }
            else if(state == EXP){
                terms.push_back(Term(a * flag, b));
                state = NEWTERM;
            }
            else
                state = ERR;
            if(ch == '-')
                flag = -1;
            else
                flag = 1;
        }
    }
    if(state == COEFF){
        terms.push_back(Term(a * flag, 0));
        state = END;
    }
    else if(state == XVAR){
        terms.push_back(Term(a * flag, 1));
        state = END;
    }
    else if(state == EXP){
        terms.push_back(Term(a * flag, b));
        state = END;
    }
    else
        state = ERR;
    if(state == END)
        RemoveZeros();
    return state;
}
int main()
{
    string cmd, line;
    int id = 1;
    double x = 0.0, y = 0.0;
    Polynomial a, b;
    while(getline(cin, cmd) && cmd != "last"){
        if(cmd == "evaluate"){
            cin >> x >> std::ws;
            getline(cin, line);
            a.fromString(line);
            y = a.evaluate(x);
            cout << id++ << ": " << y << endl;
        }
        else{
            getline(cin, line);
            a.fromString(line);
            while(getline(cin, line) && line.size() > 0 && line != "-1"){
                if(cmd == "add"){
                    b.fromString(line);
                    a += b;
                }
                else if(cmd == "subtract"){
                    b.fromString(line);
                    a -= b;
                }
                else if(cmd == "multiply"){
                    b.fromString(line);
                    a *= b;
                }
            }
            cout << id++ << ": " << a << endl;
        }
    }
}

程序在VC2005下编译并运行正常，其中乘法效率较低，可以进行改进；下面为测试用例：

add

x+1

2x^2+1

3x+4

-1

evaluate

7x^3+2x^2-10

add

2x^2+1

-2x^2-1

-1

add

2x^3-5x+2

-1

multiply

x^2+2x+1

-1

evaluate

x^6+6x^5+15x^4+20x^3+15x^2+6x+1

multiply
-x+1
-x+1
-x+1
-1

last

如果觉得没问题，请尽快采纳。

热心网友时间：2024-11-04 17:23

没问题很愿意帮你，私聊

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。
E-MAIL:11247931@qq.com

焦点

C++数据结构设计多项式运算有没有大神会做

最新推荐

猜你喜欢

热门推荐