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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 71, средняя оценка - 4.93
Praxie
0 / 0 / 0
Регистрация: 15.12.2012
Сообщений: 5
#1

Принцип реализации и работы со стеком - C++

15.12.2012, 21:16. Просмотров 10722. Ответов 6
Метки нет (Все метки)

Здравствуйте! В ходе изучения применения стека на c++, начал рассматривать нижеприведенный пример (Программа вычисляет обратную польскую запись).
Сразу же появились вопросы.
1. Что это за конструкция? push(next, ((a = pop(next)), (b = pop(next)), b - a));
2. Объясните на пальцах, как устроены "внутри" функции push и pop. С указателями и адресами я немного знаком, но разобраться не могу даже с помощью комментариев...
Спасибо.

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
#include <iostream>
#include <conio.h>
 
struct stek
{
    int d;
    struct stek *next; // указатель на следующий элемент списка (стека)
};
 
void push(stek* &next, int d);  // функция будет помещать элемент в стек
                                // next – указатель на вершину стека
int pop(stek* &next);           // функция будет извлекать элемент их стека
                                // вершина которого - next
 
void push(stek* &next, int d)
{
    stek *pv = new stek;      // объявляем новую динамическую переменную типа stek
    pv->d = d;                // записываем  значение, которое помещается в стек
    pv->next = next;          // связываем новый элемент стека с предыдущим
    next = pv;                // новый элемент стека становится его вершиной
}
 
int pop(stek* &next)
{
    int temp = next->d;     // извлекаем в переменную temp значение в вершине стека
    stek *pv = next;        // запоминаем указатель на вершину стека, чтобы затем
                            // освободить выделенную под него память
    next = next->next;      // вершиной становится предшествующий top элемент
    delete pv;              // освобождаем память, тем самым удалили вершину
    return temp;            // возвращаем значение, которое было в вершине
}
 
 
int main()
{
    // char v[25]="5 9 8 + 4 6 * * 7 + * ";
    char v[]="1 2 -";
    stek *next=0;
    int a, b;
    for(int i = 0; v[i] != '\0'; i++)
    {
        switch(v[i])
        {
            case '+': push(next, pop(next) + pop(next)); break;
            case '-': push(next, ((a = pop(next)), (b = pop(next)), b - a)); break;
            case '*': push(next, pop(next) * pop(next)); break;
            case '/': push(next, ((a = pop(next)), (b = pop(next)), b / a)); break;
            default:
                if(isdigit(v[i])) push(next, 0);
                while(isdigit(v[i]))
                    push(next, 10*pop(next) + (v[i++]-'0'));
        }
    }
    printf("\n %i \n",pop(next));
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2012, 21:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Принцип реализации и работы со стеком (C++):

функции работы со стеком - C++
необходимо написать стек..и реализовать функции добавления элементов; просмотра; удаления элемента по правилам стека; удаление...

Класс для работы со стеком - C++
Создать класс для работы со стеком. Элемент стека – символ. Использовать стек для проверки правильности расстановки скобок трех типов...

Разработать класс для работы со стеком - C++
Как можно разработать класс для работы со стеком. Элемент стека – символ. Использовать стек для проверки правильности расстановки скобок...

Построить класс для работы со стеком - C++
Построить класс для работы со стеком. Элемент стека – целое число. Ввести две неубывающие последовательности чисел в два стека....

Перегрузка операторов для работы со стеком - C++
Текст задания: Создать объект &quot;динамический стек&quot;. Перегрузить операции +, -, +=, -= для выполнения манипуляций со стеком. Вот...

Разработка класса для работы со стеком - C++
Добрый день) в общем задача звучит так: Разработать класс для работы со стеком. Элемент стека – действительное число. Применить класс...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Wolkodav
603 / 456 / 32
Регистрация: 18.09.2012
Сообщений: 1,685
15.12.2012, 22:05 #2
Стек реализован по принципу первый пришёл первый ушёл.
Функция push(), он добавляет элемент в вершину стека, т.е. есть стек:
4
3
8
вызываем функцию push(next,5);
next теперь у наз указывает на 4 (до этого на 3) т.е. на элемент который следует после вершины стека, и добавляет в вершину элемент со значением 5.

pop извлекает элемент из вершины стека.
Т.е. есть стек
5
6
8
вызываем pop(next);
он переносит указатель next на 6, т.к. вершина теперь у нас будет 6, вытаскивает и возвращает нам 5.
Примерно так.

Добавлено через 4 минуты
А внутри:
push (next,d);
Создаём новый элемент структуры, записываем в него значение d, next-указатель на следующий элемент стэка, т.е. в новый элемент структуры в поле next заносим адрес next( вершины)

pop(steck)
Создаём переменную, заносим в неё значение вершины стека, вершиной становится элемент следующий за вершиной, а указатель next структуры, присваивается указатель поля next новой вершины.
Praxie
0 / 0 / 0
Регистрация: 15.12.2012
Сообщений: 5
15.12.2012, 23:33  [ТС] #3
Спасибо. То есть, чтобы получить доступ к n-му элементу стека, необходимо выполнить n раз функцию pop(next), после чего все извлеченные элементы пропадут?
push (next,d);
Создаём новый элемент структуры, записываем в него значение d, next-указатель на следующий элемент стэка, т.е. в новый элемент структуры в поле next заносим адрес next( вершины)
В этой функции 2 аргумента.
как насчет ((a = pop(next)), (b = pop(next))? Это явно не аргументы.
C++
1
push(next, ((a = pop(next)), (b = pop(next)), b - a));
Нельзя ли написать push(next, pop(next)-pop(next))?
Wolkodav
603 / 456 / 32
Регистрация: 18.09.2012
Сообщений: 1,685
15.12.2012, 23:40 #4
на первый вопрос- да,
на второй вопрос- почему нет? просто аргумент составной)), он вернет вначале два инта, а потом запушит их разность
на третий вопрос-можно.
Praxie
0 / 0 / 0
Регистрация: 15.12.2012
Сообщений: 5
15.12.2012, 23:55  [ТС] #5
Я понял)
Для операций вычитания нужно, чтобы из второго элемента вычитался первый.
Я просто не знал, что в скобках функции можно так записывать аргументы.
Wolkodav
603 / 456 / 32
Регистрация: 18.09.2012
Сообщений: 1,685
16.12.2012, 11:44 #6
Да в скобках функции может быть все, что угодно, лишь бы оно возращяло или имело или каким-то образом приводилось к типу которая принимает функция.
sokratik1
0 / 0 / 0
Регистрация: 28.09.2012
Сообщений: 9
19.12.2012, 23:53 #7
Цитата Сообщение от Wolkodav Посмотреть сообщение
Стек реализован по принципу первый пришёл первый ушёл.
что за бред? почему? стек работает по принципу LIFO: последним вошел - первым вышел! т.е. элемент который вы последним положили будет первым извлекаться!

Добавлено через 2 часа 15 минут
Цитата Сообщение от sokratik1 Посмотреть сообщение
что за бред? почему? стек работает по принципу LIFO: последним вошел - первым вышел! т.е. элемент который вы последним положили будет первым извлекаться!
хотя логика ваших ваших рассуждений вроде верна
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.12.2012, 23:53
Привет! Вот еще темы с ответами:

Создать класс для работы со стеком действительных чисел - C++
При решении задач необходимо описать класс, который использу- ется для представления элементов динамической структуры данных. Затем...

Создать класс для работы со стеком. Элемент стека – действительное число - C++
Создать класс для работы со стеком. Элемент стека – действительное число. Применить класс для вывода возрастающих серий последовательности...

Принцип работы функции - C++
Помогите, пожалуйста, разобраться в принципе работы функции //Функция находит самую длинную неубывающую подпоследовательность void...

Принцип работы конструктора - C++
Объясните пожалуйста на простом примере принцип работы конструктора в С++. Я сейчас начал их изучать и никак не могу въехать. Спасибо.


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

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

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