#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <cctype>�

using namespace std;


template <typename T>
T pop(stack<T> &s)
{
    T res = s.top();
    s.pop();
    return res;
}

enum tokentype { ttconst, ttvar, ttopbr, ttclbr, ttfun, ttop };
struct token
{
    string name;
    tokentype type;
    token(string n = " ", tokentype t = ttop)
    {
        name = n;
        type = t;
    }
    token(char n = ' ', tokentype t = ttop)
    {
        name = n;
        type = t;
    }
    void printToken()
    {
        cout << name.c_str() << " " << type;
        cout << endl;
    }
};

string termsymbol = "+-*/^()[]%!&|";
bool istermsymbol(char c)
{
    return termsymbol.find(c) != -1;

}

tokentype ExpressionFunctionOrVariable(string s)
{
    if (s.find("(") != -1) //(s == "sin" || s == "cos" || s == "tan" || s == "arcsin" || s == "arccos" || s == "arctan")
        return ttfun;
    return ttvar;
}

bool WhetherAStringIsANumber(string s)
{

    for (int i = 0; i < s.size(); i++)
        if (s[i] != '.' && isdigit(s[i]) == false)
            return false;
    return true;
}


vector<token> BuildToken(string s)   // "sin(x)+7*abc^13-9.3*acrtg(1)"
{
    //vector<token> TokenVec;
    vector<token> toks;
    size_t i = 0;
    s += " ";
    while (i < s.length())
    {
        if (s[i] == ' ')
        {
            i++;
            continue;
        }
        string tmp = "";
        do
        {
            tmp += s[i++];
        } while (istermsymbol(s[i - 1] || istermsymbol(s[i])));
        toks.push_back(token(tmp));
    }
    for (size_t i = 0; i < toks.size(); i++)
    {
        char tokchar = toks[i].name[0];
        if (isdigit(toks[i].name[0]))
            toks[i].type = ttconst;
        else if (tokchar == '(')
            toks[i].type = ttopbr;
        else if (tokchar == ')')
            toks[i].type = ttclbr;
        else if (isalpha(tokchar))
            if (i + 1 < toks.size() && toks[i + 1].name == "(")
                toks[i].type = ttfun;
            else
                toks[i].type = ttvar;
    }
    //for (int i = 0; i< s.size(); i++)
    //{
    //  if (istermsymbol(s[i]))
    //  {
    //      if (WhetherAStringIsANumber(tmp) && tmp != "")
    //          TokenVec.push_back(token(tmp, ttconst));
    //      else if (tmp != "")
    //          TokenVec.push_back(token(tmp, ExpressionFunctionOrVariable(tmp + s[i])));
    //      switch (s[i])
    //      {
    //      case '(':
    //          TokenVec.push_back(token(s[i], ttopbr));
    //          break;
    //      case ')':
    //          TokenVec.push_back(token(s[i], ttclbr));
    //          break;
    //      default:
    //          TokenVec.push_back(token(s[i], ttop));
    //          break;
    //      }
    //      tmp = "";

    //  }
    //  else
    //  {
    //      tmp += s[i];
    //      if (tmp.find(" ") != -1)
    //          tmp.erase(tmp.find(" "), 1);
    //  }
    //}

    return toks;
}

map<string, int> priority;

void BuildPriorityMap()
{
    priority["+"] = 10;
    priority["-"] = 10;
    priority["*"] = 20;
    priority["/"] = 20;
    priority["^"] = 30;

}

vector<token> Postfix(vector<token> toks)
{
    if (priority.empty())
        BuildPriorityMap();
    stack<token> s;
    vector<token> res;
    for (auto &t : toks)
    {
        switch (t.type)
        {
        case ttvar: case ttconst: res.push_back(t); break;
        case ttopbr: s.push(t); break;
        case ttclbr: while (s.top().type != ttopbr)
            res.push_back(pop(s));
            s.pop();
            break;
        case ttfun: s.push(t); break;
        case ttop:
            while (s.size() && (s.top().type == ttfun || (s.top().type == ttop && priority[s.top().name] >= priority[t.name])))
                res.push_back(pop(s));
            s.push(t);
        }
    }
    while (s.size())
        res.push_back(pop(s));
    return res;
}



/*double op_plus(stack<double> &S)
{
return  pop(S) + pop(S);

}*/

map<string, double(*)(stack<double> &)> functions;
void BuildFunctionMap()
{
    functions["+"] = [](stack<double> &s) {return pop(s) + pop(s); };
    functions["*"] = [](stack<double> &s) {return pop(s) * pop(s); };
    functions["-"] = [](stack<double> &s) {return -pop(s) + pop(s); };
    functions["/"] = [](stack<double> &s) {return pop(s) / pop(s); };
    functions["^"] = [](stack<double> &s) {auto p = pop(s);  return pow(pop(s), p); };
    functions["sin"] = [](stack<double> &s) {return sin(pop(s)); };
    functions["cos"] = [](stack<double> &s) {return cos(pop(s)); };
    //functions["!"] = [&f](stack<double> &s) -> int { return (n) ? pop(s)*f(pop(s) - 1) : 1; };
    //functions["^"] = [](stack<double> &s) {

}

void GetExpressionStream(istream &inp, string &expr, map<string, double> &vars)
{
    getline(inp, expr);
    while (!inp.eof())
    {
        string s;
        getline(inp, s);
        int pos = s.find('=');
        if (pos == -1)
            continue;
        //var.first_not_of(' ');
        vars[s.substr(0, pos)] = stod(s.substr(pos + 1, s.length() - pos));
    }
}

//double CalculatePostFix(vector<token> &postfix, map<string, double> &vars)
//{
//  // РЕАЛИЗОВАТЬ
//
//}

int main()
{
    //string s;
    //string expression;
    //ifstream file("test.txt");
    //bool key = true;
    //while (getline(file, s))
    //  if (key == true)
    //  {
    //      expression = s;
    //      key = false;
    //  }
    //  else
    //      variable[string(s, 0, s.find("="))] = atoi(string(s, s.find("="), s.size() - 1).c_str());

    //file.close();


    vector<token> T1;
    T1 = BuildToken("700 + sin(x) + 7 * abc ^ 13 - 9.3*acrtg(1)"); // ttconst, ttvar, ttopbr, ttclbr, ttfun, ttop  700+sin(x) + 7 * abc ^ 13 - 9.3*acrtg(1)
    cout << "700 + sin(x) + 7 * abc ^ 13 - 9.3*acrtg(1)"<< endl;;
    auto T2 = Postfix(T1);
    for (auto &t : T2)
    {
        cout << t.name << " ";
    }
    cout << endl;
    return 0;
}