#include <iostream>
#include <iomanip>
#include <math.h>
#include <string>

using namespace std;

// TODO: obsluga wyjatkow!!!

enum State {StateStart, StateOperand, StateNumber, StateNumberPoint, StateNumberMantisa, StateNumberPowerSign, StateNumberPowerMinus, StateNumberPower, StateOperator, StateEnd, StateError};
enum Input {Eof, Space, Digit, Dot, E, Minus, Plus, Mul, OBr, CBr};
enum Ops { OpSub, OpAdd, OpMul, OpDiv, OpPow, OpNeg };
bool Debug = false;

class Stos
{
	public:
		class Element
		{
			private:
				double v;
				int w;
				Element * next;
			public:
				double vGet() const { return v;}
				int wGet() const { return w;}
				Element * nextGet() const { return next;}
                                void wSet(int a)    { w = a; }
				void vSet(double a) { v = a; }
				void nextSet(Element * a) { next = a; }
				Element():v(0), w(0), next(0) {};
				Element (const Element & a);
				Element (double a, int b): v(a), w(b), next(NULL) {}
                                Element & operator=(const Element &a);
                                void print() const { cout << "v: " << v << ", w: " << w; }
				friend ostream &operator<<(ostream &s,const Stos::Element &a);
		};
		Stos(): rozmiar(0), poczatek(NULL) {}
		~Stos();
		class Empty {};
		operator bool() const { return(poczatek); }
		Stos &operator<<(const Element a) { add(a); return(*this); }
		Stos &operator>>(Element & a) { rem(a); return(*this); }
		Element & operator[] (unsigned i) const;
		unsigned operator()() const { return rozmiar; }
		friend ostream &operator<<(ostream &s,const Stos &S);
		void remove(unsigned i);
		Element * last() const;
//                class Error
//                {
//                        class Empty {};
//                };
	private:
		unsigned rozmiar;
		Element * poczatek;
		void rem (Element &a);
		void add (const Element a);

};

Stos::Element * Stos::last() const
{
	if (!rozmiar)
	{
                return NULL;
//                throw Error::Empty;
	} else {
		return &((*this)[(*this)() - 1]);
	}
}

void Stos::remove (unsigned i)
{
	if (rozmiar == 0)
	{
		return;
	}
	if (i == 0)
	{
		Element * a = poczatek;
		poczatek = a->nextGet();
		delete a;
	} else if (i >= ((*this)() - 1)) {
		Element * a = &((*this)[(*this)() - 2]);
		delete a->nextGet();
		a->nextSet(NULL);
	} else {
		Element * toDelete = &((*this)[i]);
		Element * before = &((*this)[i-1]);
		before->nextSet(toDelete->nextGet());
		delete toDelete;
	}
	--rozmiar;
	return;
}

Stos::Element & Stos::operator[](unsigned i) const
{
	Stos::Element * p = poczatek;
	for (unsigned c = 0; c != i; c++)
	{
		p = p->nextGet();
	}
	return (*p);
	
}

Stos::Element::Element(const Element & a): v(a.vGet()), w(a.wGet()), next(a.nextGet())
{
}

Stos::Element & Stos::Element::operator=(const Element & a)
{
	w = a.w;
	v = a.v;
	next = a.next;
	return(*this);
}

Stos::~Stos()
{
	if (rozmiar == 0) return;
	return;
	cout << "Destruktor:" <<endl;
	cout << "	obecnie: " << (*this) << endl;
	while (poczatek)
	{
		cout << "	probuje skasowac: " << (*poczatek) << endl;
		Element *t = poczatek->nextGet();
		delete poczatek;
		poczatek = t;
	}
}

void Stos::add(const Element a)
{
	Element * N = new Element;
	(*N) = a;
	N->nextSet(NULL);
	if (rozmiar == 0)
	{
		poczatek = N;
	} else {
		Element * b = last();
		b->nextSet(N);
	}
	rozmiar++;
	return;
}

void Stos::rem(Element &a)
{
	if (!rozmiar) throw Empty();
	Element B = (*this)[(*this)() - 2];
	delete B.nextGet();
	B.nextSet(NULL);
	rozmiar--;
}

ostream &operator<<(ostream &s,const Stos::Element &a)
{
	return(s << "v: " << a.v << ", w: " << a.w);
}

ostream &operator<<(ostream &s,const Stos &S)
{
	s<<'{';
	Stos::Element *i=S.poczatek;
	if(i)
	{
		while(true)
		{
			s << '(' << (*i) << ')';
			i=i->nextGet();
			if(!i)break;
			s<<',';
		}
	}
	return(s<<'}');
}

struct UnivArgs
{
	Stos & stosA;
	Stos & stosB;
	unsigned i;
	unsigned & Position;
	int & nawiasy;
	char * wyrazenie;
};

struct TabRecord
{
	State NextState;
	void (*funkcja)(UnivArgs);
};

void ErrorDivByZero(void)
{
	cout << "Blad: proba dzielenia przez zero!" << endl;
	return;
}

void CmdClose(UnivArgs a)
{
	a.nawiasy -= 5;
	return;
}

void CmdOperator(UnivArgs a)
{
	double v = 0;
	int w = a.nawiasy;
	switch ((a.wyrazenie)[a.i])
	{
		case '-': w += 1; v = OpSub; break;
		case '+': w += 1; v = OpAdd; break;
		case '*': w += 2; v = OpMul; break;
		case '/': w += 2; v = OpDiv; break;
		case '^': w += 3; v = OpPow; break;
	}
	
	for (unsigned i = (a.stosB() - 1); (int)i > -1;)
	{
		if ((a.stosB[i].wGet() != -1) && (a.stosB[i].wGet() >= w))
		{
			a.stosA << a.stosB[i];
			a.stosB.remove(i);
			--i;
		} else {
			--i;
		}
	}
	a.stosB << Stos::Element(v, w);
	return;
}

void CmdNumber(UnivArgs a)
{
	unsigned from = a.Position;
	char buf[a.i - from + 1];
	unsigned j = 0;
	while (from < a.i)
	{
		buf[j++] = *(a.wyrazenie+(from++));
	}
	buf[j] = '\0';
	a.stosA << Stos::Element(strtod(buf, (char**)'\0'), -1);
	return;
}

void CmdEnd(UnivArgs a)
{
	for (unsigned i = (a.stosB() - 1); (int)i > -1;)
	{
		if (a.stosB[i].wGet() != -1)
		{
			a.stosA << a.stosB[i];
			a.stosB.remove(i);
			--i;
		} else {
			--i;
		}
	}
	return;
}

void CmdOpen(UnivArgs a)
{
	a.nawiasy += 5;
	return;
}

void CmdMinus(UnivArgs a)
{
	a.stosB << Stos::Element(OpNeg, 4 + a.nawiasy);
	return;
}

void CmdSaveStartPos(UnivArgs a)
{
	a.Position = a.i;
	return;
}

void StosWydruk(Stos & S)
{
	cout << ".--- Wydruk stosu ---v" << endl;
	unsigned rozm = S() - 1;
	for (unsigned i = 0; i <= rozm; ++i)
	{
		cout << "| ";
		if (S[i].wGet() == -1)
		{
			cout << "Push " << S[i].vGet() << endl;
		} else {
			if (S[i].vGet() == OpSub) { cout << "Sub"; }
			else if (S[i].vGet() == OpAdd) { cout << "Add"; }
			else if (S[i].vGet() == OpMul) { cout << "Mul"; }
			else if (S[i].vGet() == OpDiv) { cout << "Div"; }
			else if (S[i].vGet() == OpPow) { cout << "Pow"; }
			else if (S[i].vGet() == OpNeg) { cout << "Neg"; }
			cout << endl;
		}
	}
	cout << "`--------------------^" << endl;
	return;
}

char * PobierzWyrazenie(void)
{
	char * wyrazenie = new char[1];
	unsigned rozmWyr = 0;

	while(true)
	{
		char buf[10];

		cin.getline(buf, sizeof(buf));
		unsigned rozmBuf = strlen(buf);

		char * noweWyr = new char [rozmWyr + rozmBuf + 1];

		memcpy(noweWyr, wyrazenie, rozmWyr);
		memcpy(noweWyr + rozmWyr, buf, rozmBuf);
		rozmWyr += rozmBuf;
		delete[] wyrazenie;
		wyrazenie = noweWyr;
		if((signed)rozmBuf < cin.gcount()) break;
		cin.clear();
	}

	wyrazenie[rozmWyr] = '\0';
	return(wyrazenie);
}

bool WartoscWyrazu(Stos & A, Stos & B)
{
	for (unsigned i = (A() - 1); (int)i > -1 ; --i)
	{
		B << A[i];
		A.remove(i);
	}
	for (unsigned i = (B() - 1); (int)i > -1; B.remove(i), --i)
	{
		if (B[i].wGet() == -1)
		{
			A << B[i];
		} else {
			unsigned j = A() - 1;
			if (B[i].vGet() == OpNeg)
			{
				A[j].vSet(-(A[j].vGet()));
			} else {
				double wynik;
				double b = A[j].vGet();
				double a = A[j-1].vGet();
				if (B[i].vGet() == OpSub) { wynik = a - b; }
				else if (B[i].vGet() == OpAdd) { wynik = a + b; }
				else if (B[i].vGet() == OpMul) { wynik = a * b; }
				else if (B[i].vGet() == OpDiv) {
					if ( b == 0 )
					{
						ErrorDivByZero();
						return(false);
					}
					wynik = a / b;
				}
				else if (B[i].vGet() == OpPow) { wynik = pow(a, b); }
				A.remove(j--);
				A.remove(j--);
				A << Stos::Element(wynik, -1);
			}
		}
	}
	return(true);
}

void ErrorOnPosition(unsigned i)
{
	cout << "Blad:     ";
	for (unsigned j = 0; j < i; j++) cout << " ";
	cout << "^" << endl;
}

void CmdNone(UnivArgs a)
{
	return;
}

void CmdNumberAndEnd(UnivArgs a)
{
	CmdNumber(a);
	CmdEnd(a);
	return;
}

void CmdNumberAndOperator(UnivArgs a)
{
	CmdNumber(a);
	CmdOperator(a);
	return;
}

void CmdNumberAndClose(UnivArgs a)
{
	CmdNumber(a);
	CmdClose(a);
	return;
}

bool KonwertujWyrazenie(char * wyrazenie, Stos & stosA, Stos & stosB)
{
	State stan = StateStart;
	unsigned rozmWyr = strlen(wyrazenie);
	int nawiasy = 0;
	unsigned Position = 0;
	unsigned i = 0;
	TabRecord Tablica[StateError][CBr];

	for (unsigned x = 0; x <= StateEnd; ++x)
	{
		for (unsigned y = 0; y <= CBr; ++y)
		{
			Tablica[x][y].funkcja = &CmdNone;
			Tablica[x][y].NextState = StateError;
		}
	}

	Tablica[StateStart][Space].NextState = StateStart;
	Tablica[StateStart][Digit].NextState = StateNumber;
	Tablica[StateStart][Dot].NextState = StateNumberPoint;
	Tablica[StateStart][Minus].NextState = StateOperand;
	Tablica[StateStart][OBr].NextState = StateStart;
	Tablica[StateOperand][Space].NextState = StateOperand;
	Tablica[StateOperand][Digit].NextState = StateNumber;
	Tablica[StateOperand][Dot].NextState = StateNumberPoint;
	Tablica[StateOperand][OBr].NextState = StateOperand;
	Tablica[StateNumber][Eof].NextState = StateEnd;
	Tablica[StateNumber][Space].NextState = StateOperator;
	Tablica[StateNumber][Digit].NextState = StateNumber;
	Tablica[StateNumber][Dot].NextState = StateNumberMantisa;
	Tablica[StateNumber][E].NextState = StateNumberPowerSign;
	Tablica[StateNumber][Minus].NextState = StateOperand;
	Tablica[StateNumber][Plus].NextState = StateOperand;
	Tablica[StateNumber][Mul].NextState = StateStart;
	Tablica[StateNumber][CBr].NextState = StateOperator;
	Tablica[StateNumberPoint][Digit].NextState = StateNumberMantisa;
	Tablica[StateNumberMantisa][Eof].NextState = StateEnd;
	Tablica[StateNumberMantisa][Space].NextState = StateOperator;
	Tablica[StateNumberMantisa][Digit].NextState = StateNumberMantisa;
	Tablica[StateNumberMantisa][E].NextState = StateNumberPowerSign;
	Tablica[StateNumberMantisa][Minus].NextState = StateOperand;
	Tablica[StateNumberMantisa][Plus].NextState = StateOperand;
	Tablica[StateNumberMantisa][Mul].NextState = StateStart;
	Tablica[StateNumberMantisa][CBr].NextState = StateOperator;
	Tablica[StateNumberPowerSign][Digit].NextState = StateNumberPower;
	Tablica[StateNumberPowerSign][Minus].NextState = StateNumberPowerMinus;
	Tablica[StateNumberPowerMinus][Digit].NextState = StateNumberPower;
	Tablica[StateNumberPower][Eof].NextState = StateEnd;
	Tablica[StateNumberPower][Space].NextState = StateOperator;
	Tablica[StateNumberPower][Digit].NextState = StateNumberPower;
	Tablica[StateNumberPower][Minus].NextState = StateOperand;
	Tablica[StateNumberPower][Plus].NextState = StateOperand;
	Tablica[StateNumberPower][Mul].NextState = StateStart;
	Tablica[StateNumberPower][CBr].NextState = StateOperator;
	Tablica[StateOperator][Eof].NextState = StateEnd;
	Tablica[StateOperator][Space].NextState = StateOperator;
	Tablica[StateOperator][Minus].NextState = StateOperand;
	Tablica[StateOperator][Plus].NextState = StateOperand;
	Tablica[StateOperator][Mul].NextState = StateStart;
	Tablica[StateOperator][CBr].NextState = StateOperator;

	Tablica[StateStart][Digit].funkcja = &CmdSaveStartPos;
	Tablica[StateStart][Dot].funkcja = &CmdSaveStartPos;
	Tablica[StateStart][Minus].funkcja = &CmdMinus;
	Tablica[StateStart][OBr].funkcja = &CmdOpen;
	Tablica[StateOperand][Digit].funkcja = &CmdSaveStartPos;
	Tablica[StateOperand][Dot].funkcja = &CmdSaveStartPos;
	Tablica[StateOperand][OBr].funkcja = &CmdOpen;
	Tablica[StateNumber][Eof].funkcja = &CmdNumberAndEnd;
	Tablica[StateNumber][Space].funkcja = &CmdNumber;
	Tablica[StateNumber][Minus].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumber][Plus].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumber][Mul].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumber][CBr].funkcja = &CmdNumberAndClose;
	Tablica[StateNumberMantisa][Eof].funkcja = &CmdNumberAndEnd;
	Tablica[StateNumberMantisa][Space].funkcja = &CmdNumber;
	Tablica[StateNumberMantisa][Minus].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumberMantisa][Plus].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumberMantisa][Mul].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumberMantisa][CBr].funkcja = &CmdNumberAndClose;
	Tablica[StateNumberPower][Eof].funkcja = &CmdNumberAndEnd;
	Tablica[StateNumberPower][Space].funkcja = &CmdNumber;
	Tablica[StateNumberPower][Minus].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumberPower][Plus].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumberPower][Mul].funkcja = &CmdNumberAndOperator;
	Tablica[StateNumberPower][CBr].funkcja = &CmdNumberAndClose;
	Tablica[StateOperator][Eof].funkcja = &CmdEnd;
	Tablica[StateOperator][Minus].funkcja = &CmdOperator;
	Tablica[StateOperator][Plus].funkcja = &CmdOperator;
	Tablica[StateOperator][Mul].funkcja = &CmdOperator;
	Tablica[StateOperator][CBr].funkcja = &CmdClose;
	for (; i <= rozmWyr; i++)
	{
		Input in;
		switch (wyrazenie[i])
		{
			case '\0':
				in = Eof; break;
			case ' ':
			case '\t':
				in = Space; break;
			case '0':
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
				in = Digit; break;
			case '.':
				in = Dot; break;
			case 'E':
			case 'e':
				in = E; break;
			case '-':
				in = Minus; break;
			case '+':
				in = Plus; break;
			case '*':
			case '/':
			case '^':
				in = Mul; break;
			case '(':
				in = OBr; break;
			case ')':
				in = CBr; break;
			default:
				ErrorOnPosition(i);
				return(false);
				break;
		}

		UnivArgs argumenty = {stosA, stosB, i, Position, nawiasy, wyrazenie};
		Tablica[stan][in].funkcja(argumenty);
		stan = Tablica[stan][in].NextState;
		if ((nawiasy < 0) || (stan == StateError))
		{
			ErrorOnPosition(i);
			return(false);
		}
	}
	if (nawiasy != 0)
	{
		ErrorOnPosition(i - 1);
		return(false);
	}
	return(true);
}

void Koniec(void)
{
	cout << endl << "Dziekuje za korzystanie z programu." << endl;
	cout << "Maciej Korzen <maciek@korzen.org>. Grupa IZ204." << endl;
	cout << endl << "Nacisnij [Enter], aby zamknac okno.";
	cin.get();
	exit(0);
}

void Pomoc(void)
{
	cout << "Przydatne komendy:" << endl;
	cout << " ? - pomoc," << endl;
	cout << " ! - wyjscie z programu," << endl;
	cout << " # - debug." << endl;
	return;
}

void DebugSwitch(void)
{
	if (Debug == true)
	{
		cout << "Tryb debugowania wylaczony." << endl;
		Debug = false;
	} else {
		cout << "Tryb debugowania wlaczony." << endl;
		Debug = true;
	}
	return;
}

int main(void)
{
	cout << "Witamy w programie \'projekt0\'. Zyczymy milej pracy." << endl;
	Pomoc();
	char prompt[] = "projekt0> ";
	while(true)
	{
		unsigned Precyzja = 6;
		cout << prompt;
		char * wyrazenie = PobierzWyrazenie();
		if (wyrazenie[1] == '\0')
		{
			if (wyrazenie[0] == '!')
			{
				Koniec();
			} else if (wyrazenie[0] == '?') {
				Pomoc();
				continue;
			} else if (wyrazenie[0] == '#') {
				DebugSwitch();
				continue;
			}
		}
		Stos stosA = Stos();
		Stos stosB = Stos();
		if (KonwertujWyrazenie(wyrazenie, stosA, stosB) == false)
			continue;
		cout.setf(ios::fixed);
		if (Debug == true) StosWydruk(stosA);
		if (WartoscWyrazu(stosA, stosB) == false)
			continue;
		double w = stosA[0].vGet();
		cout << setprecision(Precyzja) << "Wynik: " <<  w << endl;
	}
	return(0);
}