SHARE
TWEET

Untitled

a guest Apr 18th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <ctype.h>
  5. #include <conio.h>
  6. #include <locale.h>
  7.  
  8. using namespace std;
  9.  
  10. enum Commands
  11. {
  12.    CMD_CALC = 1,
  13.    CMD_CALCREC, CMD_EXIT
  14. };
  15.  
  16. struct tree
  17. {
  18.    char elem;
  19.    tree *left, *right;
  20.  
  21.    tree(char _el = '%', tree *_left = NULL, tree *_right = NULL) :
  22.       elem(_el), left(_left), right(_right) {}
  23.  
  24. };
  25.  
  26. // stack of tree's pointers
  27. struct stack
  28. {
  29.    tree *elem;
  30.    bool w;
  31.    stack *next;
  32.  
  33.    stack(tree *_elem = NULL, bool _w = 0, stack *_next = NULL) : elem(_elem), w(_w), next(_next) {}
  34. };
  35.  
  36. // stack of ints
  37. struct stackv
  38. {
  39.    int el;
  40.    stackv *next;
  41.  
  42.    stackv(int _el = 0, stackv *_next = NULL) : el(_el), next(_next) {}
  43. };
  44.  
  45. const int Nmax = 100;
  46.  
  47. int input(char s[Nmax]);
  48. void output(int r, const char *n);
  49. void create(char s[Nmax], tree **m);
  50. void calc(tree *t, int *r);
  51. int calcrec(tree *t);
  52. void push(stack **s, tree *t, bool w);
  53. void pop(stack **s, tree **t, bool *w);
  54. void pushv(stackv **s, int v);
  55. void popv(stackv **s, int *v);
  56.  
  57. int main()
  58. {
  59.    setlocale(LC_CTYPE, "Russian");
  60.    tree *t = new tree;
  61.    int r;
  62.    char s[Nmax];
  63.  
  64.    if (input(s))
  65.    {
  66.       _getch();
  67.       return 0;
  68.    }
  69.  
  70.    create(s, &t);
  71.  
  72.    int exitFlag = 0, n = 0;
  73.    do
  74.    {
  75.       printf_s("1. Вычисление дерева без рекурсии  \n");
  76.       printf_s("2. Вычисление дерева с помощью рекурсии  \n");
  77.       printf_s("3. Выход из программы  \n");
  78.       int repeatFlag = 0;
  79.       do
  80.       {
  81.          printf_s("Введите номер команды (от 1 до 3): ");
  82.          if (!scanf_s("%d", &n))
  83.          {
  84.             printf_s("ошибка ввода");
  85.             _getch();
  86.          }
  87.          switch (n)
  88.          {
  89.             case CMD_CALC:
  90.                calc(t, &r);
  91.                output(r, "out.txt");
  92.                break;
  93.  
  94.             case CMD_CALCREC:
  95.                r = calcrec(t);
  96.                output(r, "outrec.txt");
  97.                break;
  98.  
  99.             case CMD_EXIT: exitFlag = 1;
  100.                break;
  101.  
  102.             default: printf_s("Ошибка: неверный номер команды\n");
  103.                repeatFlag = 1;
  104.             }
  105.       } while (!repeatFlag && !exitFlag);
  106.    } while (!exitFlag);
  107.    
  108.    return 0;
  109. }
  110.  
  111. int input(char s[Nmax])
  112. {
  113.    FILE *f;
  114.    fopen_s(&f, "in.txt", "r");
  115.    fgets(s, Nmax, f);
  116.    fclose(f);
  117.  
  118.    bool w = false;
  119.    int len = strlen(s), c = 0, o = 0, b = 0;
  120.    for (int i = 0; i < len; i++)
  121.    {      
  122.       switch (s[i])
  123.       {
  124.       case '(': c++; b++; break;
  125.       case ')': c--; break;
  126.       case '+':
  127.       case '-':
  128.       case '*': o++; break;
  129.       default: {}
  130.       }
  131.  
  132.       if (c < 0)
  133.       {
  134.          printf("The left bracket is expected");
  135.          return 1;
  136.       }
  137.  
  138.       if (!c && i != len - 1)
  139.          w = true;
  140.    }
  141.  
  142.    if (c > 0)
  143.    {
  144.       printf("The right bracket is expected");
  145.       return 1;
  146.    }
  147.  
  148.    if (w)
  149.    {
  150.       printf("Wrong arrangement of brackets");
  151.       return 1;
  152.    }
  153.  
  154.    if (o != b)
  155.    {
  156.       printf("The quantity of brackets does not correspond to the number of signs");
  157.       return 1;
  158.    }
  159.  
  160.    return 0;
  161. }
  162.  
  163. void output(int r, const char *n)
  164. {
  165.    FILE *f;
  166.    fopen_s(&f, n, "w");
  167.    fprintf_s(f, "%d", r);
  168.    fclose(f);
  169.    printf("Результат вычисления дерева: %d\n", r);
  170. }
  171.  
  172. // creating tree
  173. void create(char b[Nmax], tree **m)
  174. {
  175.    char x;
  176.    stack *s = NULL;
  177.    tree *t = *m;
  178.    bool w;
  179.  
  180.    /*char str[Nmax];
  181.    strcpy_s(str, _countof(str), b);
  182.    size_t _len = strlen(str);
  183.    size_t _size = sizeof(str);
  184.    size_t _count = _countof(str);*/
  185.  
  186.    int len = strlen(b);
  187.    if (len > 1)
  188.       for (int i = 1; i < len - 1; i++)
  189.          switch (b[i])
  190.          {
  191.             case '(':
  192.                push(&s, t, 0);
  193.                if (t->left)
  194.                {
  195.                   t->right = new tree;
  196.                   t = t->right;
  197.                }
  198.                else
  199.                {
  200.                   t->left = new tree;
  201.                   t = t->left;
  202.                }
  203.             break;
  204.             case '+':
  205.             case '-':
  206.             case '*': t->elem = b[i]; break;
  207.             case ')': pop(&s, &t, &w); break;
  208.             default: t->elem != '%' ? t->right = new tree(b[i]) :
  209.                           t->left = new tree(b[i]);
  210.          }
  211.    else
  212.       *m = new tree(b[0]);
  213.  
  214. }
  215.  
  216. // calculation without recursion
  217. void calc(tree *t, int *p)
  218. {
  219.    stack *s = NULL;
  220.    stackv *b = NULL;
  221.    bool w;
  222.  
  223.    do
  224.    {
  225.       while(t)
  226.       {
  227.          push(&s, t, 0);
  228.          t = t->left;
  229.       }
  230.       if (s)
  231.       {
  232.          do
  233.          {
  234.             pop(&s, &t, &w);
  235.             if (w)
  236.             {
  237.                if (isdigit(t->elem))
  238.                   pushv(&b, t->elem - '0');
  239.                else
  240.                {
  241.                   int l, r;
  242.                   popv(&b, &r);
  243.                   popv(&b, &l);
  244.                   switch (t->elem)
  245.                   {
  246.                      case '+': pushv(&b, l + r); break;
  247.                      case '-': pushv(&b, l - r); break;
  248.                      case '*': pushv(&b, l * r); break;
  249.                      default: {}
  250.                   }
  251.                }
  252.             }
  253.          } while (w && s);
  254.          if (!w)
  255.          {
  256.             push(&s, t, 1);
  257.             t = t->right;
  258.          }
  259.       }
  260.    }
  261.    while (s);
  262.  
  263.    popv(&b, p);
  264. }
  265.  
  266. // calculation with recursion
  267. int calcrec(tree *t)
  268. {
  269.    int a, b;
  270.    if (t->left)
  271.       a = calcrec(t->left);
  272.  
  273.    if (t->right)
  274.       b = calcrec(t->right);
  275.  
  276.    if (isdigit(t->elem))
  277.       return t->elem - '0';
  278.  
  279.    switch (t->elem)
  280.    {
  281.       case '+': return a + b;
  282.       case '-': return a - b;
  283.       case '*': return a * b;
  284.       default: {}
  285.    }
  286. }
  287.  
  288. void push(stack **s, tree *t, bool w)
  289. {
  290.    *s = new stack(t, w, *s);
  291. }
  292.  
  293. void pop(stack **b, tree **t, bool *w)
  294. {
  295.    stack *s = *b;
  296.    *t = s->elem;
  297.    *w = s->w;
  298.    s = s->next;
  299.    delete *b;
  300.    *b = s;
  301. }
  302.  
  303. void pushv(stackv **s, int v)
  304. {
  305.    *s = new stackv(v, *s);
  306. }
  307.  
  308. void popv(stackv **b, int *v)
  309. {
  310.    stackv *s = *b;
  311.    *v = s->el;
  312.    s = s->next;
  313.    delete *b;
  314.    *b = s;
  315. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top