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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Каррирование или карринг http://www.cyberforum.ru/cpp-beginners/thread451216.html
Определение с вики какое-то мутное, кто может объясните пожалуйста поподробнее - что это, для чего и когда применять.
C++ Принадлежность точки заштрихованной области создать программу, которая проверяет принадлежность точки заштрихованной области. помогите кому не трудно. http://s018.***********/i512/1202/d5/82b2190b05ec.png http://www.cyberforum.ru/cpp-beginners/thread451208.html
Простая, но объемная прога. Обработка текста на с++ (различные виды сортировки слов) C++
Сам файл с которого происходит считывание вложен. Само задание выглядит так: Программа должна открыть файл Go.txt и считать с него текстовую информацию в виде отдельных слов. Запомнить данные в классе в виде массива слов . Отсортировать массив по алфавиту. После этого проверить элементы массива – если слова повторяются несколько раз, то элементы дубли надо удалить, но запомнить для слова...
C++ Списки
вопрос, в каких случаях используют односвязный список заместо двух связного?
C++ Командная строка http://www.cyberforum.ru/cpp-beginners/thread451190.html
Нужно выполнить задание, но как не пойму... Ввести n строк , найти самую короткую и самую длинную строки. Вывести найденные строки и их длину. Ввод осуществить как аргументы командной строки. Подскажите, как сам ввод сделать, в нете ничего не нашел(((
C++ Написать программу,которая находит среднее значение массива целых чисел при помощи функции Написать программу,которая находит среднее значение массива целых чисел при помощи функции. (на С++) подробнее

Показать сообщение отдельно
samdavydov
59 / 20 / 2
Регистрация: 23.02.2012
Сообщений: 36
23.02.2012, 08:50     Программа с использованием объектов типа стека или очередь на C.
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
 
Текущее время: 00:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru