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

Битовые операции. Консольные формулы - C++

Восстановить пароль Регистрация
 
gluchovv
0 / 0 / 0
Регистрация: 27.04.2011
Сообщений: 14
21.07.2014, 14:02     Битовые операции. Консольные формулы #1
Добрый день. Столкнулся с проблемой перевода формулы к примеру: a^b|a&(a^b), с коннсоли. Если считывать и преобразовывать то компилятор считает коды a и b. Мне надо чтобы это было как формула. т.е. задавать значения а и b и чтобы он по этой формуле выводил результат. Сделать подобие таблицы истиннсти для функции.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.07.2014, 14:02     Битовые операции. Консольные формулы
Посмотрите здесь:

битовые операции C++
Битовые операции C++
C++ Битовые операции
Битовые операции, битовые поля. C++
C++ Битовые операции
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,164
Завершенные тесты: 1
21.07.2014, 14:56     Битовые операции. Консольные формулы #2
C++
1
2
3
4
bool a,b;
cin>>a>>b;
bool result=a^b|a&(a^b);
cout<<result;
gluchovv
0 / 0 / 0
Регистрация: 27.04.2011
Сообщений: 14
21.07.2014, 15:21  [ТС]     Битовые операции. Консольные формулы #3
да это понятно. мне надо другое. мне надо что-то наподобие таблицы истинности:
через case задаю различные значения для a b. а в консоли не значения a b а саму формулу. которая записывается в массив char. а вот как ее оттуда обрабатывать чтобы она вычислялась. и, bool не сойдет. ~true ~false не false true а -1 -2.

если делать через char то описывать как

C++
1
2
3
4
char a=0, b=0;
char c;
cin>>c; //только в с он запишет не формулу для вычисления, а массив символов...
//вот и как этот массив вычислить?
точнее говоря, я пишу класс вычисления формулы для VCC++, где в TextBox она будет вводиться, далее с массива преобразовываться, вычисляться и на label выводиться результат. на label ~bool выводится как отрицательное значение
scripter51
0 / 0 / 0
Регистрация: 21.07.2014
Сообщений: 4
21.07.2014, 15:35     Битовые операции. Консольные формулы #4
Вам нужно считать массив символов, разделить его на операции и переменные, вручную задать приоритет операций. Я бы разбил на дерево и вычислял так. Автоматом компьютер ничего не заменит).
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
21.07.2014, 15:49     Битовые операции. Консольные формулы #5
zss, ему нужно распарсить выражение и написать для него таблицу истинности, насколько я понял.

gluchovv, если таК, то это долго и упорно писать свой парсер, разбирать строку на токены. Причем если там есть еще и переменные, то все еще веселее. А у вас они, судя по всему, есть.
gluchovv
0 / 0 / 0
Регистрация: 27.04.2011
Сообщений: 14
21.07.2014, 16:03  [ТС]     Битовые операции. Консольные формулы #6
Да, есть, знания лишними не бывают. Можно подробнее?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
21.07.2014, 16:08     Битовые операции. Консольные формулы #7
gluchovv, Пишем свой интерпретатор языка BASIC почитайте. Там конечно сложнее, но знания ж лишними не бывают.
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,164
Завершенные тесты: 1
21.07.2014, 16:52     Битовые операции. Консольные формулы #8
А так
C++
1
2
3
4
5
6
7
int a,b;
for(a=0;a<=1;a++)
for(b=0;b<=1;b++)
{
    bool result=a^b|a&(a^b);
    cout<<a<<'\t'<<b<<'\t'<<result<<endl;
}
gluchovv
0 / 0 / 0
Регистрация: 27.04.2011
Сообщений: 14
22.07.2014, 10:35  [ТС]     Битовые операции. Консольные формулы #9
"получение таблицы истиности по логической функции (2, 3, 4 переменные), проверка соответствия заданой таблицы истиности логической функции" - вот задание. я не через цикл, я собирался делать через case. сначала с экрана запрос(осуществлял уже): сколько переменных? в зависимости от ответа будет вызываться разный case, скорее всего напишу функцию принимающее различное кол-во переменных (2, 3 и 4 соответственно). и через case в эту функцию буду генерировать переменные. НО, сама логическая функция вводится в консоли. я не могу заранне её в программе забивать. Нужно из строки её вытаскивать. там может быть любая функция.

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

Добавлено через 17 часов 32 минуты
Ребят, еще чем-нибудь можете помочь? с чего начать хотябы
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
22.07.2014, 10:43     Битовые операции. Консольные формулы #10
скапитаню, читаете в стрингу и парсите, нашли соимол, &, |, ^, ~, ищете аргументы, если аргумент содержит еще символ операции то остатки аргумента так же парсите(рекурсия получается, до тех пор пока не получите аргумент), лучше неверное начать с приоритетных операций(поиск их в строке)

Добавлено через 51 секунду
+ учтите что "(" и ")" могут изменить полседовательность выполнения операция, получается даже с поиска скобок надо начать
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
22.07.2014, 10:47     Битовые операции. Консольные формулы #11
gluchovv, стандартный подход:
берете строку, переводите в обратную польскую нотацию (алгоритм).
затем проходим по полученной записи и вычисляем значение (алгоритм).
gluchovv
0 / 0 / 0
Регистрация: 27.04.2011
Сообщений: 14
22.07.2014, 12:12  [ТС]     Битовые операции. Консольные формулы #12
я подобное делал для простой формулы. там мнного текстаа было изза разного расположения символов. в целом, я этот вариант рассматривал, один его минус, оочень много придется делать изза того что 4 разряда, т.е. на входе может быть сумма из 16 произведений аргументов...
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
22.07.2014, 12:23     Битовые операции. Консольные формулы #13
gluchovv, ну других вариантов нет как бы. Разве что пользоваться сторонней либой, которая будет то же самое делать, но внутри.

То есть ваша задача: получить запись в ОПН, после этого по записи построить дерево операций, а потом просто прогнать его для всех значений переменных.
IIARTEMII
20 / 20 / 3
Регистрация: 14.06.2012
Сообщений: 95
Завершенные тесты: 1
22.07.2014, 12:28     Битовые операции. Консольные формулы #14
Не хочу нудить, но есть такая книженция: "Компиляторы. Принципы, технологии и инструменты"
Там так же и приведён метод постфиксной записи, как сказал Psilon. А ещё там есть простой интерпретатор того, что Вам нужно, только там для + - / *, просто чуток модифицируете это под & | ^ и будет Вам счастье) Да и вообще там очень много интересного - советую почитать)
То, что Вам нужно, реализуется не более, чем в 30 строк кода (не считая ввода и вывода)
scripter51
0 / 0 / 0
Регистрация: 21.07.2014
Сообщений: 4
22.07.2014, 13:45     Битовые операции. Консольные формулы #15
Программа разбора и вычисления значения арифметического выражения
Тут реализация по польской нотации алгебраических выражений. У вас почти то же самое, но нужно реализовать логические операции.

Добавлено через 16 минут
Так же можно с помощью дерева реализовать, на мой взгляд это проще
http://devwiki.beloblotskiy.com/inde...B5%D0%B2%D0%B0
gluchovv
0 / 0 / 0
Регистрация: 27.04.2011
Сообщений: 14
23.07.2014, 07:20  [ТС]     Битовые операции. Консольные формулы #16
спасибо, сейчас начнуразбираться
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
23.07.2014, 12:32     Битовые операции. Консольные формулы #17
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
/////////////////////////////////////////////////////////////////////////////////////////
//получение таблицы истиности по логической функции (2, 3, 4 переменные)
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <bitset>
#include <cctype>
#include <functional>
#include <iostream>
#include <iterator>
#include <stack>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
int     const   MAX_VAR_COUNT   =   60;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef T_str::size_type                T_pos;
typedef T_str                           T_expr;
typedef T_str                           T_expr;
typedef std::stack  < char          >   T_char_stack;
typedef std::stack  < bool          >   T_bool_stack;
typedef std::bitset < MAX_VAR_COUNT >   T_bitset;
/////////////////////////////////////////////////////////////////////////////////////////
char    const   NOT_SYMB                =   '!';
char    const   AND_SYMB                =   '&';
char    const   OR_SYMB                 =   '|';
char    const   XOR_SYMB                =   '^';
char    const   ENTAILMENT_SYMB         =   '>';
char    const   EQ_SYMB                 =   '=';
char    const   NOT_EQ_SYMB             =   '#';
char    const   LEFT_PARENTHESIS_SYMB   =   '(';
char    const   RIGHT_PARENTHESIS_SYMB  =   ')';
char    const   TRUE_SYMB               =   '1';
/////////////////////////////////////////////////////////////////////////////////////////
void    print_prompt()
{
    std::cout   <<  "Введите формулу (можно с круглыми скобками) из односимвольных переменных"
                <<  std::endl
                <<  "(латинских букв) и следующих логических операторов:"
                <<  std::endl
                <<  NOT_SYMB            <<  '\t'    <<  "отрицание"         <<  std::endl
                <<  AND_SYMB            <<  '\t'    <<  "и"                 <<  std::endl
                <<  OR_SYMB             <<  '\t'    <<  "или"               <<  std::endl
                <<  XOR_SYMB            <<  '\t'    <<  "исключающее или"   <<  std::endl
                <<  ENTAILMENT_SYMB     <<  '\t'    <<  "импликация"        <<  std::endl
                <<  EQ_SYMB             <<  '\t'    <<  "эквивалентно"      <<  std::endl
                <<  NOT_EQ_SYMB         <<  '\t'    <<  "не эквивалентно"   <<  std::endl
                <<  std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
void    remove_spaces( T_expr   &   expr )
{
    T_expr  res_expr;
 
    std::remove_copy_if
        (
            expr.begin          (),
            expr.end            (),
            std::back_inserter  ( res_expr ),
            isspace
        );
 
    expr = res_expr;
}
/////////////////////////////////////////////////////////////////////////////////////////
char    get_symb( T_expr  &   expr )
{
    char    res     =   expr.front();
    expr.erase( 0, 1 );
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    is_var( char    symb )
{
    return  isalpha( symb ) != 0;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     priority( char  symb )
{
    switch( symb )
    {
    case    NOT_SYMB                :   return  6;
    case    AND_SYMB                :   return  5;
    case    OR_SYMB                 :   return  4;
    case    XOR_SYMB                :   return  4;
    case    ENTAILMENT_SYMB         :   return  3;
    case    EQ_SYMB                 :   return  2;
    case    NOT_EQ_SYMB             :   return  2;
    case    RIGHT_PARENTHESIS_SYMB  :   return  1;
    case    LEFT_PARENTHESIS_SYMB   :   return  0;
 
    default                         :   return  -1;
    }//switch
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    is_op_or_parenthesis( char    symb )
{
    return  priority( symb ) >= 0;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    succsessfully_set_from_expr_to_expr_postf
    (
        T_expr      expr,
        T_expr  &   expr_postf
    )
{
    bool            bool_res    =   !expr.empty();
    T_char_stack    char_stack;
 
    if( bool_res )
    {
        while   (
                    !expr.empty()
                )
        {
            char    cur_symb    =   get_symb( expr );
 
            if  (
                    is_var( cur_symb )
                )
            {
                expr_postf.push_back( cur_symb );
            }
            else if( cur_symb == LEFT_PARENTHESIS_SYMB )
            {
                char_stack.push( cur_symb );
            }
            else if (
                        is_op_or_parenthesis( cur_symb )
                    )
            {
                if  (
                        char_stack.empty()
                    )
                {
                    char_stack.push( cur_symb );
                }
                else
                {
                    while   (
                                    !char_stack.empty()
                                &&  priority( char_stack.top() ) >= priority( cur_symb )
                            )
                    {
                        expr_postf.push_back
                            (
                                char_stack.top()
                            );
 
                        char_stack.pop();
                    }
 
                    if( cur_symb == RIGHT_PARENTHESIS_SYMB )
                    {
                        bool_res    =       !char_stack.empty()
                                        &&  char_stack.top() == LEFT_PARENTHESIS_SYMB;
 
                        if( !bool_res )
                        {
                            break;
                        }
 
                        char_stack.pop();
                    }
                    else
                    {
                        char_stack.push( cur_symb );
                    }//else
                }//else
            }//else if
            else
            {
                bool_res    =   false;
                break;
            }//else
        }//while
    }//if
 
    if( bool_res )
    {
        while   (
                    !char_stack.empty()
                )
        {
            expr_postf.push_back
                (
                    char_stack.top()
                );
 
            char_stack.pop();
        }//while
    }//if
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_is_not_var
{
    bool    operator() ( char   symb )
    {
        return  isalpha( symb ) == 0;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
T_str   get_variables_str( T_expr  const   &  expr )
{
    T_str   res_str;
 
    std::remove_copy_if
        (
            expr.begin          (),
            expr.end            (),
            std::back_inserter  ( res_str ),
            T_is_not_var        ()
        );
 
    std::sort
        (
            res_str.begin   (),
            res_str.end     ()
        );
 
    auto    new_end     =   std::unique
                                (
                                    res_str.begin   (),
                                    res_str.end     ()
                                );
 
    return  T_str
                (
                    res_str.begin(),
                    new_end
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    get_bool_val_of_var_with_variables_str_and_var_values_str
    (
        char                cur_symb,
        T_str   const   &   variables_str,
        T_str   const   &   var_values_str
    )
{
    T_pos   pos     =   variables_str.find( cur_symb );
    return  var_values_str[ pos ]   ==  TRUE_SYMB;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    xor
    (
        bool    L,
        bool    R
    )
{
    return  L + R == 1;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    entailment
    (
        bool    L,
        bool    R
    )
{
    return  !L || R;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_execute_bin_op_with_bool_stack
    ( 
        char                bin_op_symb,
        T_bool_stack    &   bool_stack
    )
{
    bool    right_val   =   bool_stack.top();
    bool_stack.pop();
 
    bool    bool_res    =   !bool_stack.empty();
 
    if( bool_res )
    {
        bool    left_val    =   bool_stack.top();
        bool_stack.pop();
        bool    op_result   =   false;
 
        switch( bin_op_symb )
        {
        case    AND_SYMB                :   op_result   =   left_val    &&  right_val;                  break;
        case    OR_SYMB                 :   op_result   =   left_val    ||  right_val;                  break;
        case    XOR_SYMB                :   op_result   =   xor         ( left_val,     right_val   );  break;
        case    ENTAILMENT_SYMB         :   op_result   =   entailment  ( left_val,     right_val   );  break;
        case    EQ_SYMB                 :   op_result   =   left_val    ==  right_val;                  break;
        case    NOT_EQ_SYMB             :   op_result   =   left_val    !=  right_val;                  break;
 
        default                         :   bool_res = false;
        }
 
        bool_stack.push( op_result );
    }//if
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_calc_expr_postf_with_variables_str_and_var_values_and_set_res
    (
        T_expr              expr_postf,
        T_str   const   &   variables_str,
        T_str   const   &   var_values_str,
        bool            &   op_res
    )
{
    bool            bool_res    =   !expr_postf.empty();
    T_bool_stack    bool_stack;
 
    if( bool_res )
    {
        while   (
                    !expr_postf.empty()
                )
        {
            char    cur_symb    =   get_symb( expr_postf );
 
            if  (
                    is_var( cur_symb )
                )
            {
                bool_stack.push
                    (
                        get_bool_val_of_var_with_variables_str_and_var_values_str
                            (
                                cur_symb,
                                variables_str,
                                var_values_str
                            )
                    );
            }
            else
            {
                bool_res    =   !bool_stack.empty();
 
                if( !bool_res )
                {
                    break;
                }
 
                if( cur_symb == NOT_SYMB )
                {
                    bool_stack.top()    =   !bool_stack.top();
                }
                else
                {
                    bool_res    =   successfully_execute_bin_op_with_bool_stack
                                        (
                                            cur_symb,
                                            bool_stack
                                        );
                }//else
            }//else
        }//while
    }//if
 
    if( bool_res )
    {
        bool_res    =   bool_stack.size() == 1;
 
        if( bool_res )
        {
            op_res  =   bool_stack.top();
        }
    }//if
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
void    inc_bitset( T_bitset    &   var_values )
{
    var_values  =   T_bitset
                        (
                            int (
                                    var_values.to_ulong() + 1
                                )
                        );
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_print_truth_table_for_expr_and_expr_postf
    (
        T_expr  const   &  expr,
        T_expr  const   &  expr_postf
    )
{
    static  T_str   const   SPACES_STR  =   "\t";
 
    bool        bool_res        =   false;
    T_str       variables_str   =   get_variables_str   ( expr_postf );
    int         var_count       =   variables_str.size  ();
    T_bitset    var_values;
 
    std::cout   <<  std::endl
                <<  "Таблица истинности"
                <<  std::endl
                <<  variables_str
                <<  SPACES_STR
                <<  expr
                <<  std::endl;
 
    unsigned    long    func_values_count   =   1 << var_count;
 
    for( unsigned   long  i = 0; i < func_values_count; ++i )
    {
        T_str   var_values_str  =   var_values.to_string().substr
                                        (
                                            MAX_VAR_COUNT - var_count,
                                            var_count
                                        );
 
        bool    op_res  =   false;
        bool_res        =   successfully_calc_expr_postf_with_variables_str_and_var_values_and_set_res
                                (
                                    expr_postf,
                                    variables_str,
                                    var_values_str,
                                    op_res
                                );
 
        if( !bool_res )
        {
            break;
        }
 
        std::cout   <<  var_values_str
                    <<  SPACES_STR
                    <<  op_res
                    <<  std::endl;
 
        inc_bitset( var_values );
    }//for
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        T_expr  expr;
        T_expr  expr_postf;
 
        print_prompt    ();
        getline         ( std::cin, expr );
        remove_spaces   ( expr );
 
        if  (
                    !succsessfully_set_from_expr_to_expr_postf
                        (
                            expr,
                            expr_postf
                        )
 
                ||  !successfully_print_truth_table_for_expr_and_expr_postf
                        (
                            expr,
                            expr_postf
                        )
            )
        {
            std::cout   <<  "Выражение некорректно."
                        <<  std::endl;
        }//if
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2014, 13:28     Битовые операции. Консольные формулы
Еще ссылки по теме:

C++ Битовые операции
Битовые операции и операции смещения языка С C++
Битовые операции C++

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
23.07.2014, 13:28     Битовые операции. Консольные формулы #18
Путем несложных манипуляций еще возможность ввода констант добавил:
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
/////////////////////////////////////////////////////////////////////////////////////////
//получение таблицы истиности по логической функции (2, 3, 4 переменные)
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <bitset>
#include <cctype>
#include <functional>
#include <iostream>
#include <iterator>
#include <stack>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
int     const   MAX_VAR_COUNT   =   60;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef T_str::size_type                T_pos;
typedef T_str                           T_expr;
typedef T_str                           T_expr;
typedef std::stack  < char          >   T_char_stack;
typedef std::stack  < bool          >   T_bool_stack;
typedef std::bitset < MAX_VAR_COUNT >   T_bitset;
/////////////////////////////////////////////////////////////////////////////////////////
char    const   NOT_SYMB                =   '!';
char    const   AND_SYMB                =   '&';
char    const   OR_SYMB                 =   '|';
char    const   XOR_SYMB                =   '^';
char    const   ENTAILMENT_SYMB         =   '>';
char    const   EQ_SYMB                 =   '=';
char    const   NOT_EQ_SYMB             =   '#';
char    const   LEFT_PARENTHESIS_SYMB   =   '(';
char    const   RIGHT_PARENTHESIS_SYMB  =   ')';
char    const   TRUE_SYMB               =   '1';
/////////////////////////////////////////////////////////////////////////////////////////
void    print_prompt()
{
    std::cout   <<  "Введите формулу (можно с круглыми скобками) из односимвольных переменных"
                <<  std::endl
                <<  "(латинских букв), констант 0 и 1 и следующих логических операторов:"
                <<  std::endl
                <<  NOT_SYMB            <<  '\t'    <<  "отрицание"         <<  std::endl
                <<  AND_SYMB            <<  '\t'    <<  "и"                 <<  std::endl
                <<  OR_SYMB             <<  '\t'    <<  "или"               <<  std::endl
                <<  XOR_SYMB            <<  '\t'    <<  "исключающее или"   <<  std::endl
                <<  ENTAILMENT_SYMB     <<  '\t'    <<  "импликация"        <<  std::endl
                <<  EQ_SYMB             <<  '\t'    <<  "эквивалентно"      <<  std::endl
                <<  NOT_EQ_SYMB         <<  '\t'    <<  "не эквивалентно"   <<  std::endl
                <<  std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
void    remove_spaces( T_expr   &   expr )
{
    T_expr  res_expr;
 
    std::remove_copy_if
        (
            expr.begin          (),
            expr.end            (),
            std::back_inserter  ( res_expr ),
            isspace
        );
 
    expr = res_expr;
}
/////////////////////////////////////////////////////////////////////////////////////////
char    get_symb( T_expr  &   expr )
{
    char    res     =   expr.front();
    expr.erase( 0, 1 );
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    is_var( char    symb )
{
    return  isalpha( symb ) != 0;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    is_const( char    symb )
{
    return      symb    ==  '0'
            ||  symb    ==  '1';
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    is_var_or_const( char    symb )
{
    return      is_var      ( symb )
            ||  is_const    ( symb );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     priority( char  symb )
{
    switch( symb )
    {
    case    NOT_SYMB                :   return  6;
    case    AND_SYMB                :   return  5;
    case    OR_SYMB                 :   return  4;
    case    XOR_SYMB                :   return  4;
    case    ENTAILMENT_SYMB         :   return  3;
    case    EQ_SYMB                 :   return  2;
    case    NOT_EQ_SYMB             :   return  2;
    case    RIGHT_PARENTHESIS_SYMB  :   return  1;
    case    LEFT_PARENTHESIS_SYMB   :   return  0;
 
    default                         :   return  -1;
    }//switch
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    is_op_or_parenthesis( char    symb )
{
    return  priority( symb ) >= 0;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    succsessfully_set_from_expr_to_expr_postf
    (
        T_expr      expr,
        T_expr  &   expr_postf
    )
{
    bool            bool_res    =   !expr.empty();
    T_char_stack    char_stack;
 
    if( bool_res )
    {
        while   (
                    !expr.empty()
                )
        {
            char    cur_symb    =   get_symb( expr );
 
            if  (
                    is_var_or_const( cur_symb )
                )
            {
                expr_postf.push_back( cur_symb );
            }
            else if( cur_symb == LEFT_PARENTHESIS_SYMB )
            {
                char_stack.push( cur_symb );
            }
            else if (
                        is_op_or_parenthesis( cur_symb )
                    )
            {
                if  (
                        char_stack.empty()
                    )
                {
                    char_stack.push( cur_symb );
                }
                else
                {
                    while   (
                                    !char_stack.empty()
                                &&  priority( char_stack.top() ) >= priority( cur_symb )
                            )
                    {
                        expr_postf.push_back
                            (
                                char_stack.top()
                            );
 
                        char_stack.pop();
                    }
 
                    if( cur_symb == RIGHT_PARENTHESIS_SYMB )
                    {
                        bool_res    =       !char_stack.empty()
                                        &&  char_stack.top() == LEFT_PARENTHESIS_SYMB;
 
                        if( !bool_res )
                        {
                            break;
                        }
 
                        char_stack.pop();
                    }
                    else
                    {
                        char_stack.push( cur_symb );
                    }//else
                }//else
            }//else if
            else
            {
                bool_res    =   false;
                break;
            }//else
        }//while
    }//if
 
    if( bool_res )
    {
        while   (
                    !char_stack.empty()
                )
        {
            expr_postf.push_back
                (
                    char_stack.top()
                );
 
            char_stack.pop();
        }//while
    }//if
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_is_not_var
{
    bool    operator() ( char   symb )
    {
        return  isalpha( symb ) == 0;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
T_str   get_variables_str( T_expr  const   &  expr )
{
    T_str   res_str;
 
    std::remove_copy_if
        (
            expr.begin          (),
            expr.end            (),
            std::back_inserter  ( res_str ),
            T_is_not_var        ()
        );
 
    std::sort
        (
            res_str.begin   (),
            res_str.end     ()
        );
 
    auto    new_end     =   std::unique
                                (
                                    res_str.begin   (),
                                    res_str.end     ()
                                );
 
    return  T_str
                (
                    res_str.begin(),
                    new_end
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    get_bool_val_of_var_with_variables_str_and_var_values_str
    (
        char                cur_symb,
        T_str   const   &   variables_str,
        T_str   const   &   var_values_str
    )
{
    T_pos   pos     =   variables_str.find( cur_symb );
    return  var_values_str[ pos ]   ==  TRUE_SYMB;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    xor
    (
        bool    L,
        bool    R
    )
{
    return  L + R == 1;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    entailment
    (
        bool    L,
        bool    R
    )
{
    return  !L || R;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_execute_bin_op_with_bool_stack
    ( 
        char                bin_op_symb,
        T_bool_stack    &   bool_stack
    )
{
    bool    right_val   =   bool_stack.top();
    bool_stack.pop();
 
    bool    bool_res    =   !bool_stack.empty();
 
    if( bool_res )
    {
        bool    left_val    =   bool_stack.top();
        bool_stack.pop();
        bool    op_result   =   false;
 
        switch( bin_op_symb )
        {
        case    AND_SYMB                :   op_result   =   left_val    &&  right_val;                  break;
        case    OR_SYMB                 :   op_result   =   left_val    ||  right_val;                  break;
        case    XOR_SYMB                :   op_result   =   xor         ( left_val,     right_val   );  break;
        case    ENTAILMENT_SYMB         :   op_result   =   entailment  ( left_val,     right_val   );  break;
        case    EQ_SYMB                 :   op_result   =   left_val    ==  right_val;                  break;
        case    NOT_EQ_SYMB             :   op_result   =   left_val    !=  right_val;                  break;
 
        default                         :   bool_res = false;
        }
 
        bool_stack.push( op_result );
    }//if
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_calc_expr_postf_with_variables_str_and_var_values_and_set_res
    (
        T_expr              expr_postf,
        T_str   const   &   variables_str,
        T_str   const   &   var_values_str,
        bool            &   op_res
    )
{
    bool            bool_res    =   !expr_postf.empty();
    T_bool_stack    bool_stack;
 
    if( bool_res )
    {
        while   (
                    !expr_postf.empty()
                )
        {
            char    cur_symb    =   get_symb( expr_postf );
 
            if  (
                    is_var( cur_symb )
                )
            {
                bool_stack.push
                    (
                        get_bool_val_of_var_with_variables_str_and_var_values_str
                            (
                                cur_symb,
                                variables_str,
                                var_values_str
                            )
                    );
            }
            else if (
                        is_const( cur_symb )
                    )
            {
                bool_stack.push( cur_symb == TRUE_SYMB );
            }
            else
            {
                bool_res    =   !bool_stack.empty();
 
                if( !bool_res )
                {
                    break;
                }
 
                if( cur_symb == NOT_SYMB )
                {
                    bool_stack.top()    =   !bool_stack.top();
                }
                else
                {
                    bool_res    =   successfully_execute_bin_op_with_bool_stack
                                        (
                                            cur_symb,
                                            bool_stack
                                        );
                }//else
            }//else
        }//while
    }//if
 
    if( bool_res )
    {
        bool_res    =   bool_stack.size() == 1;
 
        if( bool_res )
        {
            op_res  =   bool_stack.top();
        }
    }//if
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
void    inc_bitset( T_bitset    &   var_values )
{
    var_values  =   T_bitset
                        (
                            int (
                                    var_values.to_ulong() + 1
                                )
                        );
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_print_truth_table_for_expr_and_expr_postf
    (
        T_expr  const   &  expr,
        T_expr  const   &  expr_postf
    )
{
    static  T_str   const   SPACES_STR  =   "\t";
 
    bool        bool_res        =   false;
    T_str       variables_str   =   get_variables_str   ( expr_postf );
    int         var_count       =   variables_str.size  ();
    T_bitset    var_values;
 
    std::cout   <<  std::endl
                <<  "Таблица истинности"
                <<  std::endl
                <<  variables_str
                <<  SPACES_STR
                <<  expr
                <<  std::endl;
 
    unsigned    long    func_values_count   =   1 << var_count;
 
    for( unsigned   long  i = 0; i < func_values_count; ++i )
    {
        T_str   var_values_str  =   var_values.to_string().substr
                                        (
                                            MAX_VAR_COUNT - var_count,
                                            var_count
                                        );
 
        bool    op_res  =   false;
        bool_res        =   successfully_calc_expr_postf_with_variables_str_and_var_values_and_set_res
                                (
                                    expr_postf,
                                    variables_str,
                                    var_values_str,
                                    op_res
                                );
 
        if( !bool_res )
        {
            break;
        }
 
        std::cout   <<  var_values_str
                    <<  SPACES_STR
                    <<  op_res
                    <<  std::endl;
 
        inc_bitset( var_values );
    }//for
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        T_expr  expr;
        T_expr  expr_postf;
 
        print_prompt    ();
        getline         ( std::cin, expr );
        remove_spaces   ( expr );
 
        if  (
                    !succsessfully_set_from_expr_to_expr_postf
                        (
                            expr,
                            expr_postf
                        )
 
                ||  !successfully_print_truth_table_for_expr_and_expr_postf
                        (
                            expr,
                            expr_postf
                        )
            )
        {
            std::cout   <<  "Выражение некорректно."
                        <<  std::endl;
        }//if
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}
Yandex
Объявления
23.07.2014, 13:28     Битовые операции. Консольные формулы
Ответ Создать тему
Опции темы

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