Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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) {}
- };
- struct stack
- {
- tree *elem;
- bool w;
- stack *next;
- stack(tree *_elem = NULL, bool _w = 0, stack *_next = NULL) : elem(_elem), w(_w), next(_next) {}
- };
- 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);
- }
- 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]);
- }
- 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);
- }
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement