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

Расчёт логического выражения - C++

Восстановить пароль Регистрация
 
nefton
44 / 20 / 5
Регистрация: 28.02.2013
Сообщений: 184
14.01.2014, 02:09     Расчёт логического выражения #1
Вопрос 1.
Дана строка типа "(5>8)AND(true)OR(NOT(6<=5))"
Тоесть простое логическое выражения в виде строки со скобками, числами, логическими операторами.
Строка произвольная.
Как высчитать её значение? Хоть в какую сторону копать, чтоб не изобретать велосипед?

Вопрос 2.
У меня есть структура с параметрами (целые числа).
Есть текстовый файл со строками. В каждой строке Логическое выражение с именами этих параметров.
Задача. Создать по обьекту на каждую строку. Чтоб У него была функция
C++
1
bool Answer(struct_params* params)
Надо обязательно чтоб он это делал быстро. Тоесть не перебирал все параметры и не анализировал каждый раз строку. Он один раз конструируется в памяти на основе логической строки из файла и должен быстро лопатить подаваемые ему структуры на предмет своего логического выражения.

Куда копать то? ума честно пока не приложу. Понимаю что это возможно, но как?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
14.01.2014, 02:33     Расчёт логического выражения #2
nefton, Насколько я знаю, самая быстрая реализация программы, вычисляющей значение выражения - стековый калькулятор. Почему бы вам не написать стековый калькулятор, вычисляющий значение логического выражения?

Добавлено через 1 минуту
http://ru.wikipedia.org/wiki/%CE%E1%...E0%EF%E8%F1%FC

Добавлено через 1 минуту
(это к вопросу 1)
nefton
44 / 20 / 5
Регистрация: 28.02.2013
Сообщений: 184
14.01.2014, 19:14  [ТС]     Расчёт логического выражения #3
К вопросу 2. На ум приходит 2 варианта.
1. Кривой аналог ПЛИС.
Допустим у нас есть до 4 логических параметров
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
class plis{
  bool a,b,c,d; //Локальная копия входных параметров
  bool not_a, not_b, not_c, not_d; //Применять ли оператор not к параметрам
  bool a_and_b, a_and_c, a_and_d, b_and_c, b_and_d, c_and_b; //применять ли "И" к этим двум операторам
  bool a_or_b, a_or_c, a_or_d, b_or_c, b_or_d, c_or_b; //применять ли "ИЛИ" к этим двум операторам
  void Construct(string logical_string);
  plis();
  bool Answer(a, b, c, d);
}
 
bool plis::Answer(a,b,c,d){
if (not_a) a = !a;
if (not_b) b = !b;
if (not_c) c = !c;
if (not_d) d = !d;
 
if (a_or_b) a= a||b;
....
} 
 
void Construct(string logical_string){
//На основании строки присваиваем значения "фузам"
//типа применять ли оператор "нет" к "a"
 
}
С помощью такой конструкции возможно реальзовать какуюто програмируемую логику.
Но пока писал понял что легче зубы пломбировать через попу

Вариант 2. (уже 1 )
Формировать ассемблерный код. Записывать его в память и передавать управление ему чтоб посчитать результат. Так бы я и сделал, если б писал на Ассемблере. Наверняка в С++ есть чтото аналогичное, и более продуманное.

Добавлено через 15 часов 52 минуты
Вариант 3. Генерировать автоматически текст С++ *.h файла. Потом компилировать его.
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
25.04.2014, 14:00     Расчёт логического выражения #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Может, кому-то еще будет интересно.
Вычисление логического выражения методом рекурсивного спуска:

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
#include <iostream>
using namespace std;
 
 
/* Грамматика для логического выражения
S -> E&
E -> T | T '|' E
T -> F | F '&' T
F -> 0 | 1 | '(' E ')' | '!' F
*/
 
typedef char Lexeme; // Тип для лексемы (в более сложных программах Lexeme может представлять собой целый класс). 
 
Lexeme currentLex; // Текущая лексема
 
inline void getNextLexeme() // Функция получения следующей лексемы 
{ 
    cin >> currentLex;
}
 
bool parseS();
bool parseE();
bool parseT();
bool parseF();
 
int main() 
{
    bool result;
    cout <<"Input: ";
    getNextLexeme();
    try 
    {
        result = parseS();
        cout << "Calculated: " << result <<'\n';
    }
    catch ( const char * err ) 
    {
        cout << "Error: " << err << ", but " << currentLex << " got." << endl;
    }
    
    system ("pause");
}
 
bool parseS()
{
    bool r = parseE();
    if ( currentLex != '$' ) { // Проверяем конец цепочки
        throw "End of line needed";
    }
    return r;
}
 
bool parseE()
{
    bool b = parseT();
 
    if (currentLex == '|')
    {
        getNextLexeme();
        b = parseE() || b;
    }
    
    return b;
}
 
bool parseT()
{
    bool b = parseF();
    if (currentLex == '&')
    {
        getNextLexeme();
        b = parseT() && b;
    }
    return b;
}
 
bool parseF()
{
    bool b;
    if ( currentLex == '1' || currentLex == '0' ) 
    {
        b = (currentLex == '1');
        getNextLexeme();
    }
    else if ( currentLex == '!' ) 
    {
        getNextLexeme();
        b = !parseF();
    }
    else if ( currentLex == '(' ) 
    {
        getNextLexeme();
        b = parseE(); 
        if ( currentLex != ')' ) {
            throw ") needed";
        }
        getNextLexeme();
    }
    else {
        throw " 0 or 1 or ! or ( needed";
    }
    return b;
}
Этот "калькулятор" вычисляет любое логическое выражение с операциями "&, |, !". (Скобки - опциональные).
Yandex
Объявления
25.04.2014, 14:00     Расчёт логического выражения
Ответ Создать тему
Опции темы

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