#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <map>
#include <string>
#include <cstdlib>
#include <sstream>
#include <math.h>
using namespace std;

typedef float Data;
/************************
* структура операции над числом
* c - символ операции
* prior - приоритет операции
*
*************************/
struct Operation
{
    char c;
    int prior;
};

/************************
* структура стека для чисел:
* top - индекс первого пустого элемента
* capacity - емкость стека
* a - указатель на массив данных
*************************/
struct sNum
{
    int top;
    int capacity;
    Data * a;
};

/************************
* структура стека для операций:
* top - индекс первого пустого элемента
* capacity - емкость стека
* a - указатель на массив данных
*************************/
struct sOp
{
    int top;
    int capacity;
    Operation * a;
};

//sNum methods
sNum * createsNum(int capacity);
Data popNum(sNum * s);
void printsNum(sNum * s);
void pushNum(sNum * s, Data x);
bool isEmpty(sNum * s);
bool isFull(sNum * s);
void destroysNum(sNum * s);

//sOp methods
sOp * createsOp(int capacity);
Operation popOp(sOp * s);
void printsOp(sOp * s);
void pushOp(sOp * s, Operation x);
bool isEmpty(sOp * s);
bool isFull(sOp * s);
void destroysNum(sOp * s);

#pragma region StackNumbers
/*****************************************
* void printsNum():
* параметры - sNum * s
* назначение - печать содержмиого стека.
*****************************************/
void printsNum(sNum * s)
{
    for (int i = 0; i < s->top; i++)
    {
        printf("%d ", s->a[i]);
    }

    cout << "\n";
}

/********************************************************************
* sNum * createsNum():
* параметры - int capacity
* назначение - cоздает стек, выделяя под него память динамически
*********************************************************************/
sNum * createsNum(int capacity)
{
    //sNum * sNum = (sNum*)malloc(sizeof(sNum) + (capacity - 1) * (sizeof(Data)));
    sNum * stack = (sNum*)malloc(sizeof(sNum));
    stack->top = 0;
    stack->capacity = capacity;
    stack->a = (Data*)malloc(capacity * sizeof(Data));
    return stack;
}

/**************************************************************
* void pushNum():
* параметры - sNum * s, Data x
* назначение - добавление элемента в стек на верхнюю позицию.
***************************************************************/
void pushNum(sNum * s, Data x)
{
    if (s->top >= s->capacity)
    {
        s->capacity += 10;
        //s = (sNum*)realloc(sizeof(sNum) + s->capacity * (sizeof(Data)));
        s->a = (Data*)realloc(s->a, (s->capacity) * sizeof(Data));
    }

    s->a[s->top] = x;
    s->top += 1;
}

/***********************************************
* Data popNum():
* параметры - sNum * s
* назначение - берет последний сверху элемент
***********************************************/
Data popNum(sNum * s)
{
    Data x = s->a[s->top - 1];
    //s->a[s->top - 1] = 0;
    s->top -= 1;
    return x;
}

/******************************************
* bool isEmpty():
* параметры - sNum * s
* назначение - проверка стека на пустоту
*******************************************/
bool isEmpty(sNum * s)
{
    return s->top == 0;
}

/******************************************
* bool isFull():
* параметры - sNum * s
* назначение - проверка стека на полноту
*******************************************/
bool isFull(sNum * s)
{
    return s->top == s->capacity;
}

/******************************************
* void destroysNum():
* параметры - sNum * s
* назначение - удаление стека из памяти
*******************************************/
void destroysNum(sNum * s)
{
    free(s->a);
    s->a = NULL;
    free(s);
}
#pragma endregion End

#pragma region StackOperations
void printsOp(sOp * s)
{
    for (int i = 0; i < s->top; i++)
    {
        printf("%c ", s->a[i].c);
        printf("%d ", s->a[i].prior);
    }

    cout << "\n";
}

sOp * createsOp(int capacity)
{
    //sNum * sNum = (sNum*)malloc(sizeof(sNum) + (capacity - 1) * (sizeof(Data)));
    sOp * stack = (sOp*)malloc(sizeof(sOp));
    stack->top = 0;
    stack->capacity = capacity;
    stack->a = (Operation*)malloc(capacity * sizeof(Operation));
    return stack;
}

void pushOp(sOp * s, Operation x)
{
    if (s->top >= s->capacity)
    {
        s->capacity += 10;
        //s = (sNum*)realloc(sizeof(sNum) + s->capacity * (sizeof(Data)));
        s->a = (Operation*)realloc(s->a, (s->capacity) * sizeof(Operation));
    }

    s->a[s->top].c = x.c;
    s->a[s->top].prior = x.prior;
    s->top += 1;
}

Operation popOp(sOp * s)
{
    Operation x = s->a[s->top - 1];
    //s->a[s->top - 1] = 0;
    s->top -= 1;
    return x;
}

bool isEmpty(sOp * s)
{
    return s->top == 0;
}

bool isFull(sOp * s)
{
    return s->top == s->capacity;
}

void destroysOp(sOp * s)
{
    free(s->a);
    s->a = NULL;
    free(s);
}
#pragma endregion End

#pragma region Others
/********************************************************
* bool isDigit():
* параметры - char * x
* назначение - проверка символа, является ли он числом
********************************************************/
bool isDigit(char * x)
{

    if (*x <= '9' && *x >= '0')
    {
        return true;
    }
    else
        return false;
}

/*****************************************
* float strToFloat():
* параметры - string s
* назначение - перевод строки во float.
******************************************/
float strToFloat(string s)
{
    string p1 = "", p2 = "";
    bool inp = true, start = false, go = false;
    int countD = 0;
    int pn1 = 0, pn2 = 0;
    float num;
    if (s.find('.'))
    {
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '.')
            {
                inp = false;
            }
            if (s[i] != '.' && inp)
            {
                p1 += s[i];
            }
            else if (!inp && s[i] != '.')
            {
                countD++;
                if (s[i] != '0' && !start) start = true;
                if (start)
                {
                    p2 += s[i];
                }
            }
        }

        istringstream ist1(p1);
        ist1 >> pn1;

        istringstream ist2(p2);
        ist2 >> pn2;

        num = (float)pn1 + (((float)pn2) / pow(10, countD));

    }
    else
    {
        istringstream ist1(p1);
        ist1 >> pn1;
        num = float(pn1);
    }

    return num;
}

/***************************************************************
* void calculate():
* параметры - sOp * ops, sNum * nums
* назначение - вытаскивает из стека два числа
* и операцию из другого и применяет ее к этим двум элементам.
* Потом результат кладет в стек с числами
****************************************************************/
void calculate(sOp * ops, sNum * nums)  // вытащить из стека два операнда и одну операцию из другого
{
    float a, b, res = 0;
    Operation op = popOp(ops);
    char sign = op.c;
    if (sign != '~')
    {
        a = popNum(nums);
        b = popNum(nums);

        switch (sign)
        {
        case '+':
            res = b + a;
            break;
        case '-':
            res = b - a;
            break;
        case '*':
            res = b * a;
            break;
        case '/':
            res = b / a;
            break;
        case '^':
            res = pow(b, a);
            break;
        }
    }
    else
    {
        a = popNum(nums);
        res = 0 - a;
    }

    op.c = NULL;
    op.prior = NULL;
    pushNum(nums, res);
}

/*************************************************************
* bool checkBrackets():
* параметры - string s
* назначение - проверяет введенное математическое выражение
* на правильную расстановку скобок.
***************************************************************/
bool checkBrackets(string s)
{
    int count = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(')
            count++;
        else if (s[i] == ')')
            count--;
    }

    if (count == 0)
        return true;
    else
        return false;
}

/*************************************************************
* void deleteBracket():
* параметры - sOp * s
* назначение - При встрече открывающей и закрывающей скобок
* нейтрализует их.
***************************************************************/
void deleteBracket(sOp * s)
{
    Operation op = popOp(s);
    op.c = NULL;
    op.prior = NULL;
}
#pragma endregion End
void main()
{
    map<char, int> dictOpsS = { { '@', 0 },
                                { '(', 1 },
                                { '*', 3 },
                                { '/', 3 },
                                { '%', 3 },
                                { '+', 2 },
                                { '-', 2 },
                                { '=', -1 },
                                { ')', 1 },
                                { '^', 4 },
                                { '~', 4 } };

    map<char, int> dictOpsComp = { { '@', 0 },
                                   { '(', 100 },
                                   { '*', 3 },
                                   { '/', 3 },
                                   { '%', 3 },
                                   { '+', 2 },
                                   { '-', 2 },
                                   { '=', -1 },
                                   { ')', 1 },
                                   { '^', 4 },
                                   { '~', 4 } };

    sOp * ops = createsOp(10);
    sNum * nums = createsNum(10);

    Operation temp;
    temp.prior = 0;
    temp.c = '@';
    pushOp(ops, temp);

    cout << "Enter the expression:\n";
    string exp;
    getline(cin, exp);

    string t = "";
    if (checkBrackets(exp) && exp != "")         //проверка на пустоту выражения и правильность постановки скобок.
    {
        for (int i = 0; i < exp.length(); i++)
        {
            if (exp[i] == ' ') continue;
            if (isDigit(&exp[i]) || exp[i] == '.')
            {
                t += exp[i];                        //получение числа
            }
            else
            {
                if (t != "") pushNum(nums, strToFloat(t));   //добавление в стек элемента и перевод его во float
                t = "";                                     //делаю пустым буфер для числа
                if (dictOpsComp[exp[i]] > ops->a[ops->top - 1].prior && dictOpsComp.count(exp[i]) != 0)        //если приоритет операции в списке "сравнения" больше, чем приоритет операции внутри стека, и эта операция есть в списке, в верх стека
                {
                    temp.prior = dictOpsS[exp[i]];
                    temp.c = exp[i];
                    pushOp(ops, temp);
                }
                else if (dictOpsComp[exp[i]] <= ops->a[ops->top - 1].prior && dictOpsComp.count(exp[i]) != 0)    //если приор. операции меньше или равен опер., находящейся в стеке, то пока приоритет текущей операции <= оп. в стеке,
                    //пока в стеке операндов есть 2 элемента, то вытаскивать из стека операндов 2 элемента, из стека операция одну операцию, применить ее по отношению к 2-м элементам и результат положить обратно в стек операндов.
                {
                    while (dictOpsComp[exp[i]] <= ops->a[ops->top - 1].prior && nums->top > 1 || ops->a[ops->top - 1].c == '~' && nums->top >0)  //1 условие на наличие 2 операндов, а второе на унарную операцию
                    {
                        calculate(ops, nums);
                        if (ops->a[ops->top - 1].c == '(' && exp[i] == ')')     //если последняя операция (, а текущая - ), то убрать текущую скобку и удалить левую скобку из стека операций.
                        {
                            deleteBracket(ops);
                            break;
                        }
                    }

                    if (exp[i] != ')')                //когда приоритет текущей операции все-таки станет больше последней операции в стеке, добавить текущую операцию в стек.
                    {
                        temp.prior = dictOpsS[exp[i]];
                        temp.c = exp[i];
                        pushOp(ops, temp);
                    }
                }
            }

        }

        float res = popNum(nums);
        cout << res;
    }
    else
    {
        cout << "2.Error of input, check brackets or fully of expression\n";
    }

    destroysNum(nums);    //освобождение памяти
    destroysOp(ops);
    getch();
}