C++ program to add two polynomials in forms like "4x^3+3x^2+2x+1"

PolyAdder.cc

#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <utility>

template <typename T>
class List {

    struct Node {

        T       data;
        Node*   next;

        Node(T const& data, Node* next) : data(data), next(next) {
        }

    };

    Node*       _front  = nullptr;
    Node*       _back   = nullptr;
    size_t      _size   = 0;

public:

    class Iterator {

        Node*   node;

    public:

        Iterator(Node* node) : node(node) {
        }

        T& operator * () {
            return node->data;
        }

        T* operator -> () {
            return &node->data;
        }

        Iterator& operator ++ () {
            node = node->next;
            return *this;
        }

        bool operator != (Iterator const& rhs) const {
            return node != rhs.node;
        }

    };

    class ConstIterator {

        Node const*     node;

    public:

        ConstIterator(Node const* node) : node(node) {
        }

        T const& operator * () {
            return node->data;
        }

        T const* operator -> () {
            return &node->data;
        }

        ConstIterator& operator ++ () {
            node = node->next;
            return *this;
        }

        bool operator != (ConstIterator const& rhs) const {
            return node != rhs.node;
        }

    };

    class UnderflowError : public std::runtime_error {
    
    public:

        UnderflowError() : std::runtime_error("underflow error") {
        }

    };

    List() {
    }

    ~List() {
        while(size() != 0) {
            popFront();
        }
    }

    List& pushFront(T const& x) {
        Node* node = new Node(x, _front);
        if(size() == 0) {
            _front = _back = node;
        } else {
            _front = node;
        }
        ++_size;
        return *this;
    }

    List& pushBack(T const& x) {
        Node* node = new Node(x, nullptr);
        if(size() == 0) {
            _front = _back = node;
        } else {
            _back->next = node;
            _back = node;
        }
        ++_size;
        return *this;
    }

    List& sortedInsert(T const& x, bool reversed = false) {
        pushFront(x);
        Node* node = _front;
        while(node->next && (!(node->next->data == node->data) && (node->next->data < node->data) != reversed)) {
            std::swap(node->data, node->next->data);
            node = node->next;
        }
        if(node->next && node->next->data == node->data) {
            Node* p = node->next;
            node->data += p->data;
            node->next = p->next;
            delete p;
            --_size;
        }
        return *this;
    }

    T popFront() {
        if(size() == 0) {
            throw UnderflowError();
        }
        Node* p = _front;
        _front = p->next;
        T result(p->data);
        delete p;
        --_size;
        if(size() == 0) {
            _back = nullptr;
        }
        return result;
    }

    Iterator begin() {
        if(size() == 0) {
            throw UnderflowError();
        }
        return Iterator(_front);
    }

    Iterator const& end() {
        static const Iterator _end(nullptr);
        return _end;
    }

    ConstIterator cbegin() const {
        if(size() == 0) {
            throw UnderflowError();
        }
        return ConstIterator(_front);
    }

    ConstIterator const& cend() const {
        static const ConstIterator _cend(nullptr);
        return _cend;
    }

    size_t size() const {
        return _size;
    }

};

struct Item {

    double  coeff;
    int     expon;

    Item(double coeff, int expon) : coeff(coeff), expon(expon) {
    }

    bool operator == (Item const& rhs) const {
        return expon == rhs.expon;
    }

    bool operator < (Item const& rhs) const {
        return expon < rhs.expon;
    }

    Item& operator += (Item const& rhs) {
        assert(expon == rhs.expon);
        coeff += rhs.coeff;
        return *this;
    }

};

class Poly : public List<Item> {

private:

    static int parseInt(std::string const& str, size_t ptr_err) {
        if(!str.empty()) {
            char const* c_str = str.c_str();
            char* endptr;
            long result = std::strtol(c_str, &endptr, 10);
            if(endptr == &c_str[str.length()]) {
                return (int) result;
            }
        }
        throw SyntaxError(ptr_err - str.length());
    }

    static double parseDouble(std::string const& str, size_t ptr_err) {
        if(!str.empty()) {
            char const* c_str = str.c_str();
            char* endptr;
            double result = std::strtod(c_str, &endptr);
            if(endptr == &c_str[str.length()]) {
                return result;
            }
        }
        throw SyntaxError(ptr_err - str.length());
    }

public:

    class SyntaxError : public std::runtime_error {

    private:

        size_t ptr_err;

    public:

        SyntaxError(size_t ptr_err) : std::runtime_error("syntax error"), ptr_err(ptr_err) {
        }

        void report(size_t padding = 0) const {
            for(size_t i = 0; i < padding; ++i) {
                std::cerr << ' ';
            }
            for(size_t i = 0; i < ptr_err; ++i) {
                std::cerr << '~';
            }
            std::cerr << "^ syntax error" << std::endl;
        }

    };

    Poly &parse(std::string const& expr) {
        enum State {
            ST_INIT, ST_SIGN, ST_COEFF, ST_STAR, ST_X, ST_CARET, ST_EXPON
        } state = ST_INIT;
        std::string coeff_str;
        std::string expon_str;
        double sign;
        double coeff;
        double expon;

        for(size_t ptr_err = 0; ; ++ptr_err) {
            char c = expr[ptr_err];
            if(c == ' ') {
                continue;
            }
            switch(state) {
            case ST_INIT:
                if((c >= '0' && c <= '9') || c == '.') {
                    coeff_str = c;
                    sign = 1;
                    state = ST_COEFF;
                } else if(c == '+') {
                    sign = 1;
                    state = ST_SIGN;
                } else if(c == '-') {
                    sign = -1;
                    state = ST_SIGN;
                } else if(c == 'x') {
                    coeff_str = "1";
                    sign = 1;
                    state = ST_X;
                } else {
                    throw SyntaxError(ptr_err);
                }
                break;
            case ST_SIGN:
                if((c >= '0' && c <= '9') || c == '.') {
                    coeff_str = c;
                    state = ST_COEFF;
                } else if(c == 'x') {
                    coeff_str = "1";
                    state = ST_X;
                } else {
                    throw SyntaxError(ptr_err);
                }
                break;
            case ST_COEFF:
                if(c == '\0') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    sortedInsert(Item(sign * coeff, 0), true);
                    return *this;
                } else if((c >= '0' && c <= '9') || c == '.') {
                    coeff_str += c;
                } else if(c == '+') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    sortedInsert(Item(sign * coeff, 0), true);
                    coeff_str.clear();
                    sign = 1;
                    state = ST_SIGN;
                } else if(c == '-') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    sortedInsert(Item(sign * coeff, 0), true);
                    coeff_str.clear();
                    sign = -1;
                    state = ST_SIGN;
                } else if(c == '*') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    state = ST_STAR;
                } else if(c == 'x') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    state = ST_X;
                } else {
                    throw SyntaxError(ptr_err);
                }
                break;
            case ST_STAR:
                if(c == 'x') {
                    state = ST_X;
                } else {
                    throw SyntaxError(ptr_err);
                }
                break;
            case ST_X:
                if(c == '\0') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    sortedInsert(Item(sign * coeff, 1), true);
                    return *this;
                } if(c == '+') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    sortedInsert(Item(sign * coeff, 1), true);
                    coeff_str.clear();
                    sign = 1;
                    state = ST_SIGN;
                } else if(c == '-') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    sortedInsert(Item(sign * coeff, 1), true);
                    coeff_str.clear();
                    sign = -1;
                    state = ST_SIGN;
                } else if(c == '^') {
                    coeff = parseDouble(coeff_str, ptr_err);
                    state = ST_CARET;
                } else {
                    throw SyntaxError(ptr_err);
                }
                break;
            case ST_CARET:
                if((c >= '0' && c <= '9') || c == '-') {
                    expon_str = c;
                    state = ST_EXPON;
                } else {
                    throw SyntaxError(ptr_err);
                }
                break;
            case ST_EXPON:
                if(c == '\0') {
                    expon = parseInt(expon_str, ptr_err);
                    sortedInsert(Item(sign * coeff, expon), true);
                    return *this;
                } else if(c >= '0' && c <= '9') {
                    expon_str += c;
                } else if(c == '+') {
                    expon = parseInt(expon_str, ptr_err);
                    sortedInsert(Item(sign * coeff, expon), true);
                    coeff_str.clear();
                    expon_str.clear();
                    sign = 1;
                    state = ST_SIGN;
                } else if(c == '-') {
                    expon = parseInt(expon_str, ptr_err);
                    sortedInsert(Item(sign * coeff, expon), true);
                    coeff_str.clear();
                    expon_str.clear();
                    sign = -1;
                    state = ST_SIGN;
                }
            }
        }
    }

    std::string toString() const {
        std::string result;
        for(ConstIterator iter = cbegin(); iter != cend(); ++iter) {
            if(iter->coeff > -1e-5 && iter->coeff < 1e-5) {
                continue;
            }
            if(iter->coeff >= 0) {
                if(!result.empty()) {
                    result += " + ";
                }
                if(!(iter->expon != 0 && iter->coeff > 0.99999 && iter->coeff < 1.00001)) {
                    result += std::to_string(iter->coeff);
                    result += ' ';
                }
            } else {
                if(!result.empty()) {
                    result += " - ";
                } else {
                    result += '-';
                }
                if(!(iter->expon != 0 && -iter->coeff > -0.99999 && -iter->coeff < 1.00001)) {
                    result += std::to_string(-iter->coeff);
                    result += ' ';
                }
            }
            if(iter->expon != 0) {
                result += "x";
                if(iter->expon != 1) {
                    result += '^';
                    result += std::to_string(iter->expon);
                }
            }
        }
        if(result.empty()) {
            result = "0";
        }
        return result;
    }

    Poly operator + (Poly const& rhs) const {
        Poly result;
        ConstIterator liter = cbegin();
        ConstIterator riter = rhs.cbegin();
        while(liter != cend() && riter != rhs.cend()) {
            if(riter->expon < liter->expon) {
                result.pushBack(*liter);
                ++liter;
            } else if(liter->expon < riter->expon) {
                result.pushBack(*riter);
                ++riter;
            } else {
                result.pushBack(Item(liter->coeff + riter->coeff, liter->expon));
                ++liter;
                ++riter;
            }
        }
        while(liter != cend()) {
            result.pushBack(*liter);
            ++liter;
        }
        while(riter != cend()) {
            result.pushBack(*riter);
            ++riter;
        }
        return result;
    }

    Poly operator - (Poly const& rhs) const {
        Poly result;
        ConstIterator liter = cbegin();
        ConstIterator riter = rhs.cbegin();
        while(liter != cend() && riter != rhs.cend()) {
            if(riter->expon < liter->expon) {
                result.pushBack(*liter);
                ++liter;
            } else if(liter->expon < riter->expon) {
                result.pushBack(Item(-riter->coeff, riter->expon));
                ++riter;
            } else {
                result.pushBack(Item(liter->coeff - riter->coeff, liter->expon));
                ++liter;
                ++riter;
            }
        }
        while(liter != cend()) {
            result.pushBack(*liter);
            ++liter;
        }
        while(riter != cend()) {
            result.pushBack(Item(-riter->coeff, riter->expon));
            ++riter;
        }
        return result;
    }

};

int main() {
    Poly a, b;
    try {
        std::string line;
        std::cerr << "a = ";
        std::getline(std::cin, line);
        a.parse(line);
        std::cerr << "b = ";
        std::getline(std::cin, line);
        b.parse(line);
    } catch(Poly::SyntaxError e) {
        e.report(4);
        return 1;
    }
    std::cout << std::endl;
    std::cout << "a = " << a.toString() << std::endl;
    std::cout << "b = " << b.toString() << std::endl;
    std::cout << std::endl;
    std::cout << "a + b = " << (a+b).toString() << std::endl;
    std::cout << "a - b = " << (a-b).toString() << std::endl;
    return 0;
}

TestCase.txt

Test case 1
2x+5x^8-3.1x^11
7-5x^8+11x^9

Test case 2
6x^-3-x+4.4x^2-1.2x^9
-6x^-3+5.4x^2-x^2+7.8x^15

Test case 3
1+x+x^2+x^3+x^4+x^5
-x^3-x^4

Test case 4
x+x^3
-x-x^3

Test case 5
x+x^100
x^100+x^200

Test case 6
x+x^2+x^3
0