expression_calculator

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

enum IOType
{
    INTEGER,
    ADD,
    SUBTRACT,
    MULTIPLY,
    DIVIDE,
    LEFT_PAR,
    RIGHT_PAR
};


IOType OperatorToIOType(char);
bool isOperator(IOType);

char IOTypeToOperator(IOType ioType)
{
    if (ioType == ADD)
        return '+';
    else if (ioType == SUBTRACT)
        return '-';
    else if (ioType == MULTIPLY)
        return '*';
    else if (ioType == DIVIDE)
        return '/';
    else if (ioType == LEFT_PAR)
        return '(';
    else if (ioType == RIGHT_PAR)
        return ')';
    else
    {
        std::cout << "Invalid IOType for operator!" << std::endl;
        exit(1);
    }
}


class IntegerOrOperator
{
public:
    IOType type;
    double value;
    char op;
    explicit IntegerOrOperator(int v = 0) :
            type(INTEGER),
            value(v),
            op(' ')
    {
    }
    explicit IntegerOrOperator(char o = ' ') :
            type(OperatorToIOType(o)),
            value(0),
            op(o)
    {
    }
};


class Node;
std::ostream& operator<< (std::ostream&, const Node*);

class Node
{
public:
    IntegerOrOperator* value;
    std::vector<Node*> child;
    Node* parent;
    explicit Node(IntegerOrOperator* v = nullptr, Node* p = nullptr) { value = v; parent = p;}

    void addChild(Node* ch)
    {
        child.push_back(ch);
        ch->parent=this;
    }
};

std::ostream& operator<< (std::ostream &out, const Node* node)
{
    if (node)
    {
        if (node->value->type == INTEGER)
        {
            if (node->value->value - int(node->value->value) != 0)
                out << node->value->value;
            else
                out << int(node->value->value);
        }
        else
            out << IOTypeToOperator(node->value->type);
    }
    else
        out << "nullptr";
    return out;
}

/*
std::string PrintSet(std::set<Node*>& seen)
{
    if (seen.empty())
    {
        return "{}";
    }
    else
    {
        std::string x="{";
        for (Node* n : seen)
        {
            if (n)
            {
                if (n->value->type == INTEGER)
                {
                    if (n->value->value - int(n->value->value) != 0)
                        x.append(std::to_string(n->value->value));
                    else
                        x.append(std::to_string(int(n->value->value)));
                }
                else
                    x.append(std::string(1,IOTypeToOperator(n->value->type)));
                x.append(", ");
            }
        }
        x.pop_back();
        x.pop_back();
        x.append("}");
        return x;
    }
}
*/

Node* ExecuteOperator(Node*);

void BFS(Node* node, std::set<Node*>& seen)
{
    //std::cout << "Enter BFS(" << node << ", " << PrintSet(seen) << ")" << std::endl;
    while (!(seen.size() == 1 && node->child.empty()))
    {
        if (seen.count(node) == 0)
            seen.insert(node);

        if (node->child.size() == 2 && (node->child[0]->child.empty() && node->child[1]->child.empty()))
        {
            seen.erase(node->child[0]);
            seen.erase(node->child[1]);
            ExecuteOperator(node);

            if (node->parent)
            {
                node=node->parent;
                BFS(node, seen);
                //return;
            }
        }
        else
        {
            for (auto& ch : node->child)
            {
                if (!seen.count(ch) && isOperator(ch->value->type))
                    BFS(ch, seen);
            }
        }

        //std::cout << "Exit BFS(" << node << ", " << PrintSet(seen) << ")" << std::endl;
        return;
    }
}

void ForcedStop(const std::string& message)
{
    std::cout << message << std::endl;
    exit(1);
}

/*
void PrintExpression(const std::vector<IntegerOrOperator*>& expression)
{
    for(auto x : expression)
    {
        if (x->type == INTEGER)
            std::cout << x->value << " ";
        else
            std::cout << IOTypeToOperator(x->type) << " ";
    }
}
*/

int precedence(Node* node)
{
    if(node->value->type == ADD || node->value->type == SUBTRACT)
        return 1;
    else if(node->value->type == MULTIPLY || node->value->type == DIVIDE)
        return 2;
    else
        return 0;
}


bool isOperator(IOType ioType)
{
    return (ioType == ADD || ioType == SUBTRACT || ioType == MULTIPLY || ioType == DIVIDE);
}


std::vector<IntegerOrOperator*> expression(const std::string& str_expr)
{
    std::vector<IntegerOrOperator*> expr;
    for(unsigned int i = 0; i < str_expr.size(); ++i)
    {
        while (str_expr[i] == ' ')
            i++;
        if (i >= str_expr.size())
            break;
        if ((expr.empty() || expr.back()->type == LEFT_PAR) && (str_expr[i] == '+' || str_expr[i] == '-'))
            expr.push_back(new IntegerOrOperator(0));
        if (!isdigit(str_expr[i]))
            expr.push_back(new IntegerOrOperator(str_expr[i]));
        else
        {
            if (i > 0 && str_expr[i-1] != ' ' && expr.back()->type == INTEGER)
                expr.back()->value = stoi(std::to_string(int(expr.back()->value))+std::to_string(str_expr[i] - '0'));
            else
                expr.push_back(new IntegerOrOperator(int(str_expr[i] - '0')));
        }
    }
    return expr;
}


Node* ExecuteOperator(Node* node)
{
    if (node->child.empty())
    {
        if (node->value->type == INTEGER)
            return node;
        else
            ForcedStop("Invalid expression!");

    }
    else if (node->child.size() == 1)
        ForcedStop("Invalid expression!");
    else if (node->child.size() == 2)
    {
        //std::cout << "Calculate: " << node->child[0] << " " << node << " " << node->child[1];
        if (node->child[0]->value->type == INTEGER && node->child[1]->value->type == INTEGER)
        {
            if (node->value->type == ADD)
                node->value->value = node->child[0]->value->value + node->child[1]->value->value;
            else if (node->value->type == SUBTRACT)
                node->value->value = node->child[0]->value->value - node->child[1]->value->value;
            else if (node->value->type == MULTIPLY)
                node->value->value = node->child[0]->value->value * node->child[1]->value->value;
            else if (node->value->type == DIVIDE)
            {
                if (node->child[1]->value->value != 0)
                    node->value->value = node->child[0]->value->value / node->child[1]->value->value;
                else
                    ForcedStop("Zero divisor!");
            }
            //std::cout << " = " << node->value->value << std::endl;
            node->value->type = INTEGER;

            for (int k=node->child.size(); k==0; --k)
                delete node->child[k];

            node->child.clear();
        }
        else
            ForcedStop("Invalid expression!");
    }

    return node;
}

IOType OperatorToIOType(char operator_char)
{
    if (operator_char == '+')
        return ADD;
    else if (operator_char == '-')
        return SUBTRACT;
    else if (operator_char == '*')
        return MULTIPLY;
    else if (operator_char == '/')
        return DIVIDE;
    else if (operator_char == '(')
        return LEFT_PAR;
    else if (operator_char == ')')
        return RIGHT_PAR;
    else
    {
        std::cout << "Invalid operator!" << std::endl;
        exit(1);
    }
}


Node* evaluate(const std::vector<IntegerOrOperator*>& expression)
{
    Node* prevNode = nullptr;
    Node* newNode = nullptr;
    Node* root = nullptr;
    Node* prevOp = nullptr;

    for(unsigned int i = 0; i < expression.size(); ++i)
    {
        newNode = new Node(expression[i]);
        if (isOperator(newNode->value->type))
        {
            if (prevNode)
            {
                if (prevOp)
                {
                    Node* d = prevOp;
                    if (precedence(d) < precedence(newNode))
                    {
                        prevOp->addChild(newNode);
                        newNode->addChild(prevNode);
                    }
                    else
                    {
                        while (precedence(d) >= precedence(newNode) && d != root)
                        {
                            d = d->parent;
                            if (precedence(d) < precedence(newNode))
                            {
                                d = d->child[1];
                                break;
                            }
                        }

                        if (d == root)
                        {
                            newNode->addChild(d);
                            root = newNode;

                            if(prevNode->child.empty())
                                prevOp->addChild(prevNode);
                        }
                        else
                        {
                            (d->parent)->child.erase((d->parent)->child.begin()+1);
                            (d->parent)->addChild(newNode);
                            d->addChild(prevNode);
                            newNode->addChild(d);
                        }
                    }
                }
                else
                {
                    newNode->addChild(prevNode);
                    root = newNode;
                }

                if (isOperator(prevNode->value->type) && prevNode->child.empty())
                    prevNode->addChild(newNode);
            }

            prevNode = newNode;
            prevOp = prevNode;

        }
        else if (newNode->value->type == LEFT_PAR)
        {
            std::vector<IntegerOrOperator*> loc_expr;
            ++i;

            int n_par = 1;
            while (n_par > 0)
            {
                if (expression[i]->type == LEFT_PAR)
                    ++n_par;
                else if (expression[i]->type == RIGHT_PAR)
                    --n_par;
                if (n_par > 0)
                    loc_expr.push_back(expression[i]);
                ++i;
            }
            --i;

            newNode = evaluate(loc_expr);
            prevOp->addChild(newNode);
            prevNode = newNode;
        }
        else
        {
            if (prevNode && expression[i] == expression.back())
                prevOp->addChild(newNode);

            prevNode = newNode;
            prevOp = isOperator(prevNode->value->type) ? prevNode : prevOp;
        }
    }
    return root;
}


double calculate(std::string& str_expr)
{
    auto node = evaluate(expression(str_expr));
    std::set<Node*> seen;
    BFS(node, seen);
    return node->value->value;
}


int main()
{
    std::string s = "10 * (100 - 3 / (2 * 10) + 77 *(15 + 10)) + 100";
    std::cout << calculate(s) << std::endl;

    return 0;
}