SHARE
TWEET

Untitled

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