#include <iostream>
#include <iomanip>

using namespace std;

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;

struct es
{
  es * prev;
  double v;
  int w;
  es * next;
};

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

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

es * StosNew()
{
  es * s = new es;
  s->w = NULL;
  s->v = NULL;
  s->next = s->prev = NULL;
  return s;
}

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

es * StosFindEnd(es * stos)
{
  es * p = stos;
  while (p->next != NULL) p = p->next;
  return p;
}

void StosPush(es * stos, double v, int w)
{
  es * p = StosFindEnd(stos);
  es * pn = new es;
  p->next = pn;
  pn->prev = p;
  pn->next = NULL;
  pn->v = v;
  pn->w = w;
  return;
}

void StosPop(es * stos)
{
  es * p = StosFindEnd(stos);
  if (p->prev == NULL) return;
  p = p->prev;
  delete p->next;
  p->next = NULL;
  return;
}

void StosRm(es * p)
{
  es * pp = p->prev;
  es * pn = p->next;
  if (pn == NULL)
  {
    pp->next = NULL;
  } else {
    pp->next = pn;
    pn->prev = pp;
  }
  delete p;
}

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 (es * p = StosFindEnd(a.stosB); p->prev != NULL;)
  {
    if ((p->w != -1) && ( p->w >= w))
    {
      StosPush(a.stosA, p->v, p->w);
      p = p->prev;
      StosRm(p->next);
    } else {
      p = p->prev;
    }
  }
  StosPush(a.stosB, 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';
  StosPush(a.stosA, strtod(buf, (char**)'\0'), -1);
  return;
}

void CmdEnd(UnivArgs a)
{
  es * p = StosFindEnd(a.stosB);
  while(p->prev != NULL)
  {
    if (p->w != -1)
    {
      StosPush(a.stosA, p->v, p->w);
      p = p->prev;
      StosRm(p->next);
    } else {
      p = p->prev;
    }
  }
  return;
}

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

void CmdMinus(UnivArgs a)
{
  StosPush(a.stosB, OpNeg, 4 + a.nawiasy);
  return;
}

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

void StosWydruk(es * stos)
{
  cout << ".--- Wydruk stosu ---v" << endl;
  for (es * p = stos->next; p != NULL; p = p->next)
  {
    cout << "| ";
    if (p->w == -1)
    {
      cout << "Push " << p->v << endl;
    } else {
      if (p->v == OpSub) { cout << "Sub"; }
      else if (p->v == OpAdd) { cout << "Add"; }
      else if (p->v == OpMul) { cout << "Mul"; }
      else if (p->v == OpDiv) { cout << "Div"; }
      else if (p->v == OpPow) { cout << "Pow"; }
      else if (p->v == 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(es * stosA, es * stosB)
{
  for (es * p = StosFindEnd(stosA); p->prev != NULL;)
  {
    StosPush(stosB, p->v, p->w);
    p = p->prev;
    StosPop(stosA);
  }
  for (es * p = StosFindEnd(stosB); p->prev != NULL; p = p->prev, StosPop(stosB))
  {
    if (p->w == -1)
    {
      StosPush(stosA, p->v, p->w);
    } else {
      es * q = StosFindEnd(stosA);
      if (p->v == OpNeg)
      {
        q->v = -(q->v);
      } else {
        double wynik;
        double B = q->v;
        double A = q->prev->v;
        if (p->v == OpSub) { wynik = A - B; }
        else if (p->v == OpAdd) { wynik = A + B; }
        else if (p->v == OpMul) { wynik = A * B; }
        else if (p->v == OpDiv) {
          if ( B == 0 )
          {
            ErrorDivByZero();
            return(false);
          }
          wynik = A / B;
        }
        else if (p->v == OpPow) { wynik = pow(A, B); }
        StosPop(stosA);
        StosPop(stosA);
        StosPush(stosA, 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, es * stosA, es * 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 <eaquer@ceti.pl>." << 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;
      }
    }

    es * stosA = StosNew();
    es * stosB = StosNew();

    if (KonwertujWyrazenie(wyrazenie, stosA, stosB) == false)
      continue;

    cout.setf(ios::fixed);

    if (Debug == true) StosWydruk(stosA);

    if (WartoscWyrazu(stosA, stosB) == false)
      continue;

    cout << setprecision(Precyzja) << "Wynik: " << stosA->next->v << endl;
  }
  return(0);
}