Инфиксные префиксные и постфиксные выражения

Презентация к уроку в 10 классе «Префиксная и постфиксная форма записи».

Скачать:

Вложение Размер
prefiksnaya_i_postfiksnaya_forma_zapisi.pptx 163.77 КБ

Предварительный просмотр:

Подписи к слайдам:

Префиксная и постфиксная формы записи выражений

Структура, в которой одни элементы, «подчиняются» другим, называется иерархией . В информатике иерархическую структуру называют деревом . корень лист лист лист лист лист

Дерево состоит из узлов и связей между ними (они называются дугами) дуга корень листья промежуточные узлы

A D B E F G C «Сыновья» А : B, C . «Родитель» B : A . «Потомки» А : B, C , D, E, F, G . «Предки» F : A, C . Корень — узел, не имеющий предков (A) . Лист — узел, не имеющий потомков (D, E, F, G) . Высота — наибольшее расстояние от корня до листа.

Деревья — классификации Псовые Енотовые Медвежьи Кошачьи Гиеновые Мангустовые Псообразные Кошкообразные Хищные Глава 1. Псообразные 1.1. Псовые 1.2. Енотовые 1.3. Медвежьи … Глава 2. Кошкоообразные 2.1 . Кошачьи 2.2 . Гиеновые 2.3. Мангустовые … многоуровневый список

Иерархия — файловая система Документы Фотографии Доходы .doc Расходы . odt Отдых.txt Папа.jpg Мама.gif Тексты Документы Тексты Фотографии Доходы.doc Расходы.odt Отдых.txt Папа. jpg Мама. gif Документы Доходы.doc Расходы.odt Отдых.txt Тексты Фотографии Папа. jpg Мама. gif

Деревья и арифметические выражения a 3 — + * 5 2 b * (a+3)*5−2*b (- (*(+(a,3),5) ,*(2,b) )) ( корень ( левое , правое )) — * + a 3 5 * 2 b Префиксная форма — операция перед данными. Двоичное дерево! ! левый сын правый сын

Префиксная форма — вычисление с конца — * + a 3 5 * 2 b — * + a 3 5 ( 2 * b ) — * ( a+3) 5 ( 2 * b ) — ( a+3)*5 ( 2 * b ) ( a+3)*5 — (2 * b ) Скобки не нужны, вычисляется однозначно! ! Идём с конца, встретили знак операции — выполнили её.

Префиксная форма — вычисление с конца (идём с конца, встретили знак операции — выполнили её). Операция записывается перед данными! Пример: ( a+3)* 5− ( 2 * b ) -*+a35 * 2 b 1) — * + a 3 5 ( 2 * b ) 2) — * ( a+3) 5 ( 2 * b ) 3) — ( a+3)*5 ( 2 * b ) (корень (левое, правое))

Постфиксная форма ( левое-правое-корень ) a 3 — + * 5 2 b * (a+3)*5−2*b a 3 + 5 * 2 b * — Вычисляется с начала! ! (a+3) 5 * 2 b * — (a+3)*5 2 b * — (a+3)*5 ( 2 * b ) — (a+3)*5 — ( 2 * b )

Постфиксная форма . Вычисляется с начала! (a+3)*5−2*b Пример: a3+5 *2b *- 1) (a+3 ) 5 * 2 b * — 2) (a+3 )*5 2 b * — 3) (a+3 )*5 ( 2 * b ) — левое, правое, корень Операция записывается после данных!

Постфиксная форма для компьютера предпочтительней Когда программа на языке программирования высокого уровня переводится в машинные коды, математические выражения записываются в бесскобочной постфиксной форме, так и вычисляются. Когда программа доходит до знака операции, все данные для этой операции уже готовы. a 3 + 5 * 2 b * -

Определите выражени е , соответствующее данному дереву, в «нормальном» виде со скобками (эту форму называют инфиксной — операция записывается между данными). Постройте постфиксную форму. Решение: a- ( b+c )*d Постфиксная форма: abc+d *- b c — + a d *

Записать выражение в префиксной форме: (2* a-3*d)*c+2*b + * — * 2 a * 3 d c * 2 b префиксная форма Идём с конца, встретили знак операции — выполнили её.

Записать выражение в постфиксной форме: (2* a-3*d)*c+2*b 2 a * 3 d * — c * 2 b * + постфиксная форма Вычисляется с начала!

(2* a-3*d)*c+2*b 2 * 3 d — c а * b + * 2 *

Выполнить самостоятельно в тетради: задания 1б, 2а, 3а ( у чебник, стр. 49−50) Ответы: 1б — a- (b- (c-d)) a b c d — — — 2a * + a b + c * 2 d a b + c 2 d * + * 3a 66 (12+6)*(7−3−1)+12 + * + 12 6 — — 7 3 1 12

Домашнее задание: Учебник стр. 38−40 читать Задания 1в, 2в, 3б,в письменно в тетради

По теме: методические разработки, презентации и конспекты

Презентация к уроку алгебры и начала анализа в 10 классе (профильный уровень) по теме «Тригонометрическая форма записи комплексных чисел».

Презентация к уроку алгебры и начала анализа в 10 классе (профильный уровень) по теме «Тригонометрическая форма записи комплексных чисел».

Презентация к уроку алгебры и начала анализа в 10 классе (профильный уровень) по теме «Тригонометрическая форма записи комплексных чисел».

Презентация к уроку алгебры и начала анализа в 10 классе (профильный уровень) по теме «Тригонометрическая форма записи комплексных чисел».

Урок «Формы записи алгоритмов» в 6 классе по программе Л.Л.Босовой. К уроку прилагается презентация из 20 слайдов и дидактические материалы. Практическая работа проводится в среде "ЛогоМиры.

Рекомендуется использовать презентацию на начальном уровне знакомства с алгоритмами 5−6 класс.

Технологическая карта к уроку №25 по информатике в 6 классе по теме " Форма записи алгоритмов " по ФГОС.

Читайте также:  Датчик вскрытия корпуса компьютера

Префиксы «пре», «пост» и «ин» относятся к относительной позиции оператора по отношению к операндам. В префиксной записи операция предшествует операндам, в постфиксной следует за операндами, а в инфиксной записи операция разделяет два операнда.

Вычисление выражения А + В * С, записанное в стандартной инфиксной записи, требует знания того, какая из двух операций выполняется первой. В случае + и * мы знаем, что умножение выполняется раньше сложения (при отсутствии скобок). Следовательно, выражение А + В * С интерпретируется как А + (В * С). Говорят, что умножение имеет более высокий приоритет, чем сложение.

Предположим, что мы хотим записать выражение А + В * С в постфиксной записи. Учитывая правила приоритетности операций, мы сначала преобразуем часть выражения, которая вычисляется первой — умножение. Выполняя преобразование поэтапно, получим

А + (В * С) — скобки для выделения

А + (В С *) — преобразование операции умножения

А (В С *) + — преобразование операции сложения

А В С * + — постфиксная форма

Единственным правилом, используемым в процессе преобразования, является то, что операции с более высоким приоритетом преобразуются первыми, а после того, как операция преобразована к постфиксной форме, она рассматривается как один единый операнд. Рассмотрим теперь тот же пример, но приоритет выполнения операций изменим при помощи скобок:

(А + В) * С — инфиксная форма

(А В +) * С — преобразование операции сложения

(А В +) С * — преобразование операции умножения

А В + С * — постфиксная форма

Правила приоритетности для преобразования из инфиксной в префиксную форму аналогичны. Единственное отличие от постфиксного преобразования состоит в том, что операция помещается перед операндами, а не после них.

Примеры выражений в инфиксной, постфиксной и префиксной формах:

Когда вы записываете арифметическое выражение вроде B * C, то его форма предоставляет вам достаточно информации для корректной интерпретации. В данном случае мы знаем, что переменная B умножается на переменную C, поскольку оператор умножения * находится в выражении между ними. Такой тип записи называется инфиксной, поскольку оператор расположен между (in between) двух операндов, с которыми он работает.

Рассмотрим другой инфиксный пример: A + B * C. Операторы + и * по-прежнему располагаются между операндами, но тут уже есть проблема. С какими именно операндами они будут работать? + работает с A и B или * принимает B и C? Выражение выглядит неоднозначно.

Фактически, вы можете читать и писать выражения такого типа долгое время, и они не будут вызывать у вас вопросов. Причина в том, что вы кое-что знаете о + и *. Каждый оператор имеет свой приоритет. Операторы с высоким приоритетом используются прежде операторов с низким. Единственной вещью, которая может изменить порядок приоритетов, являются скобки. Для арифметических операций умножение и деление стоят выше сложения и вычитания. Если появляются два оператора одинакового приоритета, то используются порядок слева направо, или их ассоциативность.

Давайте интерпретируем вызвавшее затруднение выражение A + B * C, используя приоритет операторов. B и C перемножаются первыми, затем к результату добавляется A. (A + B) * C заставит выполнить сложение A и B перед умножением. В выражении A + B + C по очерёдности (через ассоциативность) первым будет вычисляться самый левый +.

Хотя это очевидно для вас, помните: компьютер нуждается в точном знании того, как и в какой последовательности вычисляются операторы. Одним из способов записи выражения, гарантирующим, что не возникнет путаницы по отношению к порядку операций, является создание того, что называется выражением с полностью расставленными скобками. Такой тип выражения использует пару скобок для каждого оператора. Скобки диктуют порядок операций, так что здесь не возникает многозначности. Так же отпадает необходимость помнить правила расстановки приоритетов.

Выражение A + B * C + D может быть переписано как ((A + (B * C)) + D) с целью показать, что умножение происходит в первую очередь, а затем следует крайнее левое сложение. A + B + C + D перепишется в (((A + B) + C) + D), поскольку операции сложения ассоциируются слева направо.

Существует ещё два очень важных формата выражений, которые на первый взгляд могут показаться вам неочевидными. Рассмотрим инфиксную запись A + B. Что произойдёт, если мы поместим оператор перед двумя операндами? Результирующее выражение будет + A B. Также мы можем переместить оператор в конец, получив A B +. Всё это выглядит несколько странным.

Эти изменения позиции оператора по отношению к операндам создают два новых формата — префиксный и постфиксный. Префиксная запись выражения требует, чтобы все операторы предшествовали двум операндам, с которыми они работают. Постфиксная, в свою очередь, требует, чтобы операторы шли после соответствующих операндов. Несколько дополнительных примеров помогут прояснить этот момент (см. таблицу 2).

Читайте также:  Без наушников нет звука на телефоне

A + B * C в префиксной нотации можно переписать как + A * B C. Оператор умножения ставится непосредственно перед операндами B и C, указывая на приоритет * над +. Затем следует оператор сложения перед A и результатом умножения.

В постфиксной записи выражение выглядит как A B C * +. Порядок операций вновь сохраняется, поскольку * находится непосредственно после B и C, обозначая, что он имеет приоритет выше следующего +. Хотя операторы перемещаются и теперь находятся до или после соответствующих операндов, порядок последних по отношению друг к другу остаётся в точности таким, как был.

Таблица 2: Примеры инфиксной, префиксной и постфиксной записи
Инфиксная запись Префиксная запись Постфиксная запись
A + B + A B A B +
A + B * C + A * B C A B C * +

А сейчас рассмотрим инфиксное выражение (A + B) * C. Напомним, что в этом случае запись требует наличия скобок для указания выполнить сложение перед умножением. Однако, когда A + B записывается в префиксной форме, то оператор сложения просто помещается перед операндами: + A B. Результат этой операции является первым операндом для умножения. Оператор умножения перемещается в начало всего выражения, давая нам * + A B C. Аналогично, в постфиксной записи A B + явно указывается, что первым происходит сложение. Умножение может быть выполнено для получившегося результата и оставшегося операнда C. Соответствующим постфиксным выражением будет A B + C *.

Рассмотрим эти три выражения ещё раз (см. таблицу 3). Происходит что-то очень важное. Куда ушли скобки? Почему они не нужны нам в префиксной и постфиксной записи? Ответ в том, что операторы больше не являются неоднозначными по отношению к своим операндам. Только инфиксная запись требует дополнительных символов. Порядок операций внутри префиксного и постфиксного выражений полностью определён позицией операторов и ничем иным. Во многом именно это делает инфиксную запись наименее желательной нотацией для использования.

Таблица 3: Выражение со скобками
Инфиксное выражение Префиксное выражение Постфиксное выражение
(A + B) * C * + A B C A B + C *

Таблица 4 демонстрирует некоторые дополнительные примеры инфиксных выражений и эквивалентных им префиксных и постфиксных записей. Убедитесь, что вы понимаете, почему они эквивалентны с точки зрения порядка выполнения операций.

Таблица 4: Дополнительные примеры инфиксной, префиксной и постфиксной записи
Инфиксное выражение Префиксное выражение Постфиксное выражение
A + B * C + D + + A * B C D A B C * + D +
(A + B) * (C + D) * + A B + C D A B + C D + *
A * B + C * D + * A B * C D A B * C D * +
A + B + C + D + + + A B C D A B + C + D +

Преобразование инфиксного выражения в префиксное и постфиксное¶

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

Первой из рассматриваемых нами техник будет использование идеи полной расстановки скобок в выражении, рассмотренной нами ранее. Напомним, что A + B * C можно записать как (A + (B * C)), чтобы явно показать приоритет умножения перед сложением. Однако, при более близком рассмотрении вы увидите, что каждая пара скобок также отмечает начало и конец пары операндов с соответствующим оператором по середине.

Взгляните на правую скобку в подвыражении (B * C) выше. Если мы передвинем символ умножения с его позиции и удалим соответствующую левую скобку, получив B C *, то произойдёт конвертирование подвыражение в постфиксную нотацию. Если оператор сложения тоже передвинуть к соответствующей правой скобке и удалить связанную с ним левую скобку, то результатом станет полностью постфиксное выражение (см. рисунок 6).

Рисунок 6: Перемещение операторов вправо для постфиксной записи

Если мы сделаем тоже самое, но вместо передвижения символа на позицию к правой скобке, сдвинем его к левой, то получим префиксную нотацию (см. рисунок 7). Позиция пары скобок на самом деле является ключом к окончательной позиции заключённого между ними оператора.

Рисунок 7: Перемещение операторов влево для префиксной записи.

Таким образом, при преобразовании выражения (неважно, насколько сложного) в префиксную или постфиксную запись для установления порядка выполнения операций используется полная расстановка скобок. Затем находящийся внутри них оператор передвигается на крайнюю левую или крайнюю правую позицию — в зависимости от того, префиксную или постфиксную запись вы хотите получить.

Вот более сложное выражение: (A + B) * C — (D — E) * (F + G). Рисунок 8 демонстрирует его преобразование в постфиксный и префиксный виды.

Рисунок 8: Преобразование сложного выражения к префиксной и постфиксной записи.

Обобщённое преобразование из инфиксного в постфиксный вид¶

Нам необходимо разработать алгоритм преобразования любого инфиксного выражения в постфиксное. Для этого посмотрим ближе на сам процесс конвертирования.

Читайте также:  Дана матрица а найдите указанный элемент а32

Рассмотрим ещё раз выражение A + B * C. Как было показано выше, его постфиксным эквивалентом является A B C * +. Мы уже отмечали, что операнды A, B и C остаются на своих местах, а местоположение меняют только операторы. Ещё раз взглянем на операторы в инфиксном выражении. Первым при проходе слева направо нам попадётся +. Однако, в постфиксном выражении + находится в конце, так как следующий оператор, *, имеет приоритет над сложением. Порядок операторов в первоначальном выражении обратен результирующему постфиксному выражению.

В процессе обработки выражения операторы должны где-то храниться, пока не найден их соответствующий правый операнд. Также порядок этих сохраняемых операторов может быть обратным (из-за их приоритета), как в данном примере со сложением и умножением. Поскольку оператор сложения, появляющийся перед оператором умножения, имеет более низкий приоритет, то он должен появиться после использования последнего. Из-за такого обратного порядка имеет смысл рассмотреть использование стека для хранения операторов до тех пор, пока они не понадобятся.

Что насчёт (A + B) * C? Напомним его постфиксный эквивалент: A B + C *. Повторимся, что обрабатывая это инфиксное выражение слева направо, первым мы встретим +. В этом случае, когда мы увидим *, + уже будет помещён в результирующее выражение, поскольку имеет преимущество над * в силу использования скобок. Теперь можно приступить к рассмотрению работы алгоритма преобразования. Когда мы видим левую скобку, то сохраняем её как знак, что должен будет появиться другой оператор с высоким приоритетом. Он будет ожидать, пока не появится соответствующая правая скобка, чтобы отметить его местоположение (вспомните технику полной расстановки скобок). После появления правой скобки оператор выталкивается из стека.

Поскольку мы сканируем инфиксное выражение слева направо, то для хранения операторов будем использовать стек. Это предоставит нам обратный порядок, который был отмечен в первом примере. На вершине стека всегда будет последний сохранённый оператор. Когда бы мы не прочитали новый оператор, мы должны сравнить его по приоритету с операторами в стеке (если таковые имеются).

Предположим, что инфиксное выражение есть строка токенов, разделённых пробелами. Токенами операторов являются *, /, + и — вместе с правой и левой скобками, ( и ). Токены операндов — это однобуквенные идентификаторы A, B, C и так далее. Следующая последовательность шагов даст строку токенов в постфиксном порядке.

  1. Создать пустой стек с названием opstack для хранения операторов. Создать пустой список для вывода.
  2. Преобразовать инфиксную строку в список, используя строковый метод split .
  3. Сканировать список токенов слева направо.
    • Если токен является операндом, то добавить его в конец выходного списка.
    • Если токен является левой скобкой, положить его в opstack .
    • Если токен является правой скобкой, то выталкивать элементы из opstack пока не будет найдена соответствующая левая скобка. Каждый оператор добавлять в конец выходного списка.
    • Если токен является оператором *, /, + или — , поместить его в opstack . Однако, перед этим вытолкнуть любой из операторов, уже находящихся в opstack , если он имеет больший или равный приоритет, и добавить его в результирующий список.

    #. Когда входное выражение будет полностью обработано, проверить opstack . Любые операторы, всё ещё находящиеся в нём, следует вытолкнуть и добавить в конец итогового списка.

    Рисунок 9 демонстрирует алгоритм преобразования, работающий над выражением A * B + C * D. Заметьте, что первый оператор * удаляется до того, как мы встречаем оператор +. Также + остаётся в стеке, когда появляется второй *, поскольку умножение имеет приоритет перед сложением. В конце инфиксного выражения из стека дважды происходит выталкивание, удаляя оба оператора и помещая + как последний элемент в результирующее постфиксное выражение.

    Рисунок 9: Преобразование A * B + C * D в постфиксную запись

    Чтобы закодировать алгоритм на Python, мы будем использовать словарь под именем prec для хранения значений приоритета операторов. Он связывает каждый оператор с целым числом, которые можно сравнивать с числами других операторов, как уровень приоритетности (для этого мы произвольно выбрали целые числа 3, 2 и 1). Левая скобка получит самое низкое значение. Таким образом, любой сравниваемый с ней оператор будет иметь приоритет выше и располагаться над ней. Строка 15 определяет, что операнды могут быть любыми символами в верхнем регистре или цифрами. Полная функция преобразования показана в ActiveCode 8.

    Оцените статью
    Adblock detector