SHARE
TWEET

Untitled

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