лексический анализ дубль 2 - C++ - Ответ 4368329

#include <iostream>
#include <cmath>
#include <cstdlib>
 
using namespace std;
 
template <typename T1, typename T2>
struct MyPair {
    T1 first;
    T2 second;
    MyPair(const T1 &t1 = T1(), const T2 &t2 = T2()) : first(t1), second(t2) {}
};
 
template <typename T>
class MyVect {
public:
    MyVect() : data(0), size(0), capacity(0) {}
 
    MyVect(const MyVect& vect)
    : data(0), size(vect.size), capacity(vect.capacity) {
        copy_data(vect);
    }
 
    ~MyVect() {
        delete[] data;
        data = 0;
        size = 0;
        capacity = 0;
    }
 
    MyVect& operator=(const MyVect &vect) {
        delete[] data;
        data = 0;
        capacity = vect.capacity;
        size = vect.size;
        copy_data(vect);
        return *this;
    }
 
    T *begin() {
        return data;
    }
 
    T *end() {
        return data + size;
    }
 
    const T *begin() const {
        return data;
    }
 
    const T *end() const {
        return data + size;
    }
 
    T& back() {
      return data[size - 1];
    }
 
    const T& back() const {
      return data[size - 1];
    }
 
    bool empty() const {
        return size == 0;
    }
 
    void clear() {
        size = 0;
    }
 
    void push_back(const T &t) {
        if (size == capacity)
            resize();
        data[size++] = t;
    }
 
    void operator+=(const T &t) {
        push_back(t);
    }
 
    bool operator==(const MyVect &vect) const {
        if (size != vect.size)
            return false;
        for (int i = 0; i < size; ++i) {
            if (data[i] != vect.data[i])
                return false;
        }
        return true;
    }
 
private:
    void resize() {
        int capacity_new = capacity ? 2*capacity : 1;
        T *data_new = new T[capacity_new];
        if (data) {
            for (int i = 0; i < capacity; ++i) {
                data_new[i] = data[i];
            }
        }
        delete[] data;
        data = data_new;
        capacity = capacity_new;
    }
 
    void copy_data(const MyVect &vect) {
        if (capacity) {
            data = new T[capacity];
            for (int i = 0; i < size; ++i) {
                data[i] = vect.data[i];
            }
        }
    }
 
    T *data;
    int size;
    int capacity;
};
 
template <typename K, typename V>
class MyMap: public MyVect<MyPair<K, V>> {
public:
    typedef MyPair<K, V> Pair;
    typedef MyVect<Pair> Base;
 
    V &operator[](const K &key) {
        for (auto &d : *this) {
            if (d.first == key)
                return d.second;
        }
        Base::push_back(Pair(key, V()));
        return Base::back().second;
    }
 
    Pair *find(const K &key) {
        for (const auto &d : *this) {
            if (d.first == key)
                return &d;
        }
        return Base::end();
    }
 
    const Pair *find(const K &key) const {
        for (const auto &d : *this) {
            if (d.first == key)
                return &d;
        }
        return Base::end();
    }
};
 
class MyString: public MyVect<char> {
public:
    MyString() {}
 
    MyString(const char *s) {
        while (*s)
            push_back(*s++);
    }
 
    MyString(int count, char c) {
        while (count--) {
            push_back(c);
        }
    }
 
    const char *c_str() const {
        buf = *this;
        buf += '\0';
        return buf.begin();
    }
 
private:
    mutable MyVect<char> buf;
};
 
ostream &operator<<(ostream &out, const MyString &s)
{
    out << s.c_str();
    return out;
}
 
class Variables {
public:
    void set(const MyString &var, double val) {
        values[var] = val;
    }
 
    double value(const MyString &var) const {
        auto iter = values.find(var);
        return (iter != values.end()) ? iter->second : 0;
    }
 
    bool contains(const MyString &var) const {
        return values.find(var) != values.end();
    }
 
    void getAll(MyVect<MyString> &vars) const {
        vars.clear();
        for (const auto &var : values) {
            vars.push_back(var.first);
        }
    }
 
    void print(ostream &out) const {
        for (const auto &var : values) {
            out << var.first << " = " << var.second << endl;
        }
    }
 
private:
    MyMap<MyString, double> values;
};
 
ostream &operator<<(ostream &out, const Variables &vars) {
    vars.print(out);
    return out;
}
 
class Monomial {
public:
    Monomial(double c = 1) : coefficient(c) {}
 
    void multiply(double d) {
        coefficient *= d;
    }
 
    void multiply(const MyString& var, int degree = 1) {
        degrees[var] += degree;
    }
 
    double coef() const {
        return coefficient;
    }
 
    int degree(const MyString& var) const {
        auto iter = degrees.find(var);
        return iter != degrees.end() ? iter->second : 0;
    }
 
    double eval(const Variables &vars) const {
        double res = coefficient;
        for (const auto &v : degrees) {
            res *= pow(vars.value(v.first), v.second);
        }
        return res;
    }
 
    void print(ostream &out, bool coefSign = true) const {
        double absCoef = abs(coefficient);
        bool needMult = true;
        if (absCoef != 1) {
            out << (coefSign ? coefficient : absCoef);
        } else {
            needMult = false;
            if (coefficient < 0 && coefSign)
                out << "-";
        }
        for (const auto &v : degrees) {
            if (v.second == 0)
                continue;
            out << (needMult ? "*" : "") << v.first;
            if (v.second != 1)
                out << "^" << (v.second < 0 ? "(" : "") << v.second
                           << (v.second < 0 ? ")" : "");
            needMult = true;
        }
    }
 
private:
    double coefficient;
    MyMap<MyString, int> degrees;
};
 
class Polynomial {
public:
    void add(const Monomial& monomial) {
        monomials.push_back(monomial);
    }
 
    int maxDegree(const MyString& var) const {
        int res = 0;
        for (const auto &m : monomials) {
            res = max(res, m.degree(var));
        }
        return res;
    }
 
    double eval(const Variables &vars) const {
        double res = 0;
        for (const auto &m : monomials) {
            res += m.eval(vars);
        }
        return res;
    }
 
    void print(ostream &out) const {
        if (monomials.empty()) {
            out << "0";
            return;
        }
        auto iter = monomials.begin();
        iter->print(out);
        while (++iter != monomials.end()) {
            out << (iter->coef() > 0 ? " + " : " - ");
            iter->print(out, false);
        }
    }
 
private:
    MyVect<Monomial> monomials;
};
 
ostream &operator<<(ostream &out, const Polynomial &poly) {
    poly.print(out);
    return out;
}
 
class Parser {
public:
    static bool parse(const MyString &s, const Variables &vars, Polynomial &poly) {
        iter_t iter = s.c_str();
        try {
            Parser p(iter, vars);
            poly = p.poly();
        } catch (Error &e) {
            int consumed = iter - s.c_str();
            cerr << "Error: " << e.description << ":" << endl
                 << s << endl << MyString(consumed, ' ') << '^' << endl;
            return false;
        }
        return true;
    }
 
private:
    typedef const char* iter_t;
 
    struct Error {
        MyString description;
        Error(const MyString& descr) : description(descr) {}
    };
 
    iter_t &iter;
    const Variables &vars;
 
    Parser(iter_t &it, const Variables &vs) : iter(it), vars(vs) {}
 
    void skip() {
        while (*iter == ' ' || *iter == '\t')
            ++iter;
    }
 
    void consume() {
        iter++;
        skip();
    }
 
    bool isSign() {
        return *iter == '+' || *iter == '-';
    }
 
    Polynomial poly() {
        skip();
        if (!*iter)
            throw Error("unexpected end of string");
        Polynomial res;
        res.add(mono(true));
        skip();
        while (isSign()) {
            bool minus = (*iter++ == '-');
            Monomial m = mono(false);
            if (minus)
                m.multiply(-1);
            res.add(m);
            skip();
        }
        if (*iter)
            throw Error("expected '+' or '-'");
        return res;
    }
 
    Monomial mono(bool expectSign) {
        skip();
        if (!*iter)
            throw Error("unexpected end of string");
        Monomial res;
        if (isSign()) {
            if (!expectSign)
                throw Error("unexpected sign");
            if (*iter == '-')
                res.multiply(-1);
            consume();
        }
        bool first = true;
        if (isdigit(*iter)) {
            first = false;
            res.multiply(real());
            skip();
        }
        while (first || *iter == '*') {
            if (first)
                first = false;
            else
                consume();
            if (!isalpha(*iter))
                throw Error("variable expected");
            MyString var = variable();
            skip();
            if (*iter != '^') {
                res.multiply(var);
            } else {
                consume();
                if (!isdigit(*iter))
                    throw Error("integer value expected");
                res.multiply(var, integer());
            }
            skip();
        }
        return res;
    }
 
    MyString variable() {
        MyString res;
        iter_t start = iter;
        while (isalpha(*iter))
            res += *iter++;
        if (!vars.contains(res)) {
            iter = start;
            throw Error("unknown variable");
        }
        return res;
    }
 
    double real() {
        char* end;
        double res = strtod(iter, &end);
        iter = end;
        return res;
    }
 
    int integer() {
        int res = 0;
        while (isdigit(*iter))
            res = res*10 + (*iter++ - '0');
        return res;
    }
};
 
int main()
{
    Variables vars;
    vars.set("x", 1);
    vars.set("y", -3);
    vars.set("z", 2);
    vars.set("alpha", 0.5);
    cout << vars << endl;
    Polynomial p;
    if (Parser::parse("-5*x^20 + 2*alpha^3*z^5 - x*y*z - alpha^2*x^2", vars, p)) {
        cout << p << " = " << p.eval(vars) << endl << endl;
        MyVect<MyString> all;
        vars.getAll(all);
        for (const auto &v : all) {
            cout << "max degree of " << v << " is " << p.maxDegree(v) << endl;
        }
    }
}