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

Программа с использованием объектов типа стека или очередь на C. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
rjj
0 / 0 / 0
Регистрация: 23.02.2012
Сообщений: 4
23.02.2012, 00:43     Программа с использованием объектов типа стека или очередь на C. #1
Помогите пожалуйста с написанием.
Программа с использованием объектов типа стека или очередь.
На стандартный ввод программы поступают логические выражения из констант T(true) F(false), а также знаков конъюнкции (&) и дизъюнкции (|). Вычислить значение этого выражения.
Например (T&T)|(F&T)->T.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
(SkyNet)
 Аватар для (SkyNet)
22 / 40 / 6
Регистрация: 25.10.2011
Сообщений: 175
23.02.2012, 00:54     Программа с использованием объектов типа стека или очередь на C. #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool a, b, c;
 
cin >> a;
cin >> b;
 
if(a != false || a != true)
  a = true;
if(b != false || b != true)
  b = true;
 
 c = ( a && b ) || (a && b);
 
 if(c)
    cout << " true " ;
 else 
    cout << " false " ;
samdavydov
59 / 20 / 2
Регистрация: 23.02.2012
Сообщений: 36
23.02.2012, 08:50     Программа с использованием объектов типа стека или очередь на C. #3
rjj, привет!

Смотри, идея такая: что такое стек, представляешь?
Это структура данных, как колода карт: сверху положил, сверху же и снимаешь. Первый пришел - последний ушел.
Такой структурой удобно обрабатывать вложенные скобочные последовательности.

Создадим функцию Evaluate(), которая вычисляет значение выражения.
Подвыражение в скобках - тоже выражение. Поэтому, как только встретим скобку, функция будет вызывать сама себя.
Таким образом, Evaluate() - рекурсивная функция.

Итак, у тебя есть, к примеру (T&T)|(F&T).
Первой идет открывающая скобка, значит надо вычислить подвыражение до первой закрывающей скобки и положить результат на верхушку стека.
(T&T)|(F&T) -> T|(F&T). Последовательно вычисляя подвыражения, мы, в итоге, останемся с одним выражением вида A|B или A&B, которое можно вычислить непосредственно.

Evaluate("(T&T)|(F&T)") -> Evaluate("Evaluate("T&T")|(F&T)") -> Evaluate("T|(F&T)") -> Evaluate("T|Evaluate("F&T")") -> Evaluate("T|F") -> T

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

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
#include <iostream>
#include <stack>
 
typedef std::stack<char> Stack;
 
Stack Tokenize(const char* expression) // разбираем выражение на отдельные элементы и складываем их в стек
{
    Stack tokens;
    
    for (size_t i = 0, len = strlen(expression); i != len; ++i)
        tokens.push(expression[len - i - 1]);
 
    return tokens;
}
 
char Evaluate(Stack& tokens) // вычисляем выражение, состоящее из элементов
{
    bool result = true;
    char operation = '*'; // пустая операция
    
    while(!tokens.empty())
    {
        char token = tokens.top();
        tokens.pop();
 
        if (token == '(') // вычислить подвыражение
        {
            tokens.push(Evaluate(tokens)); // запустить саму себя на оставшемся стеке и положить результат на вершину
        }
        else if (token == ')') // вернуть результат подвыражения
        {
            return result ? 'T' : 'F';
        }
        else if (token == 'T')
        { 
            if (operation == '|')
            {
                result |= true;
                operation = '*';
            }
            else if (operation == '&')
            {
                result &= true;
                operation = '*';
            }
            else
                result = true;
        }
        else if (token == 'F')
        {
            if (operation == '|')
            {
                result |= false;
                operation = '*';
            }
            else if (operation == '&')
            {
                result &= false;
                operation = '*';
            }
            else
                result = false;
        }
        else if (token == '&')
        {
            operation = '&';
        }
        else if (token == '|')
        {
            operation = '|';
        }
    }
 
    return result ? 'T' : 'F';
}
 
int main()
{
    const char* expression = "(T&F)|((T&T)&(T&F))";
    std::cout << expression << " = " << Evaluate(Tokenize(expression)) << std::endl;
    return 0;
}
____________
http://zmartzoft.ru
rjj
0 / 0 / 0
Регистрация: 23.02.2012
Сообщений: 4
23.02.2012, 11:09  [ТС]     Программа с использованием объектов типа стека или очередь на C. #4
samdavydov,вот на этом спасибо,очень доступно и понятно.
Yandex
Объявления
23.02.2012, 11:09     Программа с использованием объектов типа стека или очередь на C.
Ответ Создать тему
Опции темы

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