ArithmeticTree

#include <iostream>
#include <string>
#include <vector>

template<typename TValue>
class Cloneable {
public:
    using value_type = TValue;
    using pointer = TValue *;

    virtual pointer clone() const = 0;
};

class BaseNode : public Cloneable<BaseNode> {
protected:
    BaseNode *left_;
    BaseNode *right_;

public:
    BaseNode()
            :
            left_(nullptr),
            right_(nullptr) {}

    BaseNode(const BaseNode &other)
            :
            left_(nullptr),
            right_(nullptr) {
        if (other.left_ != nullptr) {
            left_ = other.left_->clone();
        }
        if (other.right_ != nullptr) {
            right_ = other.right_->clone();
        }
    }

    BaseNode(BaseNode &&other)
            :
            left_(other.left_),
            right_(other.right_) {
        other.left_ = nullptr;
        other.right_ = nullptr;
    }

    virtual ~BaseNode() {
        delete left_;
        delete right_;
    }

    virtual double operator()() const = 0;

    virtual std::string to_string() const = 0;

    void setLeft(BaseNode *left) {
        left_ = left;
    }

    void setRight(BaseNode *right) {
        right_ = right;
    }
};

class NilNode : public BaseNode {
public:
    double operator()() const override {
        return left_->operator()();
    }

    std::string to_string() const override {
        return left_->to_string();
    }

    BaseNode *clone() const override {
        BaseNode *self = new NilNode;

        if (left_ != nullptr) {
            self->setLeft(left_->clone());
        }
        if (right_ != nullptr) {
            self->setRight(right_->clone());
        }
        return self;
    }
};

class PlusNode : public BaseNode {
public:
    double operator()() const override {
        if (left_ == nullptr && right_ == nullptr) {
            return 0;
        } else if (left_ == nullptr) {
            return right_->operator()();
        } else if (right_ == nullptr) {
            return left_->operator()();
        } else {
            return left_->operator()() + right_->operator()();
        }
    }

    std::string to_string() const override {
        if (left_ == nullptr && right_ == nullptr) {
            return "";
        } else if (left_ == nullptr) {
            return right_->to_string();
        } else if (right_ == nullptr) {
            return left_->to_string();
        } else {
            return "(" + left_->to_string() + "+" + right_->to_string() + ")";
        }
    }

    BaseNode *clone() const override {
        BaseNode *self = new PlusNode;

        if (left_ != nullptr) {
            self->setLeft(left_->clone());
        }
        if (right_ != nullptr) {
            self->setRight(right_->clone());
        }
        return self;
    }
};

class MinusNode : public BaseNode {
public:
    double operator()() const override {
        if (left_ == nullptr && right_ == nullptr) {
            return 0;
        } else if (left_ == nullptr) {
            return right_->operator()() * -1;
        } else if (right_ == nullptr) {
            return left_->operator()() * -1;
        } else {
            return left_->operator()() - right_->operator()();
        }
    }

    std::string to_string() const override {
        if (left_ == nullptr && right_ == nullptr) {
            return "";
        } else if (left_ == nullptr) {
            return "-" + right_->to_string();
        } else if (right_ == nullptr) {
            return "-" + left_->to_string();
        } else {
            return "(" + left_->to_string() + "-" + right_->to_string() + ")";
        }
    }

    BaseNode *clone() const override {
        BaseNode *self = new MinusNode;

        if (left_ != nullptr) {
            self->setLeft(left_->clone());
        }
        if (right_ != nullptr) {
            self->setRight(right_->clone());
        }
        return self;
    }
};

class MultiplyNode : public BaseNode {
public:
    double operator()() const override {
        return left_->operator()() * right_->operator()();
    }

    std::string to_string() const override {
        return "(" + left_->to_string() + "*" + right_->to_string() + ")";
    }

    BaseNode *clone() const override {
        BaseNode *self = new MultiplyNode;

        if (left_ != nullptr) {
            self->setLeft(left_->clone());
        }
        if (right_ != nullptr) {
            self->setRight(right_->clone());
        }
        return self;
    }
};

class DivisionNode : public BaseNode {
public:
    double operator()() const override {
        return left_->operator()() / right_->operator()();
    }

    std::string to_string() const override {
        return "(" + left_->to_string() + "/" + right_->to_string() + ")";
    }

    BaseNode *clone() const override {
        BaseNode *self = new DivisionNode;

        if (left_ != nullptr) {
            self->setLeft(left_->clone());
        }
        if (right_ != nullptr) {
            self->setRight(right_->clone());
        }
        return self;
    }
};

class DegreeNode : public BaseNode {
public:
    double operator()() const override {
        return std::pow(left_->operator()(), right_->operator()());
    }

    std::string to_string() const override {
        return "(" + left_->to_string() + "^" + right_->to_string() + ")";
    }

    BaseNode *clone() const override {
        BaseNode *self = new DegreeNode;

        if (left_ != nullptr) {
            self->setLeft(left_->clone());
        }
        if (right_ != nullptr) {
            self->setRight(right_->clone());
        }
        return self;
    }
};

class ConstantNode : public BaseNode {
public:
    double constant;

    explicit ConstantNode(double constant)
            :
            BaseNode(),
            constant(constant) {}

    double operator()() const override {
        return constant;
    }

    std::string to_string() const override {
        return std::to_string(constant);
    }

    BaseNode *clone() const override {
        BaseNode *self = new ConstantNode(constant);

        if (left_ != nullptr) {
            self->setLeft(left_->clone());
        }
        if (right_ != nullptr) {
            self->setRight(right_->clone());
        }
        return self;
    }
};


class ArithmeticTree {
    NilNode nil_;

public:
    ArithmeticTree() = default;

    ArithmeticTree(const ArithmeticTree &other) = default;

    ArithmeticTree(ArithmeticTree &&other) noexcept
            : nil_(std::move(other.nil_)) {}

    double process() const {
        return nil_.operator()();
    }

    std::string to_string() const {
        return nil_.to_string();
    }

    static ArithmeticTree parse(const std::string &source) {
        ArithmeticTree tree;
        std::vector<std::string> tokens(std::move(toTokens(source)));
        tree.nil_.setLeft(build(tokens, 0, tokens.size() - 1));
        return tree;
    }

private:
    static std::vector<std::string> toTokens(const std::string &source) {
        std::vector<std::string> tokens;
        std::string number_str;
        for (char i: source) {
            if (i == '(' || i == ')' ||
                i == '^' ||
                i == '*' || i == '/' ||
                i == '+' || i == '-') {
                if (!number_str.empty()) {
                    tokens.push_back(number_str);
                    number_str.clear();
                }
                tokens.emplace_back(1, i);
            } else {
                if (isdigit(i) || i == '.' || i == ',') {
                    number_str += i;
                }
            }
        }
        if (!number_str.empty()) {
            tokens.push_back(number_str);
        }
        return std::move(tokens);
    }

    static BaseNode *build(const std::vector<std::string> &tokens, int start, int end) {
        if (end < start) {
            return nullptr;
        }
        int inflection_index;
        if (end - start == 1) {
            if (tokens[start] == "(" || tokens[start] == ")") {
                inflection_index = end;
            } else {
                inflection_index = start;
            }
        } else {
            inflection_index = static_cast<int>(inflectionPoint(tokens, start, end));
        }

        BaseNode *new_node;
        if (tokens[inflection_index] == "+") {
            new_node = new PlusNode;
        } else if (tokens[inflection_index] == "-") {
            new_node = new MinusNode;
        } else if (tokens[inflection_index] == "*") {
            new_node = new MultiplyNode;
        } else if (tokens[inflection_index] == "/") {
            new_node = new DivisionNode;
        } else if (tokens[inflection_index] == "^") {
            new_node = new DegreeNode;
        } else {
            new_node = new ConstantNode(std::strtod(tokens[inflection_index].data(), nullptr));
        }

        new_node->setLeft(build(tokens, start, inflection_index - 1));
        new_node->setRight(build(tokens, inflection_index + 1, end));
        return new_node;
    }

    static size_t inflectionPoint(const std::vector<std::string> &tokens, size_t start, size_t end) {
        size_t result_index = start;
        int maximum_by_priority = std::numeric_limits<int>::min();
        int degree_of_nesting = 0;
        for (size_t i = start; i <= end; ++i) {
            int8_t priority = getPriority(tokens[i]);
            if (priority == 0) {
                if (tokens[i] == "(") {
                    degree_of_nesting++;
                } else if (tokens[i] == ")") {
                    degree_of_nesting--;
                }
            } else {
                if (maximum_by_priority <= priority - 3 * degree_of_nesting) {
                    maximum_by_priority = priority - 3 * degree_of_nesting;
                    result_index = i;
                }
            }
        }
        return result_index;
    }

    static int8_t getPriority(const std::string &operation) {
        if (operation == "+" || operation == "-") {
            return 3;
        } else if (operation == "*" || operation == "/") {
            return 2;
        } else if (operation == "^") {
            return 1;
        } else {
            return 0;
        }
    }
};

int main() {
    std::string expression;
    std::cin >> expression;
    ArithmeticTree tree = ArithmeticTree::parse(expression);
    std::cout << tree.to_string() << std::endl;
    std::cout << tree.process();
    return 0;
}