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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 48, средняя оценка - 4.92
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
#1

Програмирование упращения логических выражений - C++

25.12.2010, 10:10. Просмотров 7201. Ответов 34
Метки нет (Все метки)

Что прошу:
программа | каркас | идея | помощь
На свой выбор и умение прошу помочь.
Что нужно:
Программа которая сможет упрощать введенные логические функции (булевы функции). Приводить их к компактному виду, преобразовывать сокращать.
Есть программа на делфи (нету исходника) - ссылка
Отличная статья по законам алгебры логики и законами преобразования - ссылка

Задача: повторить функционал программы или помочь с мат.моделью программы. Возможно буду выполнять на флеше с возможностью работы онлайн.
Почему выбрал с++ как место для создания темы - если мне напишут исходник на с++, для меня будет проще всего разобраться в коде.

Добавлено через 11 часов 9 минут
странно, может плохо описал задачу?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2010, 10:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Програмирование упращения логических выражений (C++):

Составление логических выражений - C++
я чайник если есть решение - напишите. Буду благодарен Составление логических выражений Составить линейную программу, печатающую...

Вычисление логических выражений - C++
написать программу позволяющую вывести на экран,значение след. логических выражений. логические выражения получились,вот а) !A || !B ...

Запись логических выражений - C++
как сделать проверку && и || в одном if for(;i>0; i--) { if(a>0 && (b <0 || c<0 || d<0) z=0; } куда выходит...

Построение простых логических выражений - C++
Помогите пожалуйста. Написать программу, проверяющую принадлежность точки с координатами(х,у) заштрихованной области на плоскости

Компилятор арифметико-логических выражений - C++
Всем привет. Люди может кто поможет написать или уже может есть такое, Компилятор арифметико-логических выражений))) В поиске посмотрел...

Написать калькулятор логических выражений на С - C++
Здравствуйте. Помогите, пожалуйста, написать программу. Реализовать калькулятор – программу которая вычисляет логическое выражение...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Dimon_I
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 75
25.12.2010, 19:34 #2
походу надо определиться с обозначениями и набором функций для начала
0
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
25.12.2010, 19:48  [ТС] #3
есть идея сначала присвоить всем 19 правилам логического упрощения свои переменные
при вводе пользователем лог функции идет поиск по этой строке на истинность какой либо из 19 переменных
все истинные (магически) начинают сокращаться, а не истинные переходят просто в следующий цикл, в следующем цикле идет следующий поиск на истинность, и так пока цикл не будет полностью ложным когда уже будет не чего сократить
тогда идет ответ на вывод
PS: возможно бред...
0
Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
25.12.2010, 20:18 #4
надо построить из входного логического выражения дерево, потом пройти по дереву и поискать комбинации, которые можно упростить - заменять такие комбинации соответствующими упрощенными (заменять узлы дерева.) Рекомендую определить несколько функций для определения упрощаемых комбинаций и несколько для упрощения, чтобы вызывать их применимо к узлам.
1
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
25.12.2010, 20:36  [ТС] #5
подскажите что почитать или что использывать...
0
Dimon_I
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 75
25.12.2010, 21:03 #6
Как оформить это дерево? Принцип понятен но как параллельно считать несколько скобок или раскрывать их? как программа выделит нужные части выражения?
0
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
25.12.2010, 21:04  [ТС] #7
а у меня другой вопрос, если приоритет равный - что далее? немного не ясно.
0
Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
25.12.2010, 21:05 #8
у меня тут есть программка для построения дерева:
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
using namespace std;
struct node{
    node *l,*r;
    char val;
    node(node *ll,node *rr,char c):l(ll),r(rr),val(c){}
};
void print(node *t,int n)
{
    if (t)
    {
        print(t->r,n+1);
        for (int i=0;i<n;i++) cout << "  ";
        cout << t->val << '\n';
        print(t->l,n+1);
    }
}
void del(node *&t)
{
    if (t)
    {
        del(t->r);
        del(t->l);
        delete t;
    }
 
}
char lookahead;
int amount_of_errors=0;
void match(char c)
{
    if (lookahead==c) {
        cin.get(lookahead);
        while(lookahead==' ' || lookahead=='\t')
            scin.get(lookahead);
    } else {
        cout << "\nsyntax error in " << lookahead << '\n';
        amount_of_errors++;
    }
}
node *scan()
{
    while(lookahead==' '||lookahead=='\t')cin.get(lookahead);
    if (isalpha(lookahead)||isdigit(lookahead))return new node(0,0,lookahead);
    else
    {
        cout << "\nsyntax error in " << lookahead << '\n';
        amount_of_errors++;
        return 0;
    }
}
node *expr();
node *factor()
{
    if (lookahead=='(')
    {
        match('('); node *t=expr(); match(')');
        return t;
    }
    else
    {
        node *t = scan();
        match(lookahead);
        return t;
    }
}
node *prim();
node *prim1()
{
    if (lookahead=='&') {
        match('&'); return prim();
    } else {}
}
node *prim()
{
    node *t1=factor();
    if (lookahead=='&') {
        char c=lookahead;
        node *t2=prim1();
        return new node(t1,t2,c);
    } else return t1;
}
node *expr1()
{
    if (lookahead=='|') {
        match('|'); return expr();
    } else {}
}
node *expr()
{
    node *t1=prim();
    if (lookahead=='|') {
        char c=lookahead;
        node *t2=expr1();
        return new node(t1,t2,c);
    } else return t1;
}
int main()
{
    node *root=0;
    match(lookahead);
    root=expr();
    if (amount_of_errors) {
        cout << "error\n";
    } else {
        print(root,0);
    }
    del(root);
    return 0;
}
на ввод подается выражение вроде: t & ( f | t) | f, где t == true, f == false, & == and, | == or. Далее с этим деревом можно делать преобразования - вычислять значение выражения, упрощать или еще чего-нибудь. А что почитать... черт его знает, ваще всего дофига...
data = google("упрощение логических выражений C++");
braine << data;
braine >> result;
prepod << result;

ну например выражение X & X можно упростить подставив X.
функция для определения такого выражения в дереве
C++
1
2
3
4
5
6
7
8
9
bool is_idempotent(node *t)
{
    if (t != NULL) {
        if (t->l != NULL and t->r != NULL) {
            return t->r->val == t->l->val;
        } else return false;
    }
    return false;
}
и функция для упрощения
C++
1
2
3
4
5
6
7
void simplification_idempotency(node *&t)
{
     node *tmp = t->r; // или t = t->l; без разницы в данном случае.
     delete t->l;
     delete t;
     t = tmp;
}
использовать так:
C++
1
2
3
4
5
6
7
8
9
10
void simplification(node *&t)
{
     if (t != NULL) {
         simplification(t->r);
         simplification(t->l);
         if (is_idempotent(t)) 
             simplification_idempotency(t);
         // тут могут быть другие проверки и упрощения
     }
}
типа того. Некоторые функции упрощения могут использовать разные функции проверки, вызывать себя рекурсивно или использовать другие функции упрощения. Для начало надо реализовать все самые элементарные функции проверки и упрощения, а потом через них остальные.

П. С. вот че нашел.
1
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
25.12.2010, 22:23  [ТС] #9
спасибо))) будем внедрять.. тему не бросаю, есть непонятности)

Добавлено через 9 минут
Цитата Сообщение от Aye Aye Посмотреть сообщение
П. С. вот че нашел.
да это я наизусть знаю))

Добавлено через 1 час 3 минуты
Цитата Сообщение от Aye Aye Посмотреть сообщение
у меня тут есть программка для построения дерева:
в 35 строке ошибка(( не компилируется

Добавлено через 2 минуты
может моя идея проще? там после каждого цикла идет сохранение в переменную и после опять идет сканирование на возможность упращения.. без узелков..
0
Dimon_I
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 75
25.12.2010, 23:08 #10
возможно проще но логика не верна, возможны пропуски сокращений
0
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
25.12.2010, 23:17  [ТС] #11
Цитата Сообщение от Dimon_I Посмотреть сообщение
возможны пропуски сокращений
а как сделать чтобы они не были возможны?)))
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
26.12.2010, 00:11 #12
А можете привести пример работы вашей будущей программы, т.е. пример ввода и пример соответствующего вывода.
0
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
26.12.2010, 00:25  [ТС] #13
Да пожалуйста.

НЕ(A*B) - первый закон де моргана (ввел например человек в программу - да что угодно, просто в этом случае оно очень легко раскрывается)
ответ программы: НЕ A + НЕ B
Таблица истинности для данного выражения:
X Y F
0 0 = 1
0 1 = 1
1 0 = 1
1 1 = 0
как то так.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
26.12.2010, 01:57 #14
Цитата Сообщение от IIIa66uMEM6eP Посмотреть сообщение
Да пожалуйста.

НЕ(A*B) - первый закон де моргана (ввел например человек в программу - да что угодно, просто в этом случае оно очень легко раскрывается)
ответ программы: НЕ A + НЕ B
Таблица истинности для данного выражения:
X Y F
0 0 = 1
0 1 = 1
1 0 = 1
1 1 = 0
как то так.
А какое максимальное количество переменных может быть в выражении? Две, или можно больше?
0
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
26.12.2010, 02:29  [ТС] #15
хотя бы две...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.12.2010, 02:29
Привет! Вот еще темы с ответами:

Вывести на экран значения логических выражений - C++
Кто может помочь с программой пожалуйста? Написать программу, позволяющую вывести на экран значения следующих логических выражений...

Напишите грамматику для описания логических выражений - C++
Здравствуйте.Помогите пожалуйста решить задачу, a точнее вот: ...

Разработать программу для вычисления логических выражений - C++
Разработать программу для вычисления логических выражений. На вход программы подаётся выражение, записанное в строковом формате....

Написать интерпретатор логических выражений с построением таблицы четверок и выполнить ее - C++
Написать интерпретатор логических выражений с построением таблицы четверок и выполнить ее. Считать, что выражения включают в себя только...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.12.2010, 02:29
Ответ Создать тему
Опции темы

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