Cod sursa(job #1296156)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 20 decembrie 2014 16:44:11
Problema Evaluarea unei expresii Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 7.34 kb
#include <iostream>
#include <sstream>
#include <exception>
#include <cstring>
#include <string>
#include <fstream>

enum TokenType
{
    Error,
    Plus,
    Minus,
    Mul,
    Div,
    EndOfText,
    OpenParenthesis,
    ClosedParenthesis,
    Number
};

struct Token
{
    TokenType   Type;
    double      Value;
    char      Symbol;

    Token():Type(Error), Value(0), Symbol(0)
    {}
};

enum ASTNodeType
{
    Undefined,
    OperatorPlus,
    OperatorMinus,
    OperatorMul,
    OperatorDiv,
    UnaryMinus,
    NumberValue
};

class ASTNode
{
public:
    ASTNodeType Type;
    double      Value;
    ASTNode*    Left;
    ASTNode*    Right;

    ASTNode()
    {
        Type = Undefined;
        Value = 0;
        Left = NULL;
        Right = NULL;
    }

    ~ASTNode()
    {
        delete Left;
        delete Right;
    }
};

class ParserException : public std::exception
{
    int m_Pos;
    std::string m_Message;

public:
    ParserException(const std::string& message, int pos):
    m_Message(message),
    m_Pos(pos)
    {}

    const char* what() const noexcept(true) {
        return m_Message.c_str();
    }
};

class Parser
{
    Token m_crtToken;
    const char* m_Text;
    size_t m_Index;

private:

    ASTNode* Expression()
    {
        ASTNode* tnode = Term();
        ASTNode* e1node = Expression1();

        return CreateNode(OperatorPlus, tnode, e1node);
    }

    ASTNode* Expression1()
    {
        ASTNode* tnode;
        ASTNode* e1node;

        switch(m_crtToken.Type)
        {
          case Plus:
          GetNextToken();
          tnode = Term();
          e1node = Expression1();

          return CreateNode(OperatorPlus, e1node, tnode);

          case Minus:
          GetNextToken();
          tnode = Term();
          e1node = Expression1();

          return CreateNode(OperatorMinus, e1node, tnode);
      }

      return CreateNodeNumber(0);
  }

  ASTNode* Term()
  {
    ASTNode* fnode = Factor();
    ASTNode* t1node = Term1();

    return CreateNode(OperatorMul, fnode, t1node);
}

ASTNode* Term1()
{
    ASTNode* fnode;
    ASTNode* t1node;

    switch(m_crtToken.Type)
    {
      case Mul:
      GetNextToken();
      fnode = Factor();
      t1node = Term1();
      return CreateNode(OperatorMul, t1node, fnode);

      case Div:
      GetNextToken();
      fnode = Factor();
      t1node = Term1();
      return CreateNode(OperatorDiv, t1node, fnode);
  }

  return CreateNodeNumber(1);
}

ASTNode* Factor()
{
    ASTNode* node;
    switch(m_crtToken.Type)
    {
      case OpenParenthesis:
      GetNextToken();
      node = Expression();
      Match(')');
      return node;

      case Minus:
      GetNextToken();
      node = Factor();
      return CreateUnaryNode(node);

      case Number:
      {
        double value = m_crtToken.Value;
        GetNextToken();
        return CreateNodeNumber(value);
    }

    default:
    {
        std::stringstream sstr;
        sstr << "Unexpected token '" << m_crtToken.Symbol << "' at position " << m_Index;
        throw ParserException(sstr.str(), m_Index);
    }
}
}

ASTNode* CreateNode(ASTNodeType type, ASTNode* left, ASTNode* right)
{
    ASTNode* node = new ASTNode;
    node->Type = type;
    node->Left = left;
    node->Right = right;

    return node;
}

ASTNode* CreateUnaryNode(ASTNode* left)
{
    ASTNode* node = new ASTNode;
    node->Type = UnaryMinus;
    node->Left = left;
    node->Right = NULL;

    return node;
}

ASTNode* CreateNodeNumber(double value)
{
    ASTNode* node = new ASTNode;
    node->Type = NumberValue;
    node->Value = value;

    return node;
}

void Match(char expected)
{
    if(m_Text[m_Index-1] == expected)
        GetNextToken();
    else
    {
        std::stringstream sstr;
        sstr << "Expected token '" << expected << "' at position " << m_Index;
        throw ParserException(sstr.str(), m_Index);
    }
}

void SkipWhitespaces()
{
    while(isspace(m_Text[m_Index])) m_Index++;
}

void GetNextToken()
{
    SkipWhitespaces();

    m_crtToken.Value = 0;
    m_crtToken.Symbol = 0;

    if(m_Text[m_Index] == 0)
    {
        m_crtToken.Type = EndOfText;
        return;
    }

    if(isdigit(m_Text[m_Index]))
    {
        m_crtToken.Type = Number;
        m_crtToken.Value = GetNumber();
        return;
    }

    m_crtToken.Type = Error;

    switch(m_Text[m_Index])
    {
        case '+': m_crtToken.Type = Plus; break;
        case '-': m_crtToken.Type = Minus; break;
        case '*': m_crtToken.Type = Mul; break;
        case '/': m_crtToken.Type = Div; break;
        case '(': m_crtToken.Type = OpenParenthesis; break;
          case ')': m_crtToken.Type = ClosedParenthesis; break;
}

if(m_crtToken.Type != Error)
{
    m_crtToken.Symbol = m_Text[m_Index];
    m_Index++;
}
else
{
    std::stringstream sstr;
    sstr << "Unexpected token '" << m_Text[m_Index] << "' at position " << m_Index;
    throw ParserException(sstr.str(), m_Index);
}
}

double GetNumber()
{
    SkipWhitespaces();

    int index = m_Index;
    while(isdigit(m_Text[m_Index])) m_Index++;
    if(m_Text[m_Index] == '.') m_Index++;
    while(isdigit(m_Text[m_Index])) m_Index++;

    if(m_Index - index == 0)
        throw ParserException("Number expected but not found!", m_Index);

    char buffer[32] = {0};
    memcpy(buffer, &m_Text[index], m_Index - index);

    return atof(buffer);
}

public:
    ASTNode* Parse(const char* text)
    {
        m_Text = text;
        m_Index = 0;
        GetNextToken();

        return Expression();
    }
};


class EvaluatorException : public std::exception
{
    std::string m_Message;
public:
    EvaluatorException(const std::string& message):
    m_Message(message)
    {}

    const char* what() noexcept(true) {
        return m_Message.c_str();
    }

};

class Evaluator
{
    double EvaluateSubtree(ASTNode* ast)
    {
        if(ast == NULL)
            throw EvaluatorException("Incorrect syntax tree!");

        if(ast->Type == NumberValue)
            return ast->Value;
        else if(ast->Type == UnaryMinus)
            return -EvaluateSubtree(ast->Left);
        else
        {
            double v1 = EvaluateSubtree(ast->Left);
            double v2 = EvaluateSubtree(ast->Right);
            switch(ast->Type)
            {
                case OperatorPlus:  return v1 + v2;
                case OperatorMinus: return v1 - v2;
                case OperatorMul:   return v1 * v2;
                case OperatorDiv:   return v1 / v2;
            }
        }

        throw EvaluatorException("Incorrect syntax tree!");
    }

public:
    double Evaluate(ASTNode* ast)
    {
        if(ast == NULL)
            throw EvaluatorException("Incorrect abstract syntax tree");

        return EvaluateSubtree(ast);
    }
};

void Test(const char* text)
{
   Parser parser;

   try
   {
      ASTNode* ast = parser.Parse(text);

      try
      {
         Evaluator eval;
         double val = eval.Evaluate(ast);

         std::cout << text << " = " << val << std::endl;
      }
      catch(EvaluatorException& ex)
      {
        std::cout << text << " t " << ex.what() << std::endl;
      }

      delete ast;
   }
   catch(ParserException& ex)
   {
      std::cout << text << " t " << ex.what() << std::endl;
   }
}

std::ifstream in("evaluare.in");
std::ofstream out("evaluare.out");

int main()
{
    std::string text;
    std::getline(in,text);

    Parser parser;
    ASTNode* ast = parser.Parse(text.c_str());
    Evaluator eval;
    double val = eval.Evaluate(ast);
    out << int(val);
}