#pragma once
#include<iostream>
#include<string>
using namespace std;
template <class ATOM>
	struct NOD {

		ATOM data;
		NOD *succ;
	};
	using namespace std;
	template<class ATOM>
	NOD<ATOM> *addNod(ATOM val)
	{
		NOD<ATOM> *x = 0;
		x = new NOD<ATOM>;
		x->data = val;
		x->succ = 0;
		return x;
	}
	template <typename ATOM>
	void PUSH(NOD<ATOM> *&stack, ATOM val)
	{
		NOD<ATOM> *p = 0;
		if (isEmpty <ATOM>(stack))
		{
			stack = addNod <ATOM>(val);
		}
		else
		{
			p = addNod <ATOM>(val);
			p->succ = stack;
			stack = p;
		}
	}
	template <typename ATOM>
	void initStack(NOD<ATOM> *&stack)
	{
		stack = NULL;
	}
	template <typename ATOM>
	bool isEmpty(NOD<ATOM> *&stack)
	{
		return(stack == NULL);
	}
	template <typename ATOM>
	bool POP(NOD<ATOM> *&stack, ATOM &val)
	{
		NOD<ATOM> *p = stack;
		if (!isEmpty <ATOM>(stack))
		{
			val = p->data;
			stack = stack->succ;
			delete p;
			return 1;
		}
		return 0;
	}
	template <typename ATOM>
	bool top(NOD<ATOM> *&stack, ATOM &val)
	{
		if (!isEmpty <ATOM>(stack))
		{
			val = stack->data;
			return 1;
		}
		return 0;
	}
	template <typename ATOM>
	void afisare(NOD<ATOM> *stack)
	{
		NOD<ATOM> *p = stack;
		cout << "Stiva mea este:";
		while (stack)
		{
			cout << p->data << " ";
			p = p->succ;
		}
	}
	template <typename ATOM>
	ATOM topv(NOD<ATOM> *stack)
	{
		ATOM val;
		if (!isEmpty<ATOM>(stack))
		{
			val = stack->data;
			return val;
		}
		return NULL;
	}
	template<typename ATOM>
	string fp(string str)
	{

		string out;
		NOD<ATOM> * stack;
		initStack<ATOM>(stack);
		PUSH(stack, '#');
		for (int i = 0;i < str.size();++i)
		{
			if (str[i] == '(')
			{
				PUSH<ATOM>(stack, '(');
			}
			else
				if (isdigit(str[i]))
				{
					out += str[i];
				}
				else
					if (str[i] == ')')
					{
						while (topv<ATOM>(stack) != '(')
						{
							ATOM val;
							int temp = POP<ATOM>(stack, val);
							if (temp)
								out += val;
						}
						ATOM rez;
						bool temp = POP<ATOM>(stack, rez);
					}
					else
					{
						while (!isEmpty<ATOM>(stack) && prior(str[i]) <= priorStack(topv(stack)) && (stack->data != '#') && (stack->data != '('))
						{
							ATOM val;
							val = topv<ATOM>(stack);
							if (prior(val) <= priorStack(topv<ATOM>(stack)))
							{

								int temp = POP<ATOM>(stack, val);
								if (temp)
									out += val;

							}

						}
						PUSH<ATOM>(stack, str[i]);
					}
		}
		while (topv<ATOM>(stack) != '#')
		{
			ATOM val;
			int temp = POP<ATOM>(stack, val);
			if (temp)
				out += val;
		}
		return out;
	}

	string digits()
	{
		string x;
		char cnt;

		do
		{
			cin >> cnt;
			if (cnt != '0')
			{
				x += cnt;
			}
		} while (cnt != '0');
		return x;
	}
	int prior(char c)
	{
		if (c == '(')
			return 3;
		if ((c == '*') || (c == '/'))
			return 2;
		if ((c == '+') && (c == '-'))
			return 1;
		return -1;
	}
	int priorStack(char c)
	{
		if (c == '(')
			return 0;
		if ((c == '*') || (c == '/'))
			return 2;
		if ((c == '+') && (c == '-'))
			return 1;
		return -1;
	}
	template<typename ATOM>
	double calcul(string out)
	{
		NOD<ATOM> * stack;
		ATOM ret;
		initStack<ATOM>(stack);
		PUSH<ATOM>(stack, 0);
		for (int i = 0;i < out.size();++i)
		{
			if (isdigit(out[i]))
			{
				int ia = (out[i] - '0') % 48;
				PUSH<ATOM>(stack, (ATOM)ia);
			}
			else
			{
				ATOM a, b;
				if (!isEmpty<ATOM>(stack) && topv<ATOM>(stack) != 0)
				{
					bool temp;
					temp = POP<ATOM>(stack, a);
					temp = POP<ATOM>(stack, b);
					if (out[i] == '+')
					{
						ATOM aux = b + a;
						PUSH<ATOM>(stack, aux);
					}
					if (out[i] == '-')
					{
						ATOM aux = b - a;
						PUSH<ATOM>(stack, aux);
					}
					if (out[i] == '*')
					{
						ATOM aux= b * a;
						PUSH<ATOM>(stack, aux);
					}
					if (out[i] == '/')
					{
						ATOM aux = b / a;
						PUSH<ATOM>(stack, aux);
					}

				}
			}
		}

		if (!isEmpty<ATOM>(stack) && (topv<ATOM>(stack) != '#'))
		{
			bool k = POP<ATOM>(stack, ret);
		}
		return ret;
	}