#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <locale.h>

using namespace std;

enum Commands
{
   CMD_CALC = 1,
   CMD_CALCREC, CMD_EXIT
};

struct tree
{
   char elem;
   tree *left, *right;

   tree(char _el = '%', tree *_left = NULL, tree *_right = NULL) :
      elem(_el), left(_left), right(_right) {}

};

// stack of tree's pointers
struct stack
{
   tree *elem;
   bool w;
   stack *next;

   stack(tree *_elem = NULL, bool _w = 0, stack *_next = NULL) : elem(_elem), w(_w), next(_next) {}
};

// stack of ints
struct stackv
{
   int el;
   stackv *next;

   stackv(int _el = 0, stackv *_next = NULL) : el(_el), next(_next) {}
};

const int Nmax = 100;

int input(char s[Nmax]);
void output(int r, const char *n);
void create(char s[Nmax], tree **m);
void calc(tree *t, int *r);
int calcrec(tree *t);
void push(stack **s, tree *t, bool w);
void pop(stack **s, tree **t, bool *w);
void pushv(stackv **s, int v);
void popv(stackv **s, int *v);

int main()
{
   setlocale(LC_CTYPE, "Russian");
   tree *t = new tree;
   int r;
   char s[Nmax];

   if (input(s))
   {
      _getch();
      return 0;
   }

   create(s, &t);

   int exitFlag = 0, n = 0;
   do
   {
      printf_s("1. Вычисление дерева без рекурсии  \n");
      printf_s("2. Вычисление дерева с помощью рекурсии  \n");
      printf_s("3. Выход из программы  \n");
      int repeatFlag = 0;
      do
      {
         printf_s("Введите номер команды (от 1 до 3): ");
         if (!scanf_s("%d", &n))
         {
            printf_s("ошибка ввода");
            _getch();
         }
         switch (n)
         {
            case CMD_CALC:
               calc(t, &r);
               output(r, "out.txt");
               break;

            case CMD_CALCREC:
               r = calcrec(t);
               output(r, "outrec.txt");
               break;

            case CMD_EXIT: exitFlag = 1;
               break;

            default: printf_s("Ошибка: неверный номер команды\n");
               repeatFlag = 1;
            }
      } while (!repeatFlag && !exitFlag);
   } while (!exitFlag);

   return 0;
}

int input(char s[Nmax])
{
   FILE *f;
   fopen_s(&f, "in.txt", "r");
   fgets(s, Nmax, f);
   fclose(f);

   bool w = false;
   int len = strlen(s), c = 0, o = 0, b = 0;
   for (int i = 0; i < len; i++)
   {
      switch (s[i])
      {
      case '(': c++; b++; break;
      case ')': c--; break;
      case '+':
      case '-':
      case '*': o++; break;
      default: {}
      }

      if (c < 0)
      {
         printf("The left bracket is expected");
         return 1;
      }

      if (!c && i != len - 1)
         w = true;
   }

   if (c > 0)
   {
      printf("The right bracket is expected");
      return 1;
   }

   if (w)
   {
      printf("Wrong arrangement of brackets");
      return 1;
   }

   if (o != b)
   {
      printf("The quantity of brackets does not correspond to the number of signs");
      return 1;
   }

   return 0;
}

void output(int r, const char *n)
{
   FILE *f;
   fopen_s(&f, n, "w");
   fprintf_s(f, "%d", r);
   fclose(f);
   printf("Результат вычисления дерева: %d\n", r);
}

// creating tree
void create(char b[Nmax], tree **m)
{
   char x;
   stack *s = NULL;
   tree *t = *m;
   bool w;

   /*char str[Nmax];
   strcpy_s(str, _countof(str), b);
   size_t _len = strlen(str);
   size_t _size = sizeof(str);
   size_t _count = _countof(str);*/

   int len = strlen(b);
   if (len > 1)
      for (int i = 1; i < len - 1; i++)
         switch (b[i])
         {
            case '(':
               push(&s, t, 0);
               if (t->left)
               {
                  t->right = new tree;
                  t = t->right;
               }
               else
               {
                  t->left = new tree;
                  t = t->left;
               }
            break;
            case '+':
            case '-':
            case '*': t->elem = b[i]; break;
            case ')': pop(&s, &t, &w); break;
            default: t->elem != '%' ? t->right = new tree(b[i]) :
                          t->left = new tree(b[i]);
         }
   else
      *m = new tree(b[0]);

}

// calculation without recursion
void calc(tree *t, int *p)
{
   stack *s = NULL;
   stackv *b = NULL;
   bool w;

   do
   {
      while(t)
      {
         push(&s, t, 0);
         t = t->left;
      }
      if (s)
      {
         do
         {
            pop(&s, &t, &w);
            if (w)
            {
               if (isdigit(t->elem))
                  pushv(&b, t->elem - '0');
               else
               {
                  int l, r;
                  popv(&b, &r);
                  popv(&b, &l);
                  switch (t->elem)
                  {
                     case '+': pushv(&b, l + r); break;
                     case '-': pushv(&b, l - r); break;
                     case '*': pushv(&b, l * r); break;
                     default: {}
                  }
               }
            }
         } while (w && s);
         if (!w)
         {
            push(&s, t, 1);
            t = t->right;
         }
      }
   }
   while (s);

   popv(&b, p);
}

// calculation with recursion
int calcrec(tree *t)
{
   int a, b;
   if (t->left)
      a = calcrec(t->left);

   if (t->right)
      b = calcrec(t->right);

   if (isdigit(t->elem))
      return t->elem - '0';

   switch (t->elem)
   {
      case '+': return a + b;
      case '-': return a - b;
      case '*': return a * b;
      default: {}
   }
}

void push(stack **s, tree *t, bool w)
{
   *s = new stack(t, w, *s);
}

void pop(stack **b, tree **t, bool *w)
{
   stack *s = *b;
   *t = s->elem;
   *w = s->w;
   s = s->next;
   delete *b;
   *b = s;
}

void pushv(stackv **s, int v)
{
   *s = new stackv(v, *s);
}

void popv(stackv **b, int *v)
{
   stackv *s = *b;
   *v = s->el;
   s = s->next;
   delete *b;
   *b = s;
}