Mai intai trebuie sa te autentifici.
Cod sursa(job #1282324)
Utilizator | 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;
}