Стек. Примеры использования стека

Сентябрь 7, 2022

Главная
Алгебра
Стек. Примеры использования стека

Содержание

2. Абстрактный тип данных Стек Стеком называется последовательность элементов одного и того же типа, к которой можно
3. Операции со стеком CreateStack() - создает пустой стек DeleteStack () – уничтожает стек IsEmpty() – функция
4. Алгебраические выражения Инфиксная запись выражений: каждый бинарный оператор помещается между своими операндами Префиксная запись выражений (Prefix):
5. Алгебраические выражения
6. Преобразование инфиксной формы в Prefix и Postfix Допустим, инфиксное выражение полностью заключено в скобки Преобразование в
7. Примеры Преобразование в префиксную форму: ( ( A + B ) * C ) + *
8. Преимущества префиксной и постфиксной форм записи Не нужны приоритеты операций, правила ассоциативности, скобки Алгоритмы распознавания выражений
9. Вычисление постфиксных выражений Допустим необходимо вычислить выражение: 2*(3+4) Его постфиксная запись: 234+* Порядок выполнения операций: Помещаем
10. Пример:
11. Псевдокод алгоритма Предположения: Строка содержит синтаксически правильное выражение Унарные операции и операции возведения в степень не
12. Псевдокод алгоритма For (каждый символ ch в строке) { if (ch является операндом) // помещаем ch
13. Преобразование инфиксных выражение в постфиксные Будем использовать: Стек для хранения операций и скобок Строку PostfixExp для
14. Преобразование инфиксных выражение в постфиксные Алгоритм: Если встретился операнд – помещаем его в строку Если встретилась
15. Пример: A-(B+C*D)/F)
16. Пример: A+B*(C/B+Z*(A+D))
17. Пример: A+B*(C/B+Z*(A+D)) A+B*(C/B+Z*(A+D)) Результат: ABCB/ZAD+*+*+
18. Псевдокод алгоритма: For (ch) { Swith (ch) { case operand: PostfixExp= PostfixExp+ch; break; case ‘(‘: Push(ch);
20. Скачать презентацию

Слайд 2

Абстрактный тип данных Стек
Стеком называется последовательность элементов одного и того

же типа, к которой можно добавлять новые элементы и удалять элементы последовательности.
Причем как добавление элементов, так и удаление элементов производится с одного и того же конца последовательности, называемого вершиной стека.

Слайд 3

Операции со стеком
CreateStack() - создает пустой стек
DeleteStack () – уничтожает стек

IsEmpty() – функция определения пустоты стека ли стек
Push(NewElement) – добавляет новый элемент NewElement в стек
Pop() – удаляет верхний элемент из стека
Peek() – возвращает значение верхнего элемента (вершины стека) без его удаления

Слайд 4

Алгебраические выражения
Инфиксная запись выражений: каждый бинарный оператор помещается между своими операндами
Префиксная запись

выражений (Prefix): каждый бинарный оператор помещается перед своими операндами
(Польская запись)
Постфиксная запись выражений (Postfix): каждый бинарный оператор помещается после своих операндов
(Обратная Польская запись)

Слайд 5

Алгебраические выражения

Слайд 6

Преобразование инфиксной формы в Prefix и Postfix
Допустим, инфиксное выражение полностью заключено

в скобки
Преобразование в префиксную форму: каждый оператор перемещается на позицию соответствующей открывающейся скобки (перед операцией)
Преобразование в постфиксную форму: каждый оператор перемещается на позицию соответствующей закрывающейся скобки (после операцией)
Скобки убираются

Слайд 7

Примеры
Преобразование в префиксную форму: ( ( A + B ) * C

) + *
*+ABC
Преобразование в постфиксную форму: ( ( A + B ) * C ) + * AB+C*

Слайд 8

Преимущества префиксной и постфиксной форм записи
Не нужны приоритеты операций, правила ассоциативности,

скобки
Алгоритмы распознавания выражений и вычисления более просты

Слайд 9

Вычисление постфиксных выражений
Допустим необходимо вычислить выражение: 2(3+4)
Его постфиксная запись: 234+
Порядок выполнения операций:
Помещаем в

стек значения всех операндов, пока не встретим знак операции
Выталкиваем из стека 2 операнда
Производим с ними соответствующую операцию
Результат помещаем в стек
Повторяем операции до тех пор, пока не кончится строка символов

Слайд 10

Пример:

Слайд 11

Псевдокод алгоритма
Предположения:
Строка содержит синтаксически правильное выражение
Унарные операции и операции возведения в

степень не используются
Операнды задаются строчными буквами

Слайд 12

Псевдокод алгоритма
For (каждый символ ch в строке)
{ if (ch является операндом)

// помещаем ch в стек
Push(ch);
else
{ Opign=ch;
Op2=Pop(); //извлекаем значение из вершины
Op1=Pop(); //извлекаем значение из вершины
// выполняем соответствующую операцию
Result=Op1 Opsign Op2; // помещаем результат в стек
Push(Result);
}; // конец оператора if
} // конец оператора For

Слайд 13

Преобразование инфиксных выражение в постфиксные
Будем использовать:
Стек для хранения операций и скобок
Строку

PostfixExp для формирования постфиксного выражения

Слайд 14

Преобразование инфиксных выражение в постфиксные
Алгоритм:
Если встретился операнд – помещаем его в

строку
Если встретилась ‘(’ – помещаем в стек
Если встретился оператор:
Если стек пуст – помещаем оператор в стек
Если стек не пуст – операторы более высокого приоритета выталкиваются и помещаются в строку, пока не встретится ‘(’ или оператор более низкого приоритета
Если встретился символ ‘)’ , то все элементы выталкиваются из стека и помещаются в строку, пока не встретится соответствующая ‘(‘
Достигнув конца строки, все элементы стека добавляются в строку

Слайд 15

Пример: A-(B+C*D)/F)

Слайд 16

Пример: A+B(C/B+Z(A+D))

Слайд 17

Пример: A+B(C/B+Z(A+D))
A+B(C/B+Z(A+D))
Результат: ABCB/ZAD+++

Слайд 18

Псевдокод алгоритма:
For (ch)
{ Swith (ch)
{ case operand:
PostfixExp= PostfixExp+ch;
break;
case ‘(‘:

Push(ch);
break;
case ‘)’:
While( ‘(‘)
{ PostfixExp= PostfixExp + Peek();
Pop();
};

Стек. Примеры использования стека

Содержание

Абстрактный тип данных Стек Стеком называется последовательность элементов одного и того

Операции со стекомCreateStack() - создает пустой стекDeleteStack () – уничтожает стек

Алгебраические выраженияИнфиксная запись выражений: каждый бинарный оператор помещается между своими операндамиПрефиксная запись

Алгебраические выражения

Преобразование инфиксной формы в Prefix и PostfixДопустим, инфиксное выражение полностью заключено

ПримерыПреобразование в префиксную форму: ( ( A + B ) * C

Преимущества префиксной и постфиксной форм записиНе нужны приоритеты операций, правила ассоциативности,

Вычисление постфиксных выраженийДопустим необходимо вычислить выражение: 2*(3+4)Его постфиксная запись: 234+*Порядок выполнения операций:Помещаем в

Пример:

Псевдокод алгоритмаПредположения:Строка содержит синтаксически правильное выражениеУнарные операции и операции возведения в

Псевдокод алгоритмаFor (каждый символ ch в строке){ if (ch является операндом)

Преобразование инфиксных выражение в постфиксныеБудем использовать:Стек для хранения операций и скобокСтроку

Преобразование инфиксных выражение в постфиксныеАлгоритм:Если встретился операнд – помещаем его в