#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <algorithm>
#include <Windows.h>

using namespace std;

enum class ttype
{
	var,
	cnst,
	opbr,
	clbr,
	op,
	fun
};

const string delimiters = " +-*/()^";

USHORT prior(string term) //Приоритет операций
{
	return term == "+" || term == "-" ? 0
		: term == "*" || term == "/" ? 1
		: term == "^" ? 2 :
		term == "(" ? 3 : USHRT_MAX;
}

struct term
{
	string name;
	ttype type;
};

bool isDelimiter(char c)
{
	return find(begin(delimiters), end(delimiters), c) != end(delimiters);
}

vector<term> convertToTerms(string expr)
{
	expr += ' ';
	vector<term> terms;
	size_t i = 0;
	while (i < expr.length())
	{
		string t = "";
		if (expr[i] == ' ')
		{
			i++;
			continue;
		}
		do
		{
			t += expr[i++];
		} while (!isDelimiter(expr[i - 1]) && !isDelimiter(expr[i]));
		terms.push_back({ t,ttype::op });
	}
	for (size_t i = 0; i < terms.size(); i++)
	{
		char c = terms[i].name[0];
		if (c == '(')
		{
			terms[i].type = ttype::opbr;
		}

		else if (c == ')')
		{
			terms[i].type = ttype::clbr;
		}

		else if (isalpha(c))
		{
			if (i < terms.size() - 1 && terms[i + 1].name == "(")
			{
				terms[i].type = ttype::fun;
			}
			else
			{
				terms[i].type = ttype::var;
			}
		}
		else if (isdigit(c))
		{
			terms[i].type = ttype::cnst;
		}
	}
	return terms;
}

vector<term> convertToPostfix(const vector<term>& terms)
{
	stack<term> s;		//Префиксная запись реализуется через стек
	vector<term> res;	//Результирующая строка

	for (const auto& i : terms)
	{
		switch (i.type)
		{
		case ttype::cnst: //Если встречается константа или переменная или функция (sin,exp) то кладем сразу в результирующую строку
		case ttype::var:
		case ttype::fun:
			res.push_back(i);
			break;

		case ttype::opbr:	//Открывающую скобку с стек
			s.push(i);
			break;

		case ttype::clbr:	//Если встретилась закрывающая скобка, то вставляются все элементы из стека пока не найдется открывающая скобка
			while (s.top().type != ttype::opbr)
			{
				res.push_back(s.top());
				s.pop();
			}
			s.pop();
			break;

			/*
			Если операция o1
			1) пока на вершине стека префиксная функция…
			… ИЛИ операция на вершине стека приоритетнее o1
			… ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1
			… выталкиваем верхний элемент стека в выходную строку;
			2) помещаем операцию o1 в стек.
			*/
		case ttype::op:
			if (s.size())
			{
				while (s.top().type == ttype::op && prior(s.top().name) > prior(i.name) ||
					(prior(s.top().name) == prior(i.name) && prior(s.top().name) != 2))
				{
					res.push_back(s.top());
					s.pop();
				}
			}
			s.push(i);
			break;
		}
	}

	while (!s.empty()) //Весь оставшийся стек помещаем в конец результирующей строки
	{
		res.push_back(s.top());
		s.pop();
	}

	return res;
}

int main()
{
	const string expr = "abc+3.15*exp(2*cos(a-b/c)^(ab-c)+1.2)";
	auto terms = convertToTerms(expr);

	/*for (const auto& t : terms)
	{
		cout << t.name << "	" << static_cast<int>(t.type) << endl;
	}*/

	terms = convertToPostfix(terms);

	for (size_t i = 0; i < terms.size(); i++)
	{
		cout << terms[i].name << " ";
	}

	return 0;
}