Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 65, средняя оценка - 4.75
helloworld
0 / 0 / 0
Регистрация: 17.05.2009
Сообщений: 6
#1

Представление выражения в двоичном дереве - C++

18.05.2009, 19:58. Просмотров 8047. Ответов 6
Метки нет (Все метки)

есть выражение 4*a/2 мне надо его упростить и получить 2*a
т.е. я ввожу в программу 4*a/2, программа должна представить выражение в виде двоичного дерева, провести с этим деревом такие преобразования, чтобы оно стало иметь вид, удовлетворяющий выражению 2*a, после этого дерево (с выражением 2*a) должно быть переведено обратно в выражение {т.е. я ввожу 4*a/2, программа выдаёт 2*a }

Помогите пожалуйста, очень трудно учиться программировать с таким преподавателем, какой достался нашей несчастной группе

п.с. мой код (в основном он касается перевода выражения в двочное дерево и обратно, нет той части кода, которая должна отвечать за трансформацию дерева


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
 
typedef char tdata;
 
 int i; char ch;
 
struct node;
 
typedef node *link;
 
struct node
{ tdata data;
  link left,right;
} *tree;
 
 
 
  void printtree(link t)
  { static int l=0;
    l++;
    if(t)
     { printtree(t->right);
       for(i=0;i<l;i++)printf("    ");
       printf("\\__%c\n",t->data);
       printtree(t->left);
     }
    l--;
   } // printtree----------------------------------
int isAN()
  { return ( ch >= 'a' ) && ( ch <= 'z' ) || ( ch >= '0' ) && ( ch <= '9' );}
 
 
 
  link mknode(char c, link &l, link &r)
  {
        link t = new node;
        t -> data = c;
        t -> left = l;
        t -> right = r;
        return t;
  }
  
  
  link expr();
 
  link fact()
  {
      link t;
      scanf("%c",&ch);
      if( ch == '(' )
      {
           t = expr();
           if(ch!=')') printf("ERROR: not )\n");
      }
      else if(isAN()) t = mknode(ch,0,0);
      else printf("ERROR: not AN\n");
      return t;
      
      
      link term()
    {
        link tm;
        int done;
        char ch1;
        tm = fact();
        done = 0;
        while((ch != '\n') && (!done))
        {
             scanf("%c",&ch);
             if ( ch == '/' ) { ch1 = ch; tm = mknode( ch1, tm, fact() ); }
             else done=1;
        }
        return tm;
     }
 
  
  link expr()
  {
      link ex;
      int done;
      char ch1;
      ex = term();
      done = 0;
      while( ( ch != '\n' ) && ( !done ) )
           {
            if( ch == '*' )  { ch1 = ch; ex = mknode( ch1, ex, term() ); }
            else done = 1;
           }
   return ex;
  }
Добавлено через 14 минут 12 секунд
п.с. сорри за офтоп: господа программисты, на чём вы компилите? На чём лучше работать новичку?(bC 3.1 не устанавливается )

Добавлено через 18 часов 57 минут 7 секунд
up
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2009, 19:58     Представление выражения в двоичном дереве
Посмотрите здесь:

C++ Unicode в двоичном формате
C++ Поиск в двоичном файле
C++ Подсчет уровней в двоичном дереве поиска
C++ В двоичном дереве удалить все узлы, значения которых является простым числом
Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение? C++
C++ Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?
Перестановка байтов в двоичном файле C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
18.05.2009, 21:12     Представление выражения в двоичном дереве #2
Тебе нужно сделать так называемые локальные преобразования.

Для начала возьмём простой пример: 2+2. Ты имеешь узел + и подвешенные к нему два узла с константами. В этом случае эту конструкцию ты сворачиваешь в один узел - константу, которая есть значение выражения (в данном случае 2+2). Для удобства построения более сложных вычислений заодно можно привести все узлы с ассоциативной операцией (т.е. где от перестановки аргументов результат не меняется - плюс и умножить) к виду, чтобы константа была вторым слагаемым

Более сложный случай - это когда к операции на один операнд подвешена константа, а на другой - операция с двумя константами. Тут надо в лоб анализировать все случи типа:
(VAR + CONST1) + CONST2 преобразуем в VAR + (CONST1 + CONST2), после чего сложение констант у тебя свернётся предыдущим правилом
(VAR * CONST1) / CONST2 -> VAR * (CONST1/CONST2)
и так далее
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
18.05.2009, 21:16     Представление выражения в двоичном дереве #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
В твоём коде сейчас разбираться несоклько лениво. Когда-то давно кому-то писал что-то по разбуру выражений, можешь посмотреть. Если интересует - завтра могу небольшое описание скинуть (я уже этот пример отдавал кому-то и там описание сделал, на работе должно валяться)
Вложения
Тип файла: rar expr.rar (4.4 Кб, 907 просмотров)
helloworld
0 / 0 / 0
Регистрация: 17.05.2009
Сообщений: 6
18.05.2009, 21:39  [ТС]     Представление выражения в двоичном дереве #4
Спасибо, буду очень признателен
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
19.05.2009, 10:37     Представление выражения в двоичном дереве #5
Пояснения к expr.rar

В общем делал кому-то курсовик. Суть программы была в том,
что нужно ввести выражение (с констатами, переменными, скбками).
Потом ввести значение всех переменных, оно должно посчитать
и выдать какую-то статистику по количеству всего.
Работает только в целых числах

Сейчас я бы немного по-другому написал, но как есть так есть.

Лексический разбор в файле parser.c. Выдёргивание идёт по
лексемам (лексическим единицам, которые здесь названы token).
На каждый вызов процедуры parser_GetToken формируется одна лексемма.
Процедура возвращает тип лексеммы: константа, идентификатор,
разделитель (операции и скобки) или конец файла, при этом текстовое
значение лексемы помещается в переменную parser_Token

Тебе нужно смотреть синтаксический разбор и построение дерева начиная
от процедуры expr_ParseExpr. Она выдирает по одной лексеме и согласно
синтаксическим правилам формирует дерево. Особенность этой схемы в том,
что мы всегда находимся в состоянии, когда текущая лексема прочитана.
Т.е. метод работы такой: в самом начале читаем первую лексему, потом шмонаемся
по синтаксическим правилам. Как только обработали текущую лексему, сразу же
вытаскиваем следующую (даже если она и не нужна). При разборе простых
выражений такое поведение возможно избыточно, но при более сложных
синтаксисах именно такой способ даёт техническую простоту при использовании
нисходящего разбора

Ну и в main.c раскомментируй вызов tree_PrintNode - там в отладочном виде
будет печататься дерево. Каждый узел печатается как: номер узла, тип узла
и номера узлов-детей (если это узел арифметической операции). Понятно дело,
что скобки в дереве никак не отражаются, ибо они нужны только на письме,
чтобы обозначить порядок выполнения операций
bystrov2323
Сообщений: n/a
13.06.2009, 15:30     Представление выражения в двоичном дереве #6
У кого-нибудь есть код этой проги, мне нужен на си, если нет может на паскале есть, буду очень благодарен, заранее спс.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.06.2009, 15:50     Представление выражения в двоичном дереве
Еще ссылки по теме:

C++ Реализация словаря в двоичном дереве поиска
Реализация словаря в двоичном дереве поиска C++
C++ Подсчёт нулей в двоичном коде
C++ Чтение файла в двоичном коде
C++ Поиск в двоичном дереве

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
13.06.2009, 15:50     Представление выражения в двоичном дереве #7
Цитата Сообщение от bystrov2323 Посмотреть сообщение
У кого-нибудь есть код этой проги, мне нужен на си, если нет может на паскале есть, буду очень благодарен, заранее спс.
Evg в посте #3 уже прикрепил исходник.
Yandex
Объявления
13.06.2009, 15:50     Представление выражения в двоичном дереве
Ответ Создать тему
Опции темы

Текущее время: 22:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru