Mai intai trebuie sa te autentifici.

Cod sursa(job #1282324)

Utilizator gabrieligabrieli gabrieli Data 4 decembrie 2014 01:25:47
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.91 kb
#include <algorithm>
#include <fstream>
#include <memory>
#include <string>
#include <vector>

#include <cmath>

#include <iostream>
using namespace std;

class ExpTree
{
public:
    virtual int eval() const = 0;
    virtual ~ExpTree() {}
};

class ConstNode : public ExpTree
{
public:
    ConstNode(const int value)
    : value {value}
    {}
    
    virtual int eval() const
    { return value; }
    
private:
    int value;
};

class UnaryOpNode : public ExpTree
{
public:
    UnaryOpNode(const char op, std::shared_ptr<ExpTree> rhs)
    : op {op}, rhs {rhs}
    {}
    
    virtual int eval() const
    { return - rhs->eval(); }

private:
    char op;
    std::shared_ptr<ExpTree> rhs;
};

class BinaryOpNode : public ExpTree
{
public:
    BinaryOpNode(const char op, std::shared_ptr<ExpTree> lhs, std::shared_ptr<ExpTree> rhs)
    : op {op}, lhs {lhs}, rhs {rhs}
    {}
    
    virtual int eval() const
    {
        switch(op) {
            case '+' : return lhs->eval() + rhs->eval();
            case '-' : return lhs->eval() - rhs->eval();
            case '*' : return lhs->eval() * rhs->eval();
            case '/' : return lhs->eval() / rhs->eval();
            case '^' : return std::pow(lhs->eval(), rhs->eval());
            default: return 0;
        }
    }

private:
    char op;
    std::shared_ptr<ExpTree> lhs;
    std::shared_ptr<ExpTree> rhs;
};

std::vector<std::vector<char>> operations = { {'+', '-'}, {'*', '/'}, {'^'}, {'-'} };
const int MAX_PRIORITY = 3;
const int UNARY_OPERATIONS_TRESHOLD = 3;

inline void advanceToken(std::string::const_iterator& token, const std::string::const_iterator& end)
{ ++token; while (token != end && *token == ' ') ++token; }

inline bool isNum(std::string::const_iterator& token)
{ return '0' <= *token && *token <= '9'; }

inline int getNum(std::string::const_iterator& token)
{ return *token - '0'; }

inline bool operationHasPriority(std::string::const_iterator& token, const int priority)
{
    return operations[priority].end() !=
            std::find(operations[priority].begin(), operations[priority].end(), *token);
}

std::shared_ptr<ExpTree> createTree(
    std::string::const_iterator& token,
    const std::string::const_iterator& end,
    const int priority = 0)
{
    std::shared_ptr<ExpTree> tree;
    
    if (priority > MAX_PRIORITY) // constants and paranthesized expressions
    {
        if (*token == '(')
        {
            advanceToken(token, end);
            tree = createTree(token, end);
            advanceToken(token, end);
        }
        else
        {
            int value = 0;
            while(token != end && isNum(token))
            {
                value = value * 10 + getNum(token);
                advanceToken(token, end);
            }            
            tree = std::make_shared<ConstNode>(value);
        }
    }
    else if (priority < UNARY_OPERATIONS_TRESHOLD) // binary operations
    {
        tree = createTree(token, end, priority + 1);        
        while (token != end && operationHasPriority(token, priority))
        {
            char op = *token;
            advanceToken(token, end);
            std::shared_ptr<ExpTree> temp = createTree(token, end, priority + 1);
            tree = std::make_shared<BinaryOpNode>(op, tree, temp);
        }
    }
    else if (token != end && operationHasPriority(token, priority)) // unary operations
    {
        char op = *token;
        advanceToken(token, end);
        tree = std::make_shared<UnaryOpNode>(
                        op,
                        createTree(token, end, priority)); 
    }
    else
    {
        tree = createTree(token, end, priority + 1);
    }
    
    return tree;
}

int main()
{
    std::ifstream fin("evaluare.in");
    std::ofstream fout("evaluare.out");
    
    std::string expression;
    fin >> expression;
    
    auto it = expression.cbegin();
    std::shared_ptr<ExpTree> tree = createTree(it, expression.cend());
    
    fout << tree->eval() << std::endl;
    
    return 0;
}