Парсер для математических выражений

#ifndef PARSER_H_INCLUDED
#define PARSER_H_INCLUDED
 
namespace Parser
{
    std::string toPolish(std::string s);
}
 
#endif // PARSER_H_INCLUDED

#include <string>
#include <map>
#include <stdio.h>
#include "errors.h"
#include "parser.h"
 
namespace __Stack
{
    struct Stack
    {
        std::string value;
        Stack *next;
    };
 
    Stack *tail = NULL;
 
    void        push(std::string);
    std::string pop();
    void        clear();
}
 
void __Stack::push(std::string value)
{
    Stack *stk = new Stack();
 
    stk->value = value;
    stk->next = tail;
 
    tail = stk;
}
 
std::string __Stack::pop()
{
    std::string result = tail->value;
    Stack *stk = tail;
 
    tail = tail->next;
    delete stk;
 
    return result;
}
 
void __Stack::clear()
{
    Stack *stk;
 
    while (tail)
    {
        stk = tail;
        tail = tail->next;
        delete stk;
    }
}
 
///////////////////////////////////////////////////////////////////
 
namespace __Parser
{
    enum eTokens
    {
        NAME,           NUMBER,          FUNC,      U_MINUS,
        PLUS = '+',     MINUS = '-',     MUL = '*', DIV = '/',
        POW  = '^',     SQRT  = '\\',
        L_BRUNCH = '(', R_BRUNCH = ')'
    };
 
    eTokens curr_token;
    uint16_t char_pos = 0;
    //Используется для определения, является знак '+' или '-'
    //унарным или бинарным.
    //Если это начало выражения или перед текущим знаком была бинарная
    //операция или открывающая скобка - знак унарный.
    bool sign = true;
    //Имя переменной
    std::string x_name;
    std::string functions = {"sin", "cos"};
    std::map<eTokens, int> token_priority = {{L_BRUNCH, 0},
                                             {R_BRUNCH, 0},
                                             {PLUS,     1},
                                             {MINUS,    1},
                                             {MUL,      2},
                                             {DIV,      2},
                                             {POW,      3},
                                             {SQRT,     3},
                                             {U_MINUS,  4},
                                             {FUNC,     5}};
    const int funcs_count = 2;
 
    inline char getChar(std::string &);
    inline void backChar();
    bool        isFunc(std::string &);
    std::string getNumber(std::string &);
    std::string getName(std::string &);
    std::string getToken(std::string &);
    std::string pop();
    void        deleteSpaces(std::string);
    std::string toPolish(std::string &);
}
 
char __Parser::getChar(std::string &s)
{
    return s[char_pos++];
}
 
void __Parser::backChar()
{
    char_pos--;
}
 
bool __Parser::isFunc(std::string &s)
{
    for (int i = 0; i<funcs_count; i++)
    {
        if (s.find(functions[i]))
        {
            return true;
        }
    }
    return false;
}
 
std::string __Parser::getNumber(std::string &s)
{
    std::string result;
    char c = getChar(s);
 
    while ((c>'0') && (c<'9'))
    {
        result += c;
        if (char_pos == s.length() - 1)
        {
            return result;
        }
        c = getChar(s);
    }
    backChar();
 
    return result;
}
 
std::string __Parser::getName(std::string &s)
{
    std::string result;
    char c = getChar(s);
    bool end_str = false;
 
    while (isalpha(c))
    {
        result += c;
        if (char_pos == s.length() - 1)
        {
            end_str = true;
            break;
        }
        c = getChar(s);
    }
    if (!end_str)
    {
        backChar();
    }
 
    if (isFunc(result))
    {
        curr_token = FUNC;
    }
    else
    {
        curr_token = NAME;
        if (x_name.empty())
        {
            x_name = result;
        }
        else
        {
            throw Error("ошибка: неверное имя переменной", char_pos - result.length());
        }
    }
 
    return result;
}
 
std::string __Parser::getToken(std::string &s)
{
    char c = getChar(s);
 
    switch (c)
    {
        case '+': case '-':  case '*': case '/':
        case '^': case '\\': case '(': case ')':
            curr_token = (eTokens)c;
            std::string result;
            result += c;
            return result;
    }
 
    if ((c>'0') && (c<'9'))
    {
        backChar();
        curr_token = NUMBER;
        return getNumber(s);
    }
 
    return getName(s);
}
 
std::string __Parser::pop()
{
    std::string result = __Stack::pop();
    return getToken(result);
}
 
void __Parser::deleteSpaces(std::string s)
{
    for (uint16_t i = 0; i<s.length(); i++)
    {
        if (s[i] == ' ')
        {
            s.erase(i, 1);
        }
    }
}
 
std::string __Parser::toPolish(std::string &s)
{
    char_pos = 0;
    sign = true;
 
    int last = s.length() - 1;
    std::string result;
    std::string token_value;
    __Stack::clear();
 
    using __Stack::push;
    while (char_pos != last)
    {
        token_value = getToken(s);
        switch (curr_token)
        {
            case NUMBER:
            {
                sign = false;
                result += token_value + " ";
                break;
            }
 
            case L_BRUNCH:
            {
                sign = true;
                push(token_value);
                break;
            }
 
            case R_BRUNCH:
            {
                sign = false;
                while (true)
                {
                    token_value = pop();
                    if (curr_token == L_BRUNCH)
                    {
                        break;
                    }
                    result += token_value + " ";
                }
                break;
            }
 
            case PLUS:{} case MINUS:{} case MUL:{}
            case DIV:{}  case POW:{}   case SQRT:{}
            case FUNC:
            {
                if (curr_token == MINUS)
                {
                    if (sign)
                    {
                        curr_token = U_MINUS;
                    }
                }
                sign = false;
                eTokens tok = curr_token;
                std::string buff;
                while (true)
                {
                    buff = pop();
                    if (token_priority[curr_token]>=token_priority[tok])
                    {
                        result += buff + " ";
                    }
                    else
                    {
                        break;
                    }
                }
                push(buff);
                push(token_value);
                break;
            }
 
            case NAME:
            {
                sign = false;
                result += token_value + " ";
                break;
            }
 
            default:
            {
                throw Error("ошибка: неизвестный токен", char_pos);
                break;
            }
        }
    }
 
    return result;
}
 
std::string Parser::toPolish(std::string s)
{
    __Parser::deleteSpaces(s);
    return __Parser::toPolish(s);
}

#include <iostream>
#include <string>
#include "parser.h"
 
using namespace std;
 
int main()
{
    cout << Parser::toPolish("x + 2");
}

class function
{
public:
    virtual int priority()const=0;//приоритет операции
    virtual double calculate()const=0;//вычисление операции
protected:
    function*left=nullptr;//левый аргумент
    function*right=nullptr;//правый аргумент
};
class sum:public function
{
public:
    int priority()const{return 1;}
    double calculate()const{return left->calculate()+right->calculate();}
};

stringstream stream("1234 5678");//превратили текст в поток
int x,y;
stream>>x>>y;//прочитали текст из потока
cout<<x<<" "<<y<<endl;

    case PLUS: return [&, left, right]() { return left() + right(); };

void add_node(function*root,//корень дерева
    function*newnode//добавляемая операция
)
{
    //ищем самый правый узел дерева с приоритетом ниже добавляемой операции
    while(root->right&&root->right->priority()<newnode->priority())
        root=root->right;
    //правый аргумент найденного узла захватывает новая операция
    newnode->left=root->right;
    //и сама становится этим аргументом
    root->right=newnode;
}

AnsiString DeleteUnusableBarsets(AnsiString Function) {
    AnsiString Temp = Function;
    do {
        if (Temp[1] != '(' || Temp[Temp.Length()] != ')')
            return Temp;
        int BarsetCount = 0;
        bool BarsetExist = false;
        for (int i = 1; i < Temp.Length() - 1; i++)
            if (Temp[i] == '(') {
                BarsetCount++;
                BarsetExist = true;
            }
            else if (Temp[i] == ')') {
                BarsetCount--;
                if (!BarsetCount && BarsetExist)
                    return Temp;
            }
        Temp = Temp.SubString(2, Temp.Length() - 2);
    }
    while (1);
}
 
TDelimeterType __fastcall FindDelimeter(AnsiString Function, int *OperationType,
    int *Start, int *End) {
    *OperationType = otNone;
    for (int i = 0; i < 12; i++) {
        int BarsetCount = 0;
        for (int j = 1; j <= Function.Length(); j++)
            if (Function[j] == '(')
                BarsetCount++;
            else if (Function[j] == ')')
                BarsetCount--;
            else if (Function[j] == Delimeters[i] && !BarsetCount) {
                *Start = j - 1;
                *OperationType = i + 1;
                *End = j + 1;
                return dtBinarOperation;
            }
    }
    for (int i = 0; i < 10; i++)
        if (Function.AnsiPos(FunctionNames[i] + "(") == 1) {
            *Start = 1;
            *OperationType = i + otSin;
            *End = FunctionNames[i].Length();
            return dtUnarOperation;
        }
    return dtNone;
}
 
TTreeElement* __fastcall CreateTree(AnsiString aFunction, double **Variables) {
    if (!aFunction.Length())
        return NULL;
    AnsiString Function = aFunction.UpperCase();
    Function = DeleteUnusableBarsets(Function);
    int Start, End, Temp;
    int OperationType;
    TTreeElement *ret;
    switch (FindDelimeter(Function, &OperationType, &Start, &End)) {
    case dtNone:
        if ((Temp = CheckVariable(Function)) > -1)
            return new TVariable(Variables, Temp);
        else if ((Temp = CheckConstant(Function)) > -1)
            return new TConstant(Constants[Temp]);
        else {
            return new TConstant(StrToFloat(Function));
        }
    case dtBinarOperation: {
            AnsiString t1 = Function.SubString(1, Start);
            AnsiString t2 =
                Function.SubString(End, Function.Length() - End + 2);
            switch (OperationType) {
            case otLet:
                if ((Temp = CheckVariable(t1)) > -1) {
                    ret = new TLet(Variables, Temp);
                    ret->LeftNode = CreateTree(t2, Variables);
                    ret->RightNode = NULL;
                    return ret;
                }
                else
                    throw Exception("Unknown identifier '" + t1 + "'");
            case otOr:
                ret = new TOr();
                break;
            case otAnd:
                ret = new TAnd();
                break;
            case otAbove:
                ret = new TAbove();
                break;
            case otBelow:
                ret = new TBelow();
                break;
            case otEqual:
                ret = new TEqual();
                break;
            case otAdd:
                ret = new TAddition();
                break;
            case otSub:
                ret = new TSubstraction();
                break;
            case otMul:
                ret = new TMultiplection();
                break;
            case otDiv:
                ret = new TDivision();
                break;
            case otPow:
                ret = new TPow();
                break;
            case otRoot:
                ret = new TRoot();
                break;
            }
            ret->LeftNode = CreateTree(t1, Variables);
            ret->RightNode = CreateTree(t2, Variables);
            return ret;
        }
    case dtUnarOperation: {
            TFunction *ret1 = new TFunction();
            AnsiString t1 = Function.SubString(End + 1,
                Function.Length() - End);
            switch (OperationType) {
            case otSin:
                ret1->OnCalc = sin;
                break;
            case otCos:
                ret1->OnCalc = cos;
                break;
            case otTg:
                ret1->OnCalc = tan;
                break;
            case otCtg:
                ret1->OnCalc = ctg;
                break;
            case otArcsin:
                ret1->OnCalc = asin;
                break;
            case otArccos:
                ret1->OnCalc = acos;
                break;
            case otArctg:
                ret1->OnCalc = atan;
                break;
            case otArcctg:
                ret1->OnCalc = actg;
                break;
            case otLn:
                ret1->OnCalc = log;
                break;
            case otLog:
                ret1->OnCalc = log10;
                break;
            }
            ret1->LeftNode = CreateTree(t1, Variables);
            ret1->RightNode = NULL;
            return ret1;
        }
    }
 
    return NULL;
}

#ifndef FUNC_TREE_H_INCLUDED
#define FUNC_TREE_H_INCLUDED
 
#include <math.h>
#include <string>
#include <iostream>
 
//pi / 180
const double TO_RAD_KOEF = 0.017453292519;
 
class Func
{
    public:
        virtual int priority() = 0;
        virtual double calculate(double x) = 0;
 
        Func *left = nullptr;
        Func *right = nullptr;
};
 
class Root : public Func
{
    public:
        int priority() {return 665;}
        double calculate(double x) {return right->calculate(x);}
};
 
class Add : public Func
{
    public:
        int priority() {return 1;}
        double calculate(double x) {return left->calculate(x) + right->calculate(x);}
};
 
class Sub : public Func
{
    public:
        int priority() {return 1;}
        double calculate(double x) {return left->calculate(x) - right->calculate(x);}
};
 
class Mul : public Func
{
    public:
        int priority() {return 2;}
        double calculate(double x) {return left->calculate(x) * right->calculate(x);}
};
 
class Div : public Func
{
    public:
        int priority() {return 2;}
        double calculate(double x) {return left->calculate(x) / right->calculate(x);}
};
 
class Power : public Func
{
    public:
        int priority() {return 3;}
        double calculate(double x) {return pow(left->calculate(x), right->calculate(x));}
};
 
class Sqrt : public Func
{
    public:
        int priority() {return 3;}
        double calculate(double x) {return pow(left->calculate(x), 1.0/right->calculate(x));}
};
 
inline double toRad(double deg)
{
    return TO_RAD_KOEF * deg;
}
 
class Sinus : public Func
{
    public:
        int priority() {return 3;}
        double calculate(double x) {return sin(toRad(right->calculate(x)));}
};
 
class Cosinus : public Func
{
    public:
        int priority() {return 3;}
        double calculate(double x) {return cos(toRad(right->calculate(x)));}
};
 
class Ln : public Func
{
    public:
        int priority() {return 3;}
        double calculate(double x) {return log(right->calculate(x));}
};
 
class Number : public Func
{
    double value;
 
    public:
        Number(double v) {this->value = v;}
        int priority() {return 666;}
        double calculate(double x) {return value;}
};
 
class Name : public Func
{
    std::string value;
    public:
        Name(std::string s) {this->value = s;}
        int priority() {return 666;}
        double calculate(double x) {return x;}
};
 
class Expression
{
    Root *root;
    static uint8_t const functions_count = 3;
    std::string functions_exist[functions_count] = {"sin", "cos", "ln"};
 
    void addNode(Func *root, Func *new_node);
    double getNumber(std::string &, uint16_t &);
    std::string getName(std::string &, uint16_t &);
    bool findFunction(std::string &, Func *root);
    Root *makeTree(std::string &s, uint16_t &curr_pos);
    void deleteTree(Func *node);
 
    public:
        Expression(std::string, uint16_t curr_pos = 0);
        ~Expression() {deleteTree(root);}
 
        double calculate(double);
};
 
#endif // FUNC_TREE_H_INCLUDED

#include "calculator.h"
 
void Expression::addNode(Func *root, Func *new_node)
{
    while (root->right && (root->right->priority() < new_node->priority()))
    {
        root = root->right;
    }
    new_node->left = root->right;
    root->right = new_node;
}
 
double Expression::getNumber(std::string &s, uint16_t &curr_pos)
{
    double result = 0;
 
    char c = s[curr_pos++];
    while ((c>='0') && (c<='9'))
    {
        result *= 10;
        result += (c - '0');
        if (curr_pos == s.length())
        {
            return result;
        }
        c = s[curr_pos++];
    }
 
    if (c == '.')
    {
        double decimal = 0;
        c = s[curr_pos++];
        while ((c>='0') && (c<='9'))
        {
            decimal += (c - '0');
            decimal /= 10.0;
            if (curr_pos == s.length())
            {
                return result;
            }
            c = s[curr_pos++];
        }
 
        result += decimal;
    }
    curr_pos--;
 
    return result;
}
 
Expression::Expression(std::string s, uint16_t curr_pos)
{
    root = makeTree(s, curr_pos);
}
 
std::string Expression::getName(std::string &s, uint16_t &curr_pos)
{
    std::string result;
    char c = s[curr_pos++];
    bool end_str = false;
 
    while (isalpha(c))
    {
        result += c;
        if (curr_pos == s.length())
        {
            end_str = true;
            break;
        }
        c = s[curr_pos++];
    }
    if (!end_str)
    {
        curr_pos--;
    }
 
    return result;
}
 
bool Expression::findFunction(std::string &s, Func *root)
{
    uint8_t i;
    for (i = 0; i<functions_count; i++)
    {
        if (functions_exist[i] == s)
        {
            break;
        }
    }
 
    switch (i)
    {
        case 0:
        {
            Sinus *sinus = new Sinus();
            addNode(root, sinus);
            break;
        }
 
        case 1:
        {
            Cosinus *cosinus = new Cosinus();
            addNode(root, cosinus);
            break;
        }
 
        case 2:
        {
            Ln *ln = new Ln();
            addNode(root, ln);
            break;
        }
 
        default:
        {
            return false;
        }
    }
 
    return true;
}
 
Root * Expression::makeTree(std::string &s, uint16_t &curr_pos)
{
    Root *root = new Root();
 
    while (curr_pos < s.length())
    {
        char c = s[curr_pos++];
        switch (c)
        {
            case '+':
            {
                Add *add = new Add();
                addNode(root, add);
                break;
            }
 
            case '-':
            {
                Sub *sub = new Sub();
                addNode(root, sub);
                break;
            }
 
            case '*':
            {
                Mul *mul = new Mul();
                addNode(root, mul);
                break;
            }
 
            case '/':
            {
                Div *div = new Div();
                addNode(root, div);
                break;
            }
 
            case '^':
            {
                Power *power = new Power();
                addNode(root, power);
                break;
            }
 
            case '\\':
            {
                Sqrt *sqrt = new Sqrt();
                addNode(root, sqrt);
                break;
            }
 
            case '(':
            {
                Root *tmp = makeTree(s, curr_pos);
                addNode(root, tmp);
                break;
            }
 
            case ')':
            {
                return root;
            }
 
            case ',':
            {
                s.erase(--curr_pos, 1);
                s.insert(curr_pos, ")(");
                break;
            }
 
            default:
            {
                if ((c>='0') && (c<='9'))
                {
                    curr_pos--;
                    Number *number = new Number(getNumber(s, curr_pos));
                    addNode(root, number);
                    break;
                }
                if (c == ' ')
                {
                    break;
                }
 
                curr_pos--;
                std::string tmp = getName(s, curr_pos);
                if (!findFunction(tmp, root))
                {
                    Name *name = new Name(tmp);
                    addNode(root, name);
                }
                break;
            }
        }
    }
 
    return root;
}
 
void Expression::deleteTree(Func *node)
{
    if (node->right != nullptr)
    {
        deleteTree(node->right);
    }
    if (node->left != nullptr)
    {
        deleteTree(node->left);
    }
 
    delete node;
}
 
double Expression::calculate(double x)
{
    return root->calculate(x);
}

const double TO_RAD_KOEF = 0.017453292519;