Разное

Польская стековая система счисления: Обратная польская запись / Хабр

Содержание

Обратная польская запись / Хабр

Два плюс два, умножить на два?

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


В математике существует древняя традиция помещать оператор между операндами (x+y), а не после операндов (xy+). Форма с оператором между операндами называется инфиксной записью. Форма с оператором после операндов называется постфиксной, или обратной польской записью в честь польского логика Я. Лукасевича (1958), который изучал свойства этой записи.

Обратная польская запись имеет ряд преимуществ перед инфиксной записью при выражении алгебраических формул. Во-первых, любая формула может быть выражена без скобок. Во-вторых, она удобна для вычисления формул в машинах со стеками. В-третьих, инфиксные операторы имеют приоритеты, которые произвольны и нежелательны. Например, мы знаем, что ab+c значит (ab)+c, а не a(b+c), поскольку произвольно было определено, что умножение имеет приоритет над сложением. Но имеет ли приоритет сдвиг влево перед операцией И? Кто знает? Обратная польская запись позволяет устранить такие недоразумения.

Постановка задачи

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

Алгоритм перевода в обратную польскую запись

Существует несколько алгоритмов для превращения инфиксных формул в обратную польскую запись. Мы рассмотрим переработанный алгоритм, идее которого предложена Э. Дейкстра (E.W. Dijkstra). Предположим, что формула состоит из переменных, двухоперандных операторов +,-,*,/,^, а также левой и правой скобок. Чтобы отметить конец формулы, мы будем вставлять символ после её последнего символа и перед первым символом следующей формулы.


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

В таблице показана зависимость ситуации от того, какой вагон отправился в Техас последним и какой вагон находится у стрелки. Первый вагон (помеченный символом ⊥) всегда отправляется в Техас.

Числа соответствуют следующим ситуациям:

1. Вагон на стрелке отправляется в Техас

2. Последний вагон, направившийся в Техас, разворачивается и направляется в Калифорнию

3. Вагон, находящийся на стрелке, и последний вагон, отправившийся в Техас, угоняются и исчезают

4. Остановка. Символы, находящиеся на Калифорнийской ветке, представляют собой формулу в обратной польской записи, если читать слева направо

5. Остановка. Произошла ошибка. Изначальная формула была некорректно сбалансирована

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

Порядок следования переменных в инфиксной и постфиксной записи одинаков. Однако порядок следования операторов не всегда один и тот же. В обратной польской записи операторы появляются в том порядке, в котором они будут выполняться.

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

Обратная польская запись идеально подходит для вычисления формул на компьютере со стеком. Формула состоит из n символов, каждый из которых является либо операндом, либо оператором. Алгоритм для вычисления формулы в обратной польской записи с использованием стека прост. Нужно просто прочитать обратную польскую запись слева направо. Если встречается операнд, его нужно пометить в стек. Если встречается оператор, нужно выполнить заданную им операцию.

В качестве примера рассмотрим вычисление следующего выражения: (8+2*5)/(1+3*2-4). Соответствующая формула в обратной польской записи выглядит так: 825*+132*+4-/

Число на вершине стека – это правый операнд (а не левый). Это очень важно дл операций деления, вычитания и возведения в степень, поскольку порядок следования операндов в данном случае имеет значение (в отличие от операций сложения и умножения). Другими словами, операция деления действует следующим образом: сначала в стек помещается числитель, потом знаменатель, и тогда операция даёт правильный результат. Отметим, что преобразовать обратную польскую запись в машинный код очень легко: нужно просто двигаться по формуле в обратной польской записи, записывая по одной команде для каждого символа. Если символ является константой или переменной, нужно вписывать команду помещения этой константы или переменной в стек, если символ является оператором, нужно вписывать команду выполнения это операции.


P.S. Исходные коды вы, как всегда, можете скачать на моём сайте, пока он не ляжет под хабраэффектом.

P.P.S. Теперь все могут написать свой калькулятор. С блэкджеком и скобками.

как же приготовить хот-дог? / Хабр

Будучи дилетантом в области разработки приложений, я испытал сложности с пониманием алгоритма работы обратной польской нотации, а если быть точнее — алгоритма подготовки стека. Делу так же мало помогли статьи в «интернетах».

Все началось с того, что я затеял создание несложного интерпретатора для собственного проекта. Для решения сложных выражений на выбор было два алгоритма: рекурсивный спуск и обратная польская запись. Очевидная простота и подход к решению задачи (а может и само название) позволили последнему стать предметом для изучения.

Делу помогли две статьи. Одна из них на википедии, а вторая была написана замечательным пользователем хабра, GORKOFF, который объяснил все буквально «на пальцах».

Однако до конца я так и не понял тот важный вопрос: как же построить стек?


Не буду больше ходить вокруг да около, начнем по порядку. Представим, что у нас имеется некий массив с операциями и операндами, в который записано следующее выражение: 5*2+10. Переведем это выражение в тот вид, который «скушает» алгоритм обратной польской нотации. Для этого нам понадобится стек операций и массив выхода. Далее важно определить приоритет операций. Это необходимо для правильного распределения порядка математических действий, чтобы, например, отдавать предпочтение умножению перед сложением.

Высокий приоритет (1): здесь, следуя законам математики, разместим умножение и деление.

Низкий приоритет (2): сюда попадают сложение и вычитание.

После того, как мы определились с приоритетами, перейдем к самому строительству. Перед тем как начать, я должен кое-что пояснить:

все числа являются операндами. Они всегда записываются в массив выхода. Знаки сложения, вычитания и так далее — являются операциями. Но они могут находиться как в стеке операций, так и в массиве выхода. Куда они отправятся — зависит от того, что находится последним в стеке. Идем по порядку, слева направо:

Читаем «5».
Операнд, кладем в массив выхода.

Добавляем 5 в массив выхода.

Массив выхода: 5.

Стек операций: пусто.

Читаем «*».
Операция. В стеке операций нет ничего, поэтому мы кладем его в стек операций

Добавляем * в стек операций.

Массив выхода: 5.

Стек операций: *.

Читаем «2».
Операнд, кладем в массив выхода.

Добавляем 2 в массив выхода.

Массив выхода: 5, 2.

Стек операций: *.

Читаем «+».
Операция. Последний символ в стеке операций (*) имеет приоритет выше, чем текущий знак (+). Поэтому последний знак из стека операций мы перемещаем в массив выхода.

Перемещаем * в стек выхода. Добавляем + в стек операций.

Массив выхода: 5, 2, *.

Стек операций: +.

Читаем «10».
Операнд, кладем в массив выхода.

Добавляем 2 в массив выхода.

Массив выхода: 5, 2, *, 10.

Стек операций: +.

Так как все символы у нас закончились, мы просто выталкиваем всё из стека операций в массив выхода.

Массив выхода: 5, 2, *, 10, +.

Теперь уже можно решать полученную строку согласно алгоритму обратной польской нотации (слева-направо):

Решение

1) {5, 2, *, 10, +} {Пусто}

2) {2, *, 10, +} {5}

3) { *, 10, +} {5, 2}

4) {10, +} {10}

5) {+} {10, 10}

6) {} {20}

В результате мы имеем решение поставленной задачи:

5*2+10=20

Всей картины этот пример не демонстрирует. Попробуем более сложное выражение:

(6+10-4)/(1+1*2)+1

Читаем «(«.
Не смотря на то, что алгоритм ОПН считается бесскобочным, мы все равно считаем скобку за операцию. Так как это открывающая скобка, мы просто добавляем ее в стек.

Добавляем ( в стек операций.

Массив выхода: пусто.

Стек операций: (.

Читаем «6»

Добавляем в массив выхода.

Массив выхода: 6.

Стек операций: (.

Читаем «+»

Добавляем в стек операций.

Массив выхода: 6.

Стек операций: (, +.

Читаем «10»

Добавляем в массив выхода.

Массив выхода: 6, 10.

Стек операций: (, +.

Читаем «-«
Так как текущий знак (-) имеет равный приоритет перед последним знаком в стеке (+) мы всё равно выталкиваем знак из стека в операций в массив выхода, а текущий добавляем в стек.

Массив выхода: 6, 10, +.

Стек операций: (, -.

Читаем «4»

Добавляем в массив выхода.

Массив выхода: 6, 10, +, 4.

Стек операций: (, -.

Читаем «)»
Снова скобка, но теперь уже закрывающая. Здесь необходимо вытолкать все знаки из стека в массив до первой открывающей скобки. От обеих скобок нам попросту нужно избавиться.

Выталкиваем «-» в массив операций. Избавляемся от скобок.

Массив выхода: 6,10, +, 4, -.

Стек операций: пусто.

Читаем «/»

Добавляем в стек.

Массив выхода: 6,10, +, 4, -.

Стек операций: /.

Читаем «(«

Добавляем в стек.

Массив выхода: 6,10, +, 4, -.

Стек операций: /, (.

Читаем «1»

Добавляем в массив.

Массив выхода: 6,10, +, 4, -, 1.

Стек операций: /, (.

Читаем «+»

Добавляем в стек.

Массив выхода: 6,10, +, 4, -, 1.

Стек операций: /, (, +.

Читаем «1»

Добавляем в массив.

Массив выхода: 6,10, +, 4, -, 1, 1.

Стек операций: /, (, +.

Читаем «*»
Последний символ в стеке операций (+) имеет приоритет ниже, чем текущий знак (*). Поэтому последний знак из стека мы не трогаем, а просто добавляем как обычно текущий в стек.

Добавляем в стек.

Массив выхода: 6,10, +, 4, -, 1, 1.

Стек операций: /, (, +,*.

Читаем «2»

Добавляем в массив.

Массив выхода: 6,10, +, 4, -, 1, 1, 2.

Стек операций: /, (, +,*.

Читаем «)»
Снова закрывающая скобка, делаем все как в прошлый раз.

Выталкиваем * и + в массив операций. Избавляемся от скобок.

Массив выхода: 6,10, +, 4, -, 1, 1, 2, *, +.

Стек операций: /.

Читаем «+»

У знака деления приоритет выше. Выталкиваем / в массив. Добавляем + в стек.

Массив выхода: 6,10, +, 4, -, 1, 1, 2, *, +, /.

Стек операций: +.

Читаем «1»

Добавляем в массив.

Массив выхода: 6,10, +, 4, -, 1, 1, 2, *, +, /, 1.

Стек операций: +.

Выражение закончено. Снова выталкиваем всё из стека операций в массив выхода.

Массив выхода: 6,10, +, 4, -, 1, 1, 2, *, +, /, 1, +.

Снова считаем.

Решение

1) {6,10, +, 4, -, 1, 1, 2, *, +, /, 1, +} {Пусто}

2) {10, +, 4, -, 1, 1, 2, *, +, /, 1, +} {6}

3) {+, 4, -, 1, 1, 2, *, +, /, 1, +} {6,10}

4) {4, -, 1, 1, 2, *, +, /, 1, +} {16}

5) {-, 1, 1, 2, *, +, /, 1, +} {16,4}

6) {1, 1, 2, *, +, /, 1, +} {12}

7) {1, 2, *, +, /, 1, +} {12, 1}

8) {2, *, +, /, 1, +} {12, 1, 1}

9) {*, +, /, 1, +} {12, 1, 1, 2}

10) {+, /, 1, +} {12, 1, 2}

11) {/, 1, +} {12, 3}

12) {1, +} {4}

13) {+} {4, 1}

13) {} {5}

Итог: (6+10-4)/(1+1*2)+1=5

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

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

Тему, затрагивающую плюсы и минусы алгоритма ОПН, а так же его оптимизации я затрагивать не стану. Здесь я старался объяснить все буквально для тех, кто так же как я ищет решение этого вопроса.

Обратная польская запись — Википедия

Обра́тная по́льская запись (англ. Reverse Polish notation, RPN) — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись, обратная бесскобочная запись, постфиксная нотация, бесскобочная символика Лукасевича, польская инверсная запись, ПОЛИЗ.

Стековой машиной называется алгоритм, проводящий вычисления по обратной польской записи (см. ниже пример вычисления выражений).

История

Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем. Работа Хэмблина была представлена на конференции в июне 1957, и издана в 1957 и 1962.

Первыми компьютерами, поддерживающими обратную польскую нотацию, были KDF9 от English Electric Company, который был анонсирован в 1960 и выпущен (появился в продаже) в 1963, и американский Burroughs B5000, анонсирован в 1961, выпущен в том же 1963. Один из проектировщиков B5000, Р. С. Бартон, позже написал, что разработал обратную польскую запись независимо от Хэмблина, примерно в 1958, в процессе чтения книги по символьной логике, и до того как познакомился с работой Хэмблина.

Компания Friden перенесла ОПН в настольные калькуляторы, выпустив в июне 1964 модель EC-130. А в 1968 инженеры Hewlett-Packard разработали настольный калькулятор 9100A с поддержкой ОПН. Этот калькулятор сделал обратную польскую нотацию популярной среди учёных и инженеров, даже несмотря на то, что в ранней рекламе 9100A ОПН не упоминалась. В 1972 калькулятор HP-35 с поддержкой ОПН стал первым научным карманным калькулятором.

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

ОПН применялась в советском инженерном калькуляторе Б3-19М (совместная разработка с ГДР), выпущенном в 1976 году. Все выпускаемые в СССР вплоть до конца 1980-х годов программируемые микрокалькуляторы, за исключением «Электроника МК-85» и «Электроника МК-90», использовали ОПН — она проще реализовывалась и позволяла обойтись в программировании вычислений меньшим числом команд, по сравнению с обычной алгебраической нотацией, а количество программной памяти в этих моделях всегда было критическим ресурсом. ОПН используется в современных российских программируемых калькуляторах «Электроника МК-152» и «ЭЛЕКТРОНИКА МК-161», что обеспечивает их совместимость с программами, написанными для советских калькуляторов.

Определение

Чтобы дать индуктивное определение постфиксной нотации[1], обозначим выражения в инфиксной нотации E{\displaystyle E}, E1{\displaystyle E_{1}}, E2{\displaystyle E_{2}}, эквивалентные им выражения в постфиксной нотации E˙{\displaystyle {\dot {E}}} , E˙1{\displaystyle {\dot {E}}_{1}}, E˙2{\displaystyle {\dot {E}}_{2}} соответственно; o{\displaystyle o} — произвольный бинарный оператор, тогда:

1. Если E{\displaystyle E} — переменная или константа, то E˙{\displaystyle {\dot {E}}} есть E{\displaystyle E}.

2. Если E{\displaystyle E} — выражение вида E1oE2{\displaystyle E_{1}oE_{2}}, то E˙{\displaystyle {\dot {E}}} есть E˙1E˙2o{\displaystyle {\dot {E}}_{1}{\dot {E}}_{2}o}.

3. Если E{\displaystyle E} — выражение вида (E1){\displaystyle (E_{1})}, то E˙{\displaystyle {\dot {E}}} есть E˙1{\displaystyle {\dot {E}}_{1}}.

Описание

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

  • Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.
  • Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу.
  • Результатом вычисления выражения становится результат последней вычисленной операции.

Например, рассмотрим вычисление выражения 7 2 3 * − (эквивалентное выражение в инфиксной нотации: 7 − 2 * 3).

  1. Первый по порядку знак операции — «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду 7 6 − (результат умножения — 6, — заменяет тройку «2 3 *»).
  2. Второй знак операции — «−». Выполняется операция вычитания над операндами 7 и 6.
  3. Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.

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

Особенности обратной польской записи следующие:

  • Порядок выполнения операций однозначно задаётся порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.
  • В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, в инфиксной записи выражение 5 * (−3 + 8) использует знак «минус» как символ унарной операции (изменение знака числа), а выражение (10 − 15) * 3 применяет этот же знак для обозначения бинарной операции (вычитание). Конкретная операция определяется тем, в какой позиции находится знак. Обратная польская запись не позволяет этого: запись 5 3 − 8 + * (условный аналог первого выражения) будет интерпретирована как ошибочная, поскольку невозможно определить, что «минус» после 5 и 3 обозначает не вычитание; в результате будет сделана попытка вычислить сначала 5 − 3, затем 2 + 8, после чего выяснится, что для операции умножения не хватает операндов. Чтобы всё же записать это выражение, придётся либо переформулировать его (например, записав вместо выражения − 3 выражение 0 − 3), либо ввести для операции изменения знака отдельное обозначение, например, «±»: 5 3 ± 8 + *.
  • Так же, как и в инфиксной нотации, в ОПН одно и то же вычисление может быть записано в нескольких разных вариантах. Например, выражение (10 − 15) * 3 в ОПН можно записать как 10 15 − 3 *, а можно — как 3 10 15 − *
  • Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора (уменьшается количество нажимаемых клавиш), а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.

Вычисления на стеке

Общий порядок

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

  1. Обработка входного символа
    • Если на вход подан операнд, он помещается на вершину стека.
    • Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
  2. Если входной набор символов обработан не полностью, перейти к шагу 1.
  3. После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.

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

Пример вычисления выражений

Инфиксное выражение (1+2)×4+3{\displaystyle (1+2)\times 4+3} в ОПН может быть записано так: 1 2 + 4 × 3 +

Вычисление производится слева направо, ввод интерпретируется как указано в приведённой ниже таблице (указано состояние стека после выполнения операции, вершина стека выделена красным цветом):

Ввод Операция Стек
1 поместить в стек 1
2 поместить в стек 1, 2
+ сложение 3
4 поместить в стек 3, 4
* умножение 12
3 поместить в стек 12, 3
+ сложение 15

Результат, 15, в конце вычислений находится на вершине стека.

Клавиша «Ввод» (обозначаемая на калькуляторах как «Enter» или символом «↑») выполняет роль разделителя операндов, когда два операнда непосредственно следуют друг за другом. Если за операндом следует знак операции, то её нажатие не требуется, это сокращает количество действий, которые нужно выполнить для получения результата.

Преобразование из инфиксной нотации

Эдсгер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПЗ. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, 3 + 4 или 3 + 4 * (2 − 1)). Как и алгоритм вычисления ОПЗ, алгоритм сортировочной станции основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операции. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

Простой пример

Вход: 3 + 4

Добавим 3 к выходной строке (если прочитано число, то оно сразу добавляется к выходной строке).

Помещаем + (или его Идентификатор) в стек операций.

Добавим 4 к выходной строке.

Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операции в выходную строку. В нашем примере в стеке содержится только +.

Выходная строка: 3 4 +

В данном примере проявляются некоторые правила: все числа переносятся в выходную строку сразу после прочтения; когда выражение прочитано полностью, все оставшиеся в стеке операции выталкиваются в выходную строку.

Алгоритм

  • Пока есть ещё символы для чтения:
  • Читаем очередной символ.
  • Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.
  • Если символ является префиксной функцией (например, sin — синус), помещаем его в стек.
  • Если символ является открывающей скобкой, помещаем его в стек.
  • Если символ является закрывающей скобкой:
До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.

  • Если существуют разные виды скобок, появление непарной скобки также свидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — целая часть), добавляем к выходной строке символ этой функции.
  • Если символ является бинарной операцией о1, тогда:
1) пока на вершине стека префиксная функция…

… ИЛИ операция на вершине стека приоритетнее o1
… ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1
… выталкиваем верхний элемент стека в выходную строку;
2) помещаем операцию o1 в стек.
  • Когда входная строка закончилась, выталкиваем все символы из стека в выходную строку. В стеке должны были остаться только символы операций; если это не так, значит в выражении не согласованы скобки.
Ограничения и модификации

Алгоритм предполагает, что исходная строка корректна (проверяются не все ошибки), и все префиксные/постфиксные функции унарные.

Модификацию для многоместных функций с фиксированным количеством аргументов см. в основной статье.

Для операций вроде −x, являющихся как бинарными, так и унарными, нужна модификация: при обнаружении подобной операции система смотрит на предыдущий символ и определяет, чем будет минус, бинарной операцией или унарной функцией. Соответственно, в стеке и ОПЗ нужны разные символы для бинарного и унарного минуса.

Сложный пример

Приоритеты:

  • высокий: ^
  • средний: * /
  • низкий: + −
  • самый низкий: ( )
Вход: 3 + 4 * 2 / (1 − 5)^2

Читаем «3»
 Добавим «3» к выходной строке
  Выход: 3

Читаем «+»
 Кладём «+» в стек
  Выход: 3
  Стек: +

Читаем «4»
 Добавим «4» к выходной строке
  Выход: 3 4
  Стек: +

Читаем «*»
 Кладём «*» в стек
  Выход: 3 4
  Стек: + *

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2
  Стек: + *

Читаем «/»
 Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
  Выход: 3 4 2 *
  Стек: + /

Читаем «(»
 Кладём «(» в стек
  Выход: 3 4 2 *
  Стек: + / (

Читаем «1»
 Добавим «1» к выходной строке
  Выход: 3 4 2 * 1
  Стек: + / (

Читаем «−»
 Кладём «−» в стек
  Выход: 3 4 2 * 1
  Стек: + / ( −

Читаем «5»
 Добавим «5» к выходной строке
  Выход: 3 4 2 * 1 5
  Стек: + / ( -

Читаем «)»
 Выталкиваем «−» из стека в выходную строку, выталкиваем «(»
  Выход: 3 4 2 * 1 5 −
  Стек: + /

Читаем «^»
 Кладём «^» в стек
  Выход: 3 4 2 * 1 5 −
  Стек: + / ^

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2 * 1 5 − 2
  Стек: + / ^

Конец выражения
 Выталкиваем все элементы из стека в строку
  Выход: 3 4 2 * 1 5 − 2 ^ / +

Оптимизация выражений

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

Пример алгоритма упрощения выражения

Рассмотрим алгоритм, который осуществляет предвычисление констант в выражении. Дано выражение в ОПН. Нам понадобится стек для хранения смешанных данных (чисел и операторов).

Алгоритм подобен тому, который применяется для вычисления выражений. Мы просматриваем выражение слева направо.

Пока есть символы для чтения:

  • Читаем очередной символ.
  • Если символ является числом, помещаем его в стек.
  • Если символ является переменной, считая что переменная имеет значение null, помещаем символ в стек.
  • Если символ является оператором:
  • 1) (если все аргументы оператора, лежащие в стеке, имеют значение, отличное от null) выталкиваем аргументы оператора из стека и помещаем в стек результат операции;
  • 2) (если хотя бы один из аргументов имеет значение null) считая что результат операции null, кладём символ оператора в стек.

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

Пример работы алгоритма

Выражение
Инфиксая нотация: exp(-1/2*x)
Обратная Польская нотация: -1 2 / x * exp

Читаем: «-1»
 Кладём «-1» в стек
  Стек: -1

Читаем: «2»
 Кладём «2» в стек
  Стек: -1 2

Читаем: «/»
 Вычисляем частное, результат кладём в стек
  Стек: -0.5

Читаем: «x»
 Кладём «x» в стек со значением null
  Стек: -0.5 x(null)

Читаем: «*»
 Кладём «*» в стек со значением null
  Стек: -0.5 x(null) *(null)

Читаем «exp»
 Кладём «exp» в стек со значением null
  Стек: -0.5 x(null) *(null) exp(null)

Результат оптимизации: -0.5 x * exp

Данный метод, очевидно, не включает всех возможных способов оптимизации.

Примеры реализации

В статье «Обратная польская запись: примеры реализации» собраны примеры реализации обратной польской записи на различных языках программирования.

Практические реализации

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

Литература

  • Т. Пратт, М. Зелковиц. Языки программирования: разработка и реализация = Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation. — 4-е издание. — Питер, 2002. — 688 с. — (Классика Computer Science). — 4000 экз. — ISBN 5-318-00189-0.

Примечания

  1. ↑ А. В. Ахо, Р. Сети, Д. Д. Ульман. Компиляторы: принципы, технологии и инструменты. М.: «Вильямс», 2003. С. 51.

Ссылки

Языки программирования, использующие ОПН в качестве основной:

Другие ссылки:

Обратная польская запись — Википедия

Обра́тная по́льская запись (англ. Reverse Polish notation, RPN) — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись, обратная бесскобочная запись, постфиксная нотация, бесскобочная символика Лукасевича, польская инверсная запись, ПОЛИЗ.

Стековой машиной называется алгоритм, проводящий вычисления по обратной польской записи (см. ниже пример вычисления выражений).

История

Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем. Работа Хэмблина была представлена на конференции в июне 1957, и издана в 1957 и 1962.

Первыми компьютерами, поддерживающими обратную польскую нотацию, были KDF9 от English Electric Company, который был анонсирован в 1960 и выпущен (появился в продаже) в 1963, и американский Burroughs B5000, анонсирован в 1961, выпущен в том же 1963. Один из проектировщиков B5000, Р. С. Бартон, позже написал, что разработал обратную польскую запись независимо от Хэмблина, примерно в 1958, в процессе чтения книги по символьной логике, и до того как познакомился с работой Хэмблина.

Компания Friden перенесла ОПН в настольные калькуляторы, выпустив в июне 1964 модель EC-130. А в 1968 инженеры Hewlett-Packard разработали настольный калькулятор 9100A с поддержкой ОПН. Этот калькулятор сделал обратную польскую нотацию популярной среди учёных и инженеров, даже несмотря на то, что в ранней рекламе 9100A ОПН не упоминалась. В 1972 калькулятор HP-35 с поддержкой ОПН стал первым научным карманным калькулятором.

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

ОПН применялась в советском инженерном калькуляторе Б3-19М (совместная разработка с ГДР), выпущенном в 1976 году. Все выпускаемые в СССР вплоть до конца 1980-х годов программируемые микрокалькуляторы, за исключением «Электроника МК-85» и «Электроника МК-90», использовали ОПН — она проще реализовывалась и позволяла обойтись в программировании вычислений меньшим числом команд, по сравнению с обычной алгебраической нотацией, а количество программной памяти в этих моделях всегда было критическим ресурсом. ОПН используется в современных российских программируемых калькуляторах «Электроника МК-152» и «ЭЛЕКТРОНИКА МК-161», что обеспечивает их совместимость с программами, написанными для советских калькуляторов.

Определение

Чтобы дать индуктивное определение постфиксной нотации[1], обозначим выражения в инфиксной нотации E{\displaystyle E}, E1{\displaystyle E_{1}}, E2{\displaystyle E_{2}}, эквивалентные им выражения в постфиксной нотации E˙{\displaystyle {\dot {E}}} , E˙1{\displaystyle {\dot {E}}_{1}}, E˙2{\displaystyle {\dot {E}}_{2}} соответственно; o{\displaystyle o} — произвольный бинарный оператор, тогда:

1. Если E{\displaystyle E} — переменная или константа, то E˙{\displaystyle {\dot {E}}} есть E{\displaystyle E}.

2. Если E{\displaystyle E} — выражение вида E1oE2{\displaystyle E_{1}oE_{2}}, то E˙{\displaystyle {\dot {E}}} есть E˙1E˙2o{\displaystyle {\dot {E}}_{1}{\dot {E}}_{2}o}.

3. Если E{\displaystyle E} — выражение вида (E1){\displaystyle (E_{1})}, то E˙{\displaystyle {\dot {E}}} есть E˙1{\displaystyle {\dot {E}}_{1}}.

Описание

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

  • Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.
  • Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу.
  • Результатом вычисления выражения становится результат последней вычисленной операции.

Например, рассмотрим вычисление выражения 7 2 3 * − (эквивалентное выражение в инфиксной нотации: 7 − 2 * 3).

  1. Первый по порядку знак операции — «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду 7 6 − (результат умножения — 6, — заменяет тройку «2 3 *»).
  2. Второй знак операции — «−». Выполняется операция вычитания над операндами 7 и 6.
  3. Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.

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

Особенности обратной польской записи следующие:

  • Порядок выполнения операций однозначно задаётся порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.
  • В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, в инфиксной записи выражение 5 * (−3 + 8) использует знак «минус» как символ унарной операции (изменение знака числа), а выражение (10 − 15) * 3 применяет этот же знак для обозначения бинарной операции (вычитание). Конкретная операция определяется тем, в какой позиции находится знак. Обратная польская запись не позволяет этого: запись 5 3 − 8 + * (условный аналог первого выражения) будет интерпретирована как ошибочная, поскольку невозможно определить, что «минус» после 5 и 3 обозначает не вычитание; в результате будет сделана попытка вычислить сначала 5 − 3, затем 2 + 8, после чего выяснится, что для операции умножения не хватает операндов. Чтобы всё же записать это выражение, придётся либо переформулировать его (например, записав вместо выражения − 3 выражение 0 − 3), либо ввести для операции изменения знака отдельное обозначение, например, «±»: 5 3 ± 8 + *.
  • Так же, как и в инфиксной нотации, в ОПН одно и то же вычисление может быть записано в нескольких разных вариантах. Например, выражение (10 − 15) * 3 в ОПН можно записать как 10 15 − 3 *, а можно — как 3 10 15 − *
  • Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора (уменьшается количество нажимаемых клавиш), а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.

Вычисления на стеке

Общий порядок

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

  1. Обработка входного символа
    • Если на вход подан операнд, он помещается на вершину стека.
    • Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
  2. Если входной набор символов обработан не полностью, перейти к шагу 1.
  3. После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.

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

Пример вычисления выражений

Инфиксное выражение (1+2)×4+3{\displaystyle (1+2)\times 4+3} в ОПН может быть записано так: 1 2 + 4 × 3 +

Вычисление производится слева направо, ввод интерпретируется как указано в приведённой ниже таблице (указано состояние стека после выполнения операции, вершина стека выделена красным цветом):

Ввод Операция Стек
1 поместить в стек 1
2 поместить в стек 1, 2
+ сложение 3
4 поместить в стек 3, 4
* умножение 12
3 поместить в стек 12, 3
+ сложение 15

Результат, 15, в конце вычислений находится на вершине стека.

Клавиша «Ввод» (обозначаемая на калькуляторах как «Enter» или символом «↑») выполняет роль разделителя операндов, когда два операнда непосредственно следуют друг за другом. Если за операндом следует знак операции, то её нажатие не требуется, это сокращает количество действий, которые нужно выполнить для получения результата.

Преобразование из инфиксной нотации

Эдсгер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПЗ. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, 3 + 4 или 3 + 4 * (2 − 1)). Как и алгоритм вычисления ОПЗ, алгоритм сортировочной станции основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операции. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

Простой пример

Вход: 3 + 4

Добавим 3 к выходной строке (если прочитано число, то оно сразу добавляется к выходной строке).

Помещаем + (или его Идентификатор) в стек операций.

Добавим 4 к выходной строке.

Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операции в выходную строку. В нашем примере в стеке содержится только +.

Выходная строка: 3 4 +

В данном примере проявляются некоторые правила: все числа переносятся в выходную строку сразу после прочтения; когда выражение прочитано полностью, все оставшиеся в стеке операции выталкиваются в выходную строку.

Алгоритм

  • Пока есть ещё символы для чтения:
  • Читаем очередной символ.
  • Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.
  • Если символ является префиксной функцией (например, sin — синус), помещаем его в стек.
  • Если символ является открывающей скобкой, помещаем его в стек.
  • Если символ является закрывающей скобкой:
До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.

  • Если существуют разные виды скобок, появление непарной скобки также свидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — целая часть), добавляем к выходной строке символ этой функции.
  • Если символ является бинарной операцией о1, тогда:
1) пока на вершине стека префиксная функция…

… ИЛИ операция на вершине стека приоритетнее o1
… ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1
… выталкиваем верхний элемент стека в выходную строку;
2) помещаем операцию o1 в стек.
  • Когда входная строка закончилась, выталкиваем все символы из стека в выходную строку. В стеке должны были остаться только символы операций; если это не так, значит в выражении не согласованы скобки.
Ограничения и модификации

Алгоритм предполагает, что исходная строка корректна (проверяются не все ошибки), и все префиксные/постфиксные функции унарные.

Модификацию для многоместных функций с фиксированным количеством аргументов см. в основной статье.

Для операций вроде −x, являющихся как бинарными, так и унарными, нужна модификация: при обнаружении подобной операции система смотрит на предыдущий символ и определяет, чем будет минус, бинарной операцией или унарной функцией. Соответственно, в стеке и ОПЗ нужны разные символы для бинарного и унарного минуса.

Сложный пример

Приоритеты:

  • высокий: ^
  • средний: * /
  • низкий: + −
  • самый низкий: ( )
Вход: 3 + 4 * 2 / (1 − 5)^2

Читаем «3»
 Добавим «3» к выходной строке
  Выход: 3

Читаем «+»
 Кладём «+» в стек
  Выход: 3
  Стек: +

Читаем «4»
 Добавим «4» к выходной строке
  Выход: 3 4
  Стек: +

Читаем «*»
 Кладём «*» в стек
  Выход: 3 4
  Стек: + *

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2
  Стек: + *

Читаем «/»
 Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
  Выход: 3 4 2 *
  Стек: + /

Читаем «(»
 Кладём «(» в стек
  Выход: 3 4 2 *
  Стек: + / (

Читаем «1»
 Добавим «1» к выходной строке
  Выход: 3 4 2 * 1
  Стек: + / (

Читаем «−»
 Кладём «−» в стек
  Выход: 3 4 2 * 1
  Стек: + / ( −

Читаем «5»
 Добавим «5» к выходной строке
  Выход: 3 4 2 * 1 5
  Стек: + / ( -

Читаем «)»
 Выталкиваем «−» из стека в выходную строку, выталкиваем «(»
  Выход: 3 4 2 * 1 5 −
  Стек: + /

Читаем «^»
 Кладём «^» в стек
  Выход: 3 4 2 * 1 5 −
  Стек: + / ^

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2 * 1 5 − 2
  Стек: + / ^

Конец выражения
 Выталкиваем все элементы из стека в строку
  Выход: 3 4 2 * 1 5 − 2 ^ / +

Оптимизация выражений

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

Пример алгоритма упрощения выражения

Рассмотрим алгоритм, который осуществляет предвычисление констант в выражении. Дано выражение в ОПН. Нам понадобится стек для хранения смешанных данных (чисел и операторов).

Алгоритм подобен тому, который применяется для вычисления выражений. Мы просматриваем выражение слева направо.

Пока есть символы для чтения:

  • Читаем очередной символ.
  • Если символ является числом, помещаем его в стек.
  • Если символ является переменной, считая что переменная имеет значение null, помещаем символ в стек.
  • Если символ является оператором:
  • 1) (если все аргументы оператора, лежащие в стеке, имеют значение, отличное от null) выталкиваем аргументы оператора из стека и помещаем в стек результат операции;
  • 2) (если хотя бы один из аргументов имеет значение null) считая что результат операции null, кладём символ оператора в стек.

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

Пример работы алгоритма

Выражение
Инфиксая нотация: exp(-1/2*x)
Обратная Польская нотация: -1 2 / x * exp

Читаем: «-1»
 Кладём «-1» в стек
  Стек: -1

Читаем: «2»
 Кладём «2» в стек
  Стек: -1 2

Читаем: «/»
 Вычисляем частное, результат кладём в стек
  Стек: -0.5

Читаем: «x»
 Кладём «x» в стек со значением null
  Стек: -0.5 x(null)

Читаем: «*»
 Кладём «*» в стек со значением null
  Стек: -0.5 x(null) *(null)

Читаем «exp»
 Кладём «exp» в стек со значением null
  Стек: -0.5 x(null) *(null) exp(null)

Результат оптимизации: -0.5 x * exp

Данный метод, очевидно, не включает всех возможных способов оптимизации.

Примеры реализации

В статье «Обратная польская запись: примеры реализации» собраны примеры реализации обратной польской записи на различных языках программирования.

Практические реализации

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

Литература

  • Т. Пратт, М. Зелковиц. Языки программирования: разработка и реализация = Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation. — 4-е издание. — Питер, 2002. — 688 с. — (Классика Computer Science). — 4000 экз. — ISBN 5-318-00189-0.

Примечания

  1. ↑ А. В. Ахо, Р. Сети, Д. Д. Ульман. Компиляторы: принципы, технологии и инструменты. М.: «Вильямс», 2003. С. 51.

Ссылки

Языки программирования, использующие ОПН в качестве основной:

Другие ссылки:

Обратная польская нотация — это… Что такое Обратная польская нотация?

Обра́тная по́льская нота́ция (ОПН) (Обратная польская запись, Обратная бесскобочная запись (ОБЗ), Постфиксная нотация, Бесскобочная символика Лукашевича, Польская инверсная запись, Полиз) — форма записи математических выражений, в которой операнды расположены перед знаками операций.

Стековой машиной называется алгоритм, проводящий вычисления по обратной польской записи (см. ниже пример вычисления выражений).

История

Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем. Работа Хэмблина была представлена на конференции в июне 1957, и издана в 1957 и 1962.

Первыми компьютерами, поддерживающими обратную польскую нотацию были KDF9 от English Electric Company, который был анонсирован в 1960 и выпущен (появился в продаже) в 1963, и американский Burroughs B5000, анонсирован в 1961, выпущен в том же 1963. Один из проектировщиков B5000, Р. С. Бартон, позже написал, что разработал обратную польскую запись назависимо от Хэмблина, примерно в 1958, в процессе чтения книги по символьной логике, и до того как познакомился с работой Хэмблина.

Компания Friden перенесла ОПН в настольные калькуляторы, выпустив в июне 1964 модель EC-130. А в 1968 инженеры 1972 калькулятор HP-35 с поддержкой ОПН стал первый научным карманным калькулятором.

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

ОПН применялась в советском инженерном калькуляторе Б3-19М (совместная разработка с ГДР), выпущенном в 1976 году. Все выпускаемые в СССР вплоть до конца 1980-х годов программируемые микрокалькуляторы, за исключением «Электроника МК-85», использовали ОПН — она проще реализовывалась и позволяла обойтись в программировании вычислений меньшим числом команд, по сравнению с обычной алгебраической нотацией, а количество программной памяти в этих моделях всегда было критическим ресурсом (не более 105 ячеек, при том, что команда занимала 1-2 ячейки). ОПН используется в современных российских программируемых калькуляторах «Электроника МК-152» и «ЭЛЕКТРОНИКА_МК-161», что обеспечивает их совместимость с программами, написанными для советских калькуляторов.

Определение

Чтобы дать индуктивное определение постфиксной нотации[1], обозначим выражения в инфиксной нотации E, E1, E2, эквивалентные им выражения в постфиксной нотации E‘ , E1, E2 соответственно; o — произвольный бинарный оператор, тогда:

1. Если E — переменная или константа, то E‘ есть E.

2. Если E — выражение вида E1oE2, то E‘ есть E1E2o.

3. Если E — выражение вида (E1), то E‘ есть E1.

Описание

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

  • Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.
  • Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу.
  • Результатом вычисления выражения становится результат последней вычисленной операции.

Например, рассмотрим вычисление выражения 7 2 3 * - (эквивалентное выражение в инфиксной нотации: 7-2*3).

  1. Первый по порядку знак операции — «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду 7 6 - (результат умножения — 6, — заменяет тройку «2 3 *»).
  2. Второй знак операции — «-». Выполняется операция вычитания над операндами 7 и 6.
  3. Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.

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

Особенности обратной польской записи следующие:

  • Порядок выполнения операций однозначно задаётся порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.
  • В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, в инфиксной записи выражение 5 * (-3 + 8) использует знак «минус» как символ унарной операции (изменение знака числа), а выражение (10 - 15) * 3 применяет этот же знак для обозначения бинарной операции (вычитание). Конкретная операция определяется тем, в какой позиции находится знак. Обратная польская запись не позволяет этого: запись 5 3 - 8 + * (условный аналог первого выражения) будет интерпретирована как ошибочная, поскольку невозможно определить, что «минус» после 5 и 3 обозначает не вычитание; в результате будет сделана попытка вычислить сначала 5 - 3, затем 2 + 8, после чего выяснится, что для операции умножения не хватает операндов. Чтобы всё же записать это выражение, придётся либо переформулировать его, либо ввести для операции изменения знака отдельное обозначение, например, «±»: 5 3 ± 8 + *.
  • Так же, как и в инфиксной нотации, в ОПН одно и то же вычисление может быть записано в нескольких разных вариантах. Например, выражение (10 - 15) * 3 в ОПН можно записать как 10 15 - 3 *, а можно — как 3 10 15 - *
  • Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора (уменьшается количество нажимаемых клавиш), а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.

Вычисления на стеке

Общий порядок

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

  1. Обработка входного символа
    • Если на вход подан операнд, он помещается на вершину стека.
    • Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
  2. Если входной набор символов обработан не полностью, перейти к шагу 1.
  3. После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.

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

Пример вычисления выражений

Выражение ((1 + 2) * 4) + 3 в ОПН может быть записано так:

1 2 + 4 * 3 +

Вычисление производится следующим образом (указано состояние стека после выполнения операции):

Ввод Операция Стек
1 поместить в стек 1
2 поместить в стек 1, 2
+ сложение 3
4 поместить в стек 3, 4
* умножение 12
3 поместить в стек 12, 3
+ сложение 15

Результат, 15, в конце вычислений находится на вершине стека.

Другой способ представить работу стека в процессе вычисления представлен ниже (на примере калькулятора HP48S). (Вершина стека выделена цветом).

+----+
|  1 |  1 [Ввод]
+----+
+----+
|  1 |
|  2 |  2
+----+
+----+
|  3 |  + 
+----+
+----+
|  3 |
|  4 |  4
+----+
+----+
| 12 |  * 
+----+
+----+
| 12 |
|  3 |  3
+----+
+----+
| 15 |  + 
+----+

Клавиша «Ввод» (обозначаемая на калькуляторах как «Enter» или символом «↑») выполняет роль разделителя операндов, когда два операнда непосредственно следуют друг за другом. Если за операндом следует знак операции, то её нажатие не требуется, это сокращает количество действий, которые нужно выполнить для получения результата.

Преобразование из инфиксной нотации

Эдскер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПН. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, 3 + 4 или 3 + 4 * (2 - 1)). Как и алгоритм вычисления ОПН, алгоритм сортировочной станции основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операторы. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

Простой пример

Вход: 3 + 4

Добавим 3 к выходной строке (если прочитано число, то оно сразу добавляется к выходной строке).

Помещаем + (или его Идентификатор) в стек операторов.

Добавим 4 к выходной строке.

Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операторы в выходную строку. В нашем примере в стеке содержится только +.

Выходная строка: 3 4 +

В данном примере проявляются некоторые правила: все числа переносятся в выходную строку сразу после прочтения; когда выражение прочитано полностью, все оставшиеся в стеке операторы выталкиваются в выходную строку.

Алгоритм

  • Пока есть ещё символы для чтения:
  • Читаем очередной символ.
  • Если символ является числом, добавить его к выходной строке.
  • Если символ является символом функции, помещаем его в стек.
  • Если символ является разделителем аргументов функции (то есть, запятая):
До тех пор, пока верхним элементом стека не станет открывающаяся скобка, выталкиваем элементы из стека в выходную строку. Если открывающаяся скобка не встретилась, это означает, что в выражении либо неверно поставлен разделитель, либо несогласованы скобки.
  • Если символ является оператором, о1, тогда:
1) пока…

… (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
… (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…
… выталкиваем верхние элементы стека c бо́льшим либо равным приоритетом в выходную строку;
2) помещаем оператор o1 в стек.

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

Сложный пример

Приоритеты: 
 • ^    высокий 
 • * /  средний 
 • + -  низкий 
 (Ссылка)

Вход: 3 + 4 * 2 / (1 - 5)^2

Читаем «3»
 Добавим «3» к выходной строке
  Выход: 3

Читаем «+»
 Кладём «+» в стек
  Выход: 3
  Стек: +

Читаем «4»
 Добавим «4» к выходной строке
  Выход: 3 4
  Стек: +

Читаем «*»
 Кладём «*» в стек
  Выход: 3 4
  Стек: + *

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2
  Стек: + *

Читаем «/»
 Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
  Выход: 3 4 2 *
  Стек: + /

Читаем «(»
 Кладём «(» в стек
  Выход: 3 4 2 *
  Стек: + / (

Читаем «1»
 Добавим «1» к выходной строке
  Выход: 3 4 2 * 1
  Стек: + / (

Читаем «-»
 Кладём «-» в стек
  Выход: 3 4 2 * 1
  Стек: + / ( -

Читаем «5»
 Добавим «5» к выходной строке
  Выход: 3 4 2 * 1 5
  Стек: + / ( -

Читаем «)»
 Выталкиваем «-» из стека в выходную строку, выталкиваем «(»
  Выход: 3 4 2 * 1 5 -
  Стек: + /

Читаем «^»
 Кладём «^» в стек
  Выход: 3 4 2 * 1 5 -
  Стек: + / ^

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2 * 1 5 - 2
  Стек: + / ^

Конец выражения
 Выталкиваем все элементы из стека в строку
  Выход: 3 4 2 * 1 5 - 2 ^ / +

Оптимизация выражений

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

Пример алгоритма упрощения выражения

Рассмотрим алгоритм, который осуществляет предвычисление констант в выражении. Дано выражение в ОПН. Нам понадобится стек для хранения смешанных данных (чисел и операторов).

Алгоритм подобен тому, который применяется для вычисления выражений. Мы просматриваем выражение слева направо.

Пока есть символы для чтения:

  • Читаем очередной символ.
  • Если символ является числом, помещаем его в стек.
  • Если символ является переменной, считая что переменная имеет значение null, помещаем символ в стек.
  • Если символ является оператором:
  • 1) (если все аргументы оператора, лежащие в стеке, имеют значение, отличное от null) выталкиваем аргументы оператора из стека и помещаем в стек результат операции;
  • 2) (если хотя бы один из аргументов имеет значение null) считая что результат операции null, кладём символ оператора в стек.

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

Пример работы алгоритма

Выражение
Инфиксая нотация: exp(-1/2*x)
Обратная Польская нотация: -1 2 / x * exp

Читаем: «-1»
 Кладём «-1» в стек
  Стек: -1

Читаем: «2»
 Кладём «2» в стек
  Стек: -1 2

Читаем: «/»
 Вычисляем частное, результат кладём в стек
  Стек: -0.5

Читаем: «x»
 Кладём «x» в стек со значением null
  Стек: -0.5 x(null)

Читаем: «*»
 Кладём «*» в стек со значением null
  Стек: -0.5 x(null) *(null)

Читаем «exp»
 Кладём «exp» в стек со значением null
  Стек: -0.5 x(null) *(null) exp(null)

Результат оптимизации: -0.5 x * exp

Данный метод, очевидно, не включает всех возможных способов оптимизации.

Примеры реализации

calc :: String -> [Float]
calc = foldl f [] . words
where
f (x:y:zs) «+» = (y + x):zs
f (x:y:zs) «-» = (y — x):zs
f (x:y:zs) «*» = (y * x):zs
f (x:y:zs) «/» = (y / x):zs
f xs y = read y : xs

program calc;
 
{$apptype console}
 
type
real=double;
 
const
prs='+-*/(';
pri:array [1..5] of byte = (1,1,2,2,0);
 
var
s1,s2:string;
q:array[0..500] of real;
w:array[0..500] of char;
n,len,len2,i,j:longint;
t:real;
ch:char;
 
procedure push(x:real);
begin
  inc(len);
  q[len]:=x;
end;
 
function pop:real;
begin
  pop:=q[len];
  q[len]:=0;
  dec(len);
end;
 
procedure pushc(x:char);
begin
  inc(len2);
  w[len2]:=x;
end;
 
function popc:char;
begin
  popc:=w[len2];
  w[len2]:=#0;
  dec(len2);
end;
 
function oper(s1,s2:real;s3:char):real;
var
s:string;
x,y,z:real;
tmp:integer;
begin
  x:=s1;
  y:=s2;
  case s3 of
    '+':z:=x+y;
    '-':z:=x-y;
    '*':z:=x*y;
    '/':z:=x/y;
  end;
  oper:=z;
end;
 
procedure prechange(var s:string);
var
i:longint;
begin
  if s[1]='-' then s:='0'+s;
  i:=1;
  while i<=n do if (s[i]='(')and(s[i+1]='-') then insert('0',s,i+1) else inc(i);
end;
 
function change(s:string):string;
var
i:longint;
rezs:string;
c:boolean;
begin
  c:=false;
  for i:=1 to n do begin
    if not(s[i] in ['+','-','*','/','(',')']) then begin
      if c then rezs:=rezs+' ';
      rezs:=rezs+s[i];
      c:=false;
    end
    else begin
      c:=true;
      if s[i]='(' then pushc(s[i]) else
      if s[i]=')' then begin
        while w[len2]<>'(' do begin
          rezs:=rezs+' '+popc;
        end;
        popc;
      end else
      if s[i] in ['+','-','*','/'] then begin
        while pri[pos(w[len2],prs)]>=pri[pos(s[i],prs)] do rezs:=rezs+' '+popc;
        pushc(s[i]);
      end;
    end;
  end;
  while len2<>0 do rezs:=rezs+' '+popc;
  change:=rezs;
end;
 
function count(s:string):real;
var
ss:string;
x,s1,s2:real;
chh,s3:char;
p,i,j:longint;
tmp:integer;
begin
  i:=0;
  repeat
    j:=i+1;
    repeat inc(i) until s[i]=' ';
    ss:=copy(s,j,i-j);
    chh:=ss[1];
    if not(chh in ['+','-','*','/']) then begin
      val(ss,p,tmp);
      push(p);
    end
    else begin
      s2:=pop;
      s1:=pop;
      s3:=chh;
      push(oper(s1,s2,s3));
    end;
  until i>=n;
  x:=pop;
  count:=x;
end;
 
procedure writeL(x:real);
var
y,a,b:longint;
q:real;
begin
  y:=trunc(x);
  b:=0;
  if abs(x-y)<(1e-12) then
  writeln(y)
  else begin
    if y>0 then a:=round(ln(y)/ln(10))+1 else a:=1;
    q:=x;
    repeat
      q:=q*10;
      inc(b);
    until abs(q-trunc(q))<(1e-12);
    writeln(x:a+b:b);
  end;
end;
 
begin
 
 
repeat
    writeln('Enter expression');
    readln(s1);
    n:=length(s1);
    prechange(s1);
    n:=length(s1);
    s2:=change(s1);
    if s2[1]=' ' then delete(s2,1,1);
    s2:=s2+' ';
    n:=length(s2);
    t:=count(s2);
    writeL(t);
    writeln('One more expression?(Y/N)');
    readln(ch);
until upcase(ch)='N';
 
end.

Стековый калькулятор и обратная польская запись формулы





⇐ ПредыдущаяСтр 5 из 11Следующая ⇒

В 1920 г. польский математик Ян Лукашевич предложил способ записи арифметических формул, не использующий скобок. В привычной нам записи знак операции записывается между аргументами, например, сумма чисел 2 и 3 записывается как 2 + 3. Ян Лукашевич предложил две другие формы записи: префиксная форма, в которой знак операции записывается перед аргументами, и постфиксная форма, в которой знак операции записывается после аргументов. В префиксной форме сумма чисел 2 и 3 записывается как + 2 3, в постфиксной — как 2 3 +. В честь Яна Лукашевича эти формы записи называют прямой и обратной польской записью.

В польской записи скобки не нужны. Например, выражение

(2+3)*(15-7)

записывается в прямой польской записи как

* + 2 3 — 15 7,

в обратной польской записи — как

2 3 + 15 7 — *.

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

Обратная польская запись формулы позволяет вычислять выражение любой сложности, используя стек как запоминающее устройство для хранения промежуточных результатов. Такой стековый калькулятор был впервые выпущен фирмой Hewlett Packard. Обычные модели калькуляторов не позволяют вычислять сложные формулы без использования бумаги и ручки для записи промежуточных результатов. В некоторых моделях есть скобки с одним или двумя уровнями вложенности, но более сложные выражения вычислять невозможно. Также в обычных калькуляторах трудно понять, как результат и аргументы перемещаются в процессе ввода и вычисления между регистрами калькулятора. Калькулятор обычно имеет регистры X, Y и регистр памяти, промежуточные результаты каким-то образом перемещаются по регистрам, каким именно — запомнить невозможно.

В отличие от других калькуляторов, устройство стекового калькулятора вполне понятно и легко запоминается. Калькулятор имеет память в виде стека. При вводе числа оно просто добавляется в стек. При нажатии на клавишу операции, например, на клавишу +, аргументы операции сначала извлекаются из стека, затем с ними выполняется операция, наконец, результат операции помещается обратно в стек. Таким образом, при выполнении операции с двумя аргументами, например, сложения, в стеке должно быть не менее двух чисел. Аргументы удаляются из стека и на их место кладется результат, то есть при выполнении сложения глубина стека уменьшается на единицу. Вершина стека всегда содержит результат последней операции и высвечивается на дисплее калькулятора.



Для вычисления выражения надо сначала преобразовать его в обратную польскую запись (при некотором навыке это легко сделать в уме). В приведенном выше примере выражение (2+3)*(15-7) преобразуется к

2 3 + 15 7 — *

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

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

2 3 + 15 7 — *

Стек вначале пуст. Последовательно добавляем числа 2 и 3 в стек.

| | вводим число 2 | 2 | вводим число 3 | 3 |

Далее читаем символ + и нажимаем на клавишу + калькулятора. Числа 2 и 3 извлекаются из стека, складываются, и результат помещается обратно в стек.

выполняем сложение | 5 |

Далее, в стек добавляются числа 15 и 7.

| 5 | вводим число 15 | 15 | вводим число 7 | 7 |

Читаем символ — и нажимаем на клавишу — калькулятора. Со стека при этом снимаются два верхних числа 7 и 15 и выполняется операция вычитания. Причем уменьшаемым является то число, которое было введено раньше, а вычитаемым — число, введенное позже. Иначе говоря, при выполнении некоммутативных операций, таких как вычитание или деление, правым аргументом является число на вершине стека, левым — число, находящееся под вершиной стека.

выполняем вычитание | 8 |

Наконец, читаем символ * и нажимаем на клавишу * калькулятора. Калькулятор выполняет умножение, со стека снимаются два числа, перемножаются, результат помещается обратно в стек.




| 8 | выполняем умножение | 40 ||

Число 40 является результатом вычисления выражения. Оно находится на вершине стека и высвечивается на дисплее стекового калькулятора.

Польская запись присутствует и в обычных вычислениях: запись функций — прямая польская запись sin(x), а вычисление факториала n!- обратная.

Очередь

Очередь как структура данных понятна даже людям, не знакомым с программированием. Очередь содержит элементы, как бы выстроенные друг за другом в цепочку. У очереди есть начало и конец. Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала, т.е. действует принцип: Первый вошел- первый вышел FIFO. В отличие от обычной очереди, которую всегда можно при желании покинуть, из середины программистской очереди удалять элементы нельзя.

Очередь можно представить в виде трубки. В один конец трубки можно добавлять шарики — элементы очереди, из другого конца они извлекаются. Элементы в середине очереди, т.е. шарики внутри трубки, недоступны. Конец трубки, в который добавляются шарики, соответствует концу очереди, конец, из которого они извлекаются — началу очереди. Таким образом, концы трубки не симметричны, шарики внутри трубки движутся только в одном направлении.

В принципе, можно было бы разрешить добавлять элементы в оба конца очереди и забирать их также из обоих концов. Такая структура данных в программировании тоже существует, ее название — «дек», от англ. Double Ended Queue, т.е. очередь с двумя концами. Дек применяется значительно реже, чем очередь.

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

Любая, даже самая простая, операционная система всегда в той или иной степени многозадачная. Это значит, что в момент нажатия клавиши операционная система может быть занята какой-либо другой работой. Тем не менее, операционная система ни в какой ситуации не имеет права проигнорировать нажатие на клавишу. Поэтому происходит прерывание работы компьютера, он запоминает свое состояние и переключается на обработку нажатия, на клавишу. Такая обработка должна быть очень короткой, чтобы не нарушить выполнение других задач. Команда, отдаваемая нажатием на клавишу, просто добавляется в конец очереди запросов, ждущих своего выполнения. После этого прерывание заканчивается, компьютер восстанавливает свое состояние и продолжает работу, которая была прервана нажатием на клавишу. Запрос, поставленный в очередь, будет выполнен не сразу, а только когда наступит его черед.

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

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











Обратная польская запись — Википедия

Обра́тная по́льская запись (англ. Reverse Polish notation, RPN) — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись, обратная бесскобочная запись, постфиксная нотация, бесскобочная символика Лукасевича, польская инверсная запись, ПОЛИЗ.

Стековой машиной называется алгоритм, проводящий вычисления по обратной польской записи (см. ниже пример вычисления выражений).

История

Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем. Работа Хэмблина была представлена на конференции в июне 1957, и издана в 1957 и 1962.

Первыми компьютерами, поддерживающими обратную польскую нотацию, были KDF9 от English Electric Company, который был анонсирован в 1960 и выпущен (появился в продаже) в 1963, и американский Burroughs B5000, анонсирован в 1961, выпущен в том же 1963. Один из проектировщиков B5000, Р. С. Бартон, позже написал, что разработал обратную польскую запись независимо от Хэмблина, примерно в 1958, в процессе чтения книги по символьной логике, и до того как познакомился с работой Хэмблина.

Компания Friden перенесла ОПН в настольные калькуляторы, выпустив в июне 1964 модель EC-130. А в 1968 инженеры Hewlett-Packard разработали настольный калькулятор 9100A с поддержкой ОПН. Этот калькулятор сделал обратную польскую нотацию популярной среди учёных и инженеров, даже несмотря на то, что в ранней рекламе 9100A ОПН не упоминалась. В 1972 калькулятор HP-35 с поддержкой ОПН стал первым научным карманным калькулятором.

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

ОПН применялась в советском инженерном калькуляторе Б3-19М (совместная разработка с ГДР), выпущенном в 1976 году. Все выпускаемые в СССР вплоть до конца 1980-х годов программируемые микрокалькуляторы, за исключением «Электроника МК-85» и «Электроника МК-90», использовали ОПН — она проще реализовывалась и позволяла обойтись в программировании вычислений меньшим числом команд, по сравнению с обычной алгебраической нотацией, а количество программной памяти в этих моделях всегда было критическим ресурсом. ОПН используется в современных российских программируемых калькуляторах «Электроника МК-152» и «ЭЛЕКТРОНИКА МК-161», что обеспечивает их совместимость с программами, написанными для советских калькуляторов.

Определение

Чтобы дать индуктивное определение постфиксной нотации[1], обозначим выражения в инфиксной нотации E{\displaystyle E}, E1{\displaystyle E_{1}}, E2{\displaystyle E_{2}}, эквивалентные им выражения в постфиксной нотации E˙{\displaystyle {\dot {E}}} , E˙1{\displaystyle {\dot {E}}_{1}}, E˙2{\displaystyle {\dot {E}}_{2}} соответственно; o{\displaystyle o} — произвольный бинарный оператор, тогда:

1. Если E{\displaystyle E} — переменная или константа, то E˙{\displaystyle {\dot {E}}} есть E{\displaystyle E}.

2. Если E{\displaystyle E} — выражение вида E1oE2{\displaystyle E_{1}oE_{2}}, то E˙{\displaystyle {\dot {E}}} есть E˙1E˙2o{\displaystyle {\dot {E}}_{1}{\dot {E}}_{2}o}.

3. Если E{\displaystyle E} — выражение вида (E1){\displaystyle (E_{1})}, то E˙{\displaystyle {\dot {E}}} есть E˙1{\displaystyle {\dot {E}}_{1}}.

Описание

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

  • Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.
  • Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу.
  • Результатом вычисления выражения становится результат последней вычисленной операции.

Например, рассмотрим вычисление выражения 7 2 3 * − (эквивалентное выражение в инфиксной нотации: 7 − 2 * 3).

  1. Первый по порядку знак операции — «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду 7 6 − (результат умножения — 6, — заменяет тройку «2 3 *»).
  2. Второй знак операции — «−». Выполняется операция вычитания над операндами 7 и 6.
  3. Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.

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

Особенности обратной польской записи следующие:

  • Порядок выполнения операций однозначно задаётся порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.
  • В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, в инфиксной записи выражение 5 * (−3 + 8) использует знак «минус» как символ унарной операции (изменение знака числа), а выражение (10 − 15) * 3 применяет этот же знак для обозначения бинарной операции (вычитание). Конкретная операция определяется тем, в какой позиции находится знак. Обратная польская запись не позволяет этого: запись 5 3 − 8 + * (условный аналог первого выражения) будет интерпретирована как ошибочная, поскольку невозможно определить, что «минус» после 5 и 3 обозначает не вычитание; в результате будет сделана попытка вычислить сначала 5 − 3, затем 2 + 8, после чего выяснится, что для операции умножения не хватает операндов. Чтобы всё же записать это выражение, придётся либо переформулировать его (например, записав вместо выражения − 3 выражение 0 − 3), либо ввести для операции изменения знака отдельное обозначение, например, «±»: 5 3 ± 8 + *.
  • Так же, как и в инфиксной нотации, в ОПН одно и то же вычисление может быть записано в нескольких разных вариантах. Например, выражение (10 − 15) * 3 в ОПН можно записать как 10 15 − 3 *, а можно — как 3 10 15 − *
  • Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора (уменьшается количество нажимаемых клавиш), а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.

Вычисления на стеке

Общий порядок

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

  1. Обработка входного символа
    • Если на вход подан операнд, он помещается на вершину стека.
    • Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
  2. Если входной набор символов обработан не полностью, перейти к шагу 1.
  3. После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.

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

Пример вычисления выражений

Инфиксное выражение (1+2)×4+3{\displaystyle (1+2)\times 4+3} в ОПН может быть записано так: 1 2 + 4 × 3 +

Вычисление производится слева направо, ввод интерпретируется как указано в приведённой ниже таблице (указано состояние стека после выполнения операции, вершина стека выделена красным цветом):

Ввод Операция Стек
1 поместить в стек 1
2 поместить в стек 1, 2
+ сложение 3
4 поместить в стек 3, 4
* умножение 12
3 поместить в стек 12, 3
+ сложение 15

Результат, 15, в конце вычислений находится на вершине стека.

Клавиша «Ввод» (обозначаемая на калькуляторах как «Enter» или символом «↑») выполняет роль разделителя операндов, когда два операнда непосредственно следуют друг за другом. Если за операндом следует знак операции, то её нажатие не требуется, это сокращает количество действий, которые нужно выполнить для получения результата.

Преобразование из инфиксной нотации

Эдсгер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПЗ. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, 3 + 4 или 3 + 4 * (2 − 1)). Как и алгоритм вычисления ОПЗ, алгоритм сортировочной станции основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операции. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

Простой пример

Вход: 3 + 4

Добавим 3 к выходной строке (если прочитано число, то оно сразу добавляется к выходной строке).

Помещаем + (или его Идентификатор) в стек операций.

Добавим 4 к выходной строке.

Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операции в выходную строку. В нашем примере в стеке содержится только +.

Выходная строка: 3 4 +

В данном примере проявляются некоторые правила: все числа переносятся в выходную строку сразу после прочтения; когда выражение прочитано полностью, все оставшиеся в стеке операции выталкиваются в выходную строку.

Алгоритм

  • Пока есть ещё символы для чтения:
  • Читаем очередной символ.
  • Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.
  • Если символ является префиксной функцией (например, sin — синус), помещаем его в стек.
  • Если символ является открывающей скобкой, помещаем его в стек.
  • Если символ является закрывающей скобкой:
До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.

  • Если существуют разные виды скобок, появление непарной скобки также свидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — целая часть), добавляем к выходной строке символ этой функции.
  • Если символ является бинарной операцией о1, тогда:
1) пока на вершине стека префиксная функция…

… ИЛИ операция на вершине стека приоритетнее o1
… ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1
… выталкиваем верхний элемент стека в выходную строку;
2) помещаем операцию o1 в стек.
  • Когда входная строка закончилась, выталкиваем все символы из стека в выходную строку. В стеке должны были остаться только символы операций; если это не так, значит в выражении не согласованы скобки.
Ограничения и модификации

Алгоритм предполагает, что исходная строка корректна (проверяются не все ошибки), и все префиксные/постфиксные функции унарные.

Модификацию для многоместных функций с фиксированным количеством аргументов см. в основной статье.

Для операций вроде −x, являющихся как бинарными, так и унарными, нужна модификация: при обнаружении подобной операции система смотрит на предыдущий символ и определяет, чем будет минус, бинарной операцией или унарной функцией. Соответственно, в стеке и ОПЗ нужны разные символы для бинарного и унарного минуса.

Сложный пример

Приоритеты:

  • высокий: ^
  • средний: * /
  • низкий: + −
  • самый низкий: ( )
Вход: 3 + 4 * 2 / (1 − 5)^2

Читаем «3»
 Добавим «3» к выходной строке
  Выход: 3

Читаем «+»
 Кладём «+» в стек
  Выход: 3
  Стек: +

Читаем «4»
 Добавим «4» к выходной строке
  Выход: 3 4
  Стек: +

Читаем «*»
 Кладём «*» в стек
  Выход: 3 4
  Стек: + *

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2
  Стек: + *

Читаем «/»
 Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
  Выход: 3 4 2 *
  Стек: + /

Читаем «(»
 Кладём «(» в стек
  Выход: 3 4 2 *
  Стек: + / (

Читаем «1»
 Добавим «1» к выходной строке
  Выход: 3 4 2 * 1
  Стек: + / (

Читаем «−»
 Кладём «−» в стек
  Выход: 3 4 2 * 1
  Стек: + / ( −

Читаем «5»
 Добавим «5» к выходной строке
  Выход: 3 4 2 * 1 5
  Стек: + / ( -

Читаем «)»
 Выталкиваем «−» из стека в выходную строку, выталкиваем «(»
  Выход: 3 4 2 * 1 5 −
  Стек: + /

Читаем «^»
 Кладём «^» в стек
  Выход: 3 4 2 * 1 5 −
  Стек: + / ^

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2 * 1 5 − 2
  Стек: + / ^

Конец выражения
 Выталкиваем все элементы из стека в строку
  Выход: 3 4 2 * 1 5 − 2 ^ / +

Оптимизация выражений

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

Пример алгоритма упрощения выражения

Рассмотрим алгоритм, который осуществляет предвычисление констант в выражении. Дано выражение в ОПН. Нам понадобится стек для хранения смешанных данных (чисел и операторов).

Алгоритм подобен тому, который применяется для вычисления выражений. Мы просматриваем выражение слева направо.

Пока есть символы для чтения:

  • Читаем очередной символ.
  • Если символ является числом, помещаем его в стек.
  • Если символ является переменной, считая что переменная имеет значение null, помещаем символ в стек.
  • Если символ является оператором:
  • 1) (если все аргументы оператора, лежащие в стеке, имеют значение, отличное от null) выталкиваем аргументы оператора из стека и помещаем в стек результат операции;
  • 2) (если хотя бы один из аргументов имеет значение null) считая что результат операции null, кладём символ оператора в стек.

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

Пример работы алгоритма

Выражение
Инфиксая нотация: exp(-1/2*x)
Обратная Польская нотация: -1 2 / x * exp

Читаем: «-1»
 Кладём «-1» в стек
  Стек: -1

Читаем: «2»
 Кладём «2» в стек
  Стек: -1 2

Читаем: «/»
 Вычисляем частное, результат кладём в стек
  Стек: -0.5

Читаем: «x»
 Кладём «x» в стек со значением null
  Стек: -0.5 x(null)

Читаем: «*»
 Кладём «*» в стек со значением null
  Стек: -0.5 x(null) *(null)

Читаем «exp»
 Кладём «exp» в стек со значением null
  Стек: -0.5 x(null) *(null) exp(null)

Результат оптимизации: -0.5 x * exp

Данный метод, очевидно, не включает всех возможных способов оптимизации.

Примеры реализации

В статье «Обратная польская запись: примеры реализации» собраны примеры реализации обратной польской записи на различных языках программирования.

Практические реализации

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

Литература

  • Т. Пратт, М. Зелковиц. Языки программирования: разработка и реализация = Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation. — 4-е издание. — Питер, 2002. — 688 с. — (Классика Computer Science). — 4000 экз. — ISBN 5-318-00189-0.

Примечания

  1. ↑ А. В. Ахо, Р. Сети, Д. Д. Ульман. Компиляторы: принципы, технологии и инструменты. М.: «Вильямс», 2003. С. 51.

Ссылки

Языки программирования, использующие ОПН в качестве основной:

Другие ссылки:

Стеки коммутаторов

— Cisco Meraki

Коммутаторы Cisco Meraki

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

Определение порядка складывания

Стекинг для вашей сети

Коммутаторы

Meraki имеют несколько вариантов, которые наилучшим образом подходят для вашей сети.В этой статье обсуждаются функции стекирования MS, которые можно использовать для наилучшего соответствия вашему развертыванию, а именно: виртуальное стекирование, физическое стекирование и гибкое стекирование.

Общие сведения о виртуальном стеке

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

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

Общие сведения о физическом стеке

Physical Stacking помогает обеспечить простое управление и физическое резервирование. Используя два физических порта стекирования на задней панели каждого коммутатора, стек может обеспечить резервирование шлюза на уровне 3 и резервирование с двойным подключением на уровне 2. После установки всех кабелей стекирования требуется только один восходящий канал для обеспечения подключения к стеку.

Пошаговое руководство по настройке стека физических коммутаторов можно найти в разделе этой статьи «Настройка стека физических коммутаторов».

Понимание гибкого стекирования

Доступность и избыточность наиболее полезны на уровне распределения сети. На коммутаторах серий MS420 и MS425 любые два порта можно настроить как порты стека. Это позволяет настроить полное резервирование для вашего шлюза и минимизировать влияние сбоя в сети.

Для достижения гибкого стекирования выберите два порта на каждом коммутаторе и включите опцию стекирования:

Пошаговое руководство по настройке гибкого стека коммутаторов можно найти в разделе этой статьи «Настройка гибкого стека коммутаторов».

Доступность стека

Если не указано иное, штабелировать можно только аналогичные модели, независимо от плотности портов. Например, MS350-48 и MS350-24X могут быть объединены в стек, но MS250-48 не могут быть объединены в стек с MS350-48.

Модель Виртуальное накопление Физическое стекирование Гибкое штабелирование
MS120
MS210

Совместимость с MS225

MS220

MS225

Совместимость с MS210

MS250

MS320

MS350

MS355
MS390
MS410

MS420

MS425

MS450

Для коммутаторов, поддерживающих физическое / гибкое стекирование:

Скорость передачи данных кабеля стекирования Совместимая серия

40 гигабит

100 гигабит

120 гигабит

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

Настройка физического стека коммутаторов

До восьми коммутаторов Meraki MS можно сконфигурировать в физическом стеке для обеспечения высокоскоростной связи между устройствами.

Можно штабелировать только похожие модели. Например, MS350-48 и MS350-24X могут быть объединены в стек, но MS250-48 не могут быть объединены в стек с MS350-48. Серии MS210 и MS225 также совместимы с физическим стеком.

Физическое стекирование доступно на коммутаторах MS210, MS225, MS250, MS350, MS355, MS390 и MS410, которые включают выделенные порты стекирования.В этом разделе описывается физическое стекирование .

Гибкое стекирование доступно на коммутаторах MS420 и MS425, которые не имеют выделенных портов стекирования; любой порт на этих коммутаторах можно настроить как порт стека. Для гибкого стекирования см. Раздел «Настройка гибкого стека коммутатора» этой статьи.

Настройка физического стека коммутаторов Видео

Шаги настройки стека физических коммутаторов

Приведенные ниже шаги объясняют, как подготовить группу коммутаторов для физического стекирования, как собрать их вместе и как настроить стек в Dashboard.

  1. Добавьте переключатели в сеть Dashboard. Это может быть новая сеть Dashboard для этих коммутаторов или существующая сеть с другими коммутаторами. Не настраивайте стек в Dashboard.
  2. Подключите каждый коммутатор к отдельным каналам связи, чтобы вывести их обоих в сеть и убедиться, что они могут регистрироваться с помощью Meraki Dashboard.
  3. Загрузите последнюю сборку микропрограммы с помощью Менеджера обновления микропрограммы в разделе Организация> Монитор> Обновления микропрограммы , если они еще не настроены для этого.Это помогает гарантировать, что на каждом коммутаторе работает одна и та же сборка прошивки.
  4. При выключенном питании всех коммутаторов и отключенных каналах соедините коммутаторы вместе с помощью кабелей стекирования в кольцевой топологии (как показано на следующем рисунке). Чтобы создать полное кольцо, начните с подключения коммутатора 1 / порта стека 1 к коммутатору 2 / порта стека 2, затем переключите 2 / порт стека 1 на коммутатор 3 / порт стека 2 и так далее, при этом нижний коммутатор подключается к верхнему коммутатору. чтобы завершить кольцо.
  1. Подключите к одному каналу восходящей связи для всего стека коммутаторов.
  2. Включите все коммутаторы, затем подождите несколько минут, пока они загрузят последнюю версию микропрограммы и обновления с Dashboard. Коммутаторы могут перезагрузиться во время этого процесса.
    • Во время этого процесса светодиоды питания на передней панели каждого переключателя будут мигать.
    • После того, как коммутаторы загрузят и установят микропрограммное обеспечение, их индикаторы питания будут гореть белым или зеленым.
  3. Перейдите к Switch> Monitor> Switch stacks .
  4. Настройте стек коммутаторов в Dashboard. Если Dashboard уже обнаружил правильный стек в Обнаруженные потенциальные стеки , щелкните Подготовить этот стек , чтобы автоматически настроить стек.
    В противном случае, чтобы настроить стек вручную:
  • Перейдите к Switch> Monitor> Switch stacks .
  • Нажмите добавить один / Добавить стопку :
  • Установите флажки напротив коммутаторов, которые вы хотите объединить в стек, назовите стек и нажмите Create .:
  1. Настройка завершена, стек должен быть запущен и работает.

ПРИМЕЧАНИЕ. После того, как стек коммутаторов запущен и работает, можно добавить несколько восходящих каналов для резервирования.

Укладка MS390s

Выполните следующие действия, чтобы настроить стек MS390, или посмотрите это короткое видео.

  1. Добавьте переключатели в сеть Dashboard. Это может быть новая сеть Dashboard для этих коммутаторов или существующая сеть с другими коммутаторами. Не настраивайте стек в Dashboard.
  2. Подключите каждый коммутатор к отдельным каналам связи, чтобы вывести их обоих в сеть и убедиться, что они могут регистрироваться с помощью Meraki Dashboard.
  3. Загрузите ту же сборку микропрограмм (которая включает поддержку MS390) с помощью диспетчера обновления микропрограмм в разделе Организация> Монитор> Обновления микропрограмм , если они еще не настроены для этого. Это помогает гарантировать, что на каждом коммутаторе работает одна и та же сборка прошивки.Обратите внимание, что обновление коммутаторов может занять около часа.

  4. Перейдите к Switch> Monitor> Switch stacks

  5. Настройте стек коммутатора в Dashboard.

  • Установите флажки напротив коммутаторов, которые нужно объединить в стек, назовите стек и нажмите Create .
  1. Убедитесь, что все коммутаторы загрузили последнюю конфигурацию.Чтобы проверить это, перейдите к Switch> Switches и выберите переключатель MS390. Найдите «CONFIG» в столбце слева на странице сведений о коммутаторе и проверьте, отображается ли статус « Up to date ».
  2. Выключите коммутаторы и отключите все восходящие каналы.
  3. При выключенном питании всех коммутаторов и отключенных каналах соедините коммутаторы вместе с помощью кабелей стекирования в кольцевой топологии (как показано на следующем рисунке). Чтобы создать полное кольцо, начните с подключения коммутатора 1 / порта стека 1 к коммутатору 2 / порта стека 2, затем переключите 2 / порт стека 1 на коммутатор 3 / порт стека 2 и так далее, при этом нижний коммутатор подключается к верхнему коммутатору. чтобы завершить кольцо.При подключении кабелей стекирования убедитесь, что каждый разъем правильно совмещен с портом стекирования коммутатора, к которому он подключается, и затяните винты вручную (по часовой стрелке). Убедитесь, что логотип Cisco находится на верхней стороне разъема.
  1. Подключите к одному каналу восходящей связи для всего стека коммутаторов.
  2. Включите все переключатели.
  1. Каждый член стека будет отображать один и тот же IP-адрес управления на панели управления, поскольку на первичной панели работает только одна плоскость управления.

  2. Время загрузки может меняться в зависимости от количества элементов в стеке и используемых портов.

  3. Перезагрузка элемента стека (с панели мониторинга / физического цикла питания) перезагрузит все элементы в стеке. То же самое применяется при выполнении сброса к заводским настройкам для элемента стека.

Добавление нового элемента в стек
  1. Добавьте новый коммутатор в сеть Dashboard существующего стека MS390.
  2. Подключите новый коммутатор к восходящему каналу, чтобы вывести его в сеть, и убедитесь, что он регистрируется с помощью Meraki Dashboard.
  3. Обновите коммутатор до той же сборки микропрограммы, что и на стеке коммутатора, используя диспетчер обновления микропрограммы в разделе Организация> Монитор> Обновления микропрограмм ,

  4. Перед добавлением нового участника в существующий стек убедитесь, что общее количество виртуальных локальных сетей ограничено 1000. Например, если у вас есть существующий стек с каждым портом, установленным на собственный VLAN 1, 1–1000 и порты нового члена установлены на собственные VLAN 1; разрешенные VLAN: 1,2001-2500, тогда общее количество VLAN в стеке будет 1000 (1-1000) +500 (2001-2500) = 1500.Dashboard не позволит добавить нового члена в стек и покажет следующую ошибку:

  1. Перейдите к Switch> Switch stacks и выберите существующий стек, в который вы хотите добавить коммутатор.

  2. Убедитесь, что все коммутаторы в существующем стеке получили новую конфигурацию. Чтобы убедиться в этом, перейдите к «Коммутатор »> «Коммутаторы » и выберите в стеке коммутатор MS390.Найдите «КОНФИГУРАЦИЯ» в столбце слева на странице сведений о коммутаторе и проверьте, отображается ли статус «Актуально».

  3. На вкладке «Управление участниками» добавьте новый коммутатор в существующий стек.

  4. Выключите коммутатор и физически установите новый коммутатор в существующий стек в виде кольца.

  5. Включите нового участника.

Настройка гибкого стека коммутаторов

До восьми коммутаторов Meraki MS420 / 425 можно сконфигурировать в гибкий стек для обеспечения высокоскоростной связи между устройствами.

Гибкое стекирование доступно на коммутаторах MS420 и MS425, которые не имеют выделенных портов стекирования; любой интерфейс SFP + на этих коммутаторах можно настроить как порт стека. В этой статье описывается гибкая укладка .

Можно штабелировать только похожие модели. Например, MS350-48 и MS350-24X могут быть объединены в стек, но MS250-48 не могут быть объединены в стек с MS350-48.

Физическое стекирование доступно на коммутаторах MS225, MS250, MS350 и MS410, которые включают выделенные порты стекирования.Для физического стекирования и обратитесь к разделу «Настройка физического стека коммутатора» этой статьи.

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

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

Настройка гибкого стека коммутаторов Видео

Этапы настройки стека гибких коммутаторов

Следующие шаги объясняют, как подготовить группу коммутаторов для гибкого стекирования, как объединить их вместе и как настроить стек в Dashboard:

  1. Добавьте переключатели в сеть Dashboard.Это может быть новая сеть Dashboard для этих коммутаторов или существующая сеть с другими коммутаторами. Не настраивайте стек в Dashboard.
  2. Подключите восходящий канал к каждому коммутатору. Убедитесь, что порты восходящего канала отличаются от предполагаемых портов стекирования.
  1. Включите все коммутаторы, затем подождите несколько минут, пока они загрузят последнюю версию микропрограммы и обновлений с Dashboard. Коммутаторы могут перезагрузиться во время этого процесса.
    • Во время этого процесса светодиоды питания на передней панели каждого переключателя будут мигать.
    • После того, как коммутаторы загрузят и установят прошивку, их светодиоды питания будут гореть белым или зеленым.
  2. Выберите (но еще не подключайте) два порта на коммутатор в качестве выделенных портов стекирования. Стеки коммутаторов должны быть подключены по кольцевой топологии (как показано на следующем рисунке). Убедитесь, что порты стекирования отличаются от порта восходящей связи коммутатора. Фактически пока не подключайте порты. Это будет сделано на шаге 6.

Рекомендуется настроить и использовать идентичные типы портов в качестве портов гибкого стекирования. Например, 2 интерфейса 10 Гбит / с (SFP +) или 2 интерфейса 40 Гбит / с (QSFP) могут быть соединены вместе в качестве гибких портов стекирования.

  1. Настройте нужные порты для стекирования в Dashboard под Switch> Configure> Switch ports :
  1. Подключите стек коммутатора через предусмотренные порты стекирования, как показано на рисунке в шаге 4.
  2. Перейдите к Switch> Monitor> Switch stacks .
  3. Настройте стек коммутаторов в Dashboard. Если Dashboard уже обнаружил правильный стек в Обнаруженные потенциальные стеки , щелкните Подготовить этот стек , чтобы автоматически настроить стек.
    В противном случае, чтобы настроить стек вручную:
  • Перейдите к Switch> Monitor> Switch stacks .
  • Нажмите добавить один / Добавить стопку :
  • Установите флажки напротив коммутаторов, которые вы хотите объединить в стек, назовите стек и нажмите Create .:
  1. Отключите все восходящие каналы коммутатора, кроме одного, который будет восходящим каналом для стека коммутаторов.

Просмотр и создание ваших стеков

Страница Switch Stacks обеспечивает быстрый доступ ко всем настроенным стекам в сети, а также предоставляет простые варианты конфигурации для новых развертываемых стеков. Щелкнув на «Добавить стек» или при обнаружении стека, вы сможете легко настроить новый физический стек.

Проверить работоспособность стека

Просмотр стека

Чтобы проверить состояние стека визуально, просто щелкните любую строку в списке стека. Это приведет вас к обзору выбранной стопки. Отсюда вы можете легко получить представление о подключенных портах и ​​о том, какие коммутаторы содержатся в стеке. Мы включили возможность мигать светодиодами на коммутаторах в стеке, чтобы легко указать, какой это коммутатор, для всех, кто на месте смотрит на стек.

Управляющие элементы стека

Чтобы добавить или удалить участников стека, просто щелкните вкладку «Управление участниками» и выберите коммутаторы, которые вы хотите добавить или удалить из стека, и щелкните либо добавить, либо удалить коммутаторы.

Замена и клонирование элементов стека

Следующие шаги следует использовать в следующих случаях:

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

Примечание : Все следующие инструкции одинаковы для физического и гибкого стека коммутаторов.

Замена и клонирование члена стека Видео

Замена элемента стека

Следующие шаги будут клонировать исходный элемент стека и удалять его из стека:

  1. Выключите заменяемый элемент стека
  2. Заявите на складе новый / запасной выключатель:
  • Перейдите в Организация> Инвентарь
  • Нажмите кнопку Заявление
  • Введите серийный номер нового коммутатора.При замене нескольких элементов укажите все серийные номера
  1. Добавить коммутатор в сеть, содержащую стек
  • Выберите коммутатор, который нужно добавить в сеть
  • Нажмите Добавить в …
  • Выберите сеть и Добавить к существующей

Примечание : после добавления коммутатора в сеть и перед добавлением в стек или заменой он должен быть индивидуально переведен в оперативный режим и обновлен до той же сборки встроенного ПО, что и остальная часть стека.Невыполнение этого требования может помешать успешному объединению коммутатора в стек. Сконфигурированную сборку прошивки для сети можно проверить в Организация> Обновления прошивки . Мигающий белый или зеленый светодиод на индикаторе состояния на коммутаторе указывает на то, что идет обновление прошивки.

  1. (необязательно) Измените имя нового коммутатора
  • Перейдите к Switch> Switches
  • Выбрать новый переключатель
  • Щелкните рядом с заголовком, чтобы переименовать переключатель
  1. Клонировать и заменить элемент стека
  • Перейдите к коммутатору > Стеки коммутаторов
  • Выбрать существующий стек
  • Перейдите к вкладке Clone и замените элемент
  • Выберите переключатель источника, который необходимо заменить
  • Выберите переключатель назначения, который заменит переключатель источника
  1. Физически поменять местами переключатели

Старый коммутатор можно затем использовать в качестве автономного коммутатора или удалить из сети

Клонирование элемента стека

Следующие шаги будут клонировать исходный элемент стека без удаления его из стека.

  1. Заявить на складе новый / запасной выключатель:
  • Перейдите в раздел «Организация»> «Инвентарь»
  • Нажмите кнопку «Требовать»
  • Введите серийный номер нового коммутатора. При замене нескольких элементов укажите все серийные номера
  1. Добавить коммутатор в сеть, содержащую стек
  • Выберите коммутатор, который нужно добавить в сеть
  • Нажмите Добавить в …
  • Выберите сеть и Добавить к существующей
  1. (необязательно) Измените имя нового коммутатора
  • Перейдите к Switch> Switches
  • Выбрать новый переключатель
  • Щелкните рядом с заголовком, чтобы переименовать переключатель
  1. Клонировать элемент стека
  • Перейдите к Switch> Switches
  • Выбрать сменный выключатель
  • Щелкните Правка> Клонировать
  • Выберите исходный элемент стопки
  1. Добавьте новый коммутатор в стек.
  • Перейдите к коммутатору > Стеки коммутаторов
  • Выбрать существующий стек
  • Перейдите на вкладку Управление участниками . В разделе Добавить участников выберите переключатель, чтобы добавить

Пошаговое руководство по замене коммутатора для стеков

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

  1. На странице «Организация »> «Настроить»> «Инвентаризация» укажите новый коммутатор, а затем добавьте новый коммутатор в существующую сеть.

  1. Привязать новый переключатель к профилю шаблона.
  • Перейдите к родительскому шаблону на панели инструментов.

  • Перейдите к Switch> Configure> Profiles в этом шаблоне.

  • Щелкните соответствующий профиль.

  • Нажмите кнопку Переключатели привязки .

  • Установите флажок рядом с новым переключателем и нажмите кнопку Привязать к профилю .

  1. Обновление микропрограммы для нового коммутатора.
  • Обеспечьте новому коммутатору физическое восходящее соединение и затем включите его. Новый коммутатор необходимо подключить как автономное устройство, еще не добавленный в стек, чтобы он мог обновлять свою прошивку.

  • Подтвердите с помощью графика подключения или службы поддержки, что микропрограммное обеспечение коммутатора обновлено.

  • Пока новый коммутатор обновляется, вы можете выполнить следующие шаги, остановившись перед шагом 8, пока новый коммутатор не обновится.

  1. Получить текущую конфигурацию.
  • Перейдите к Switch> Configure> Profiles в родительском шаблоне.

  • Щелкните интересующий вас профиль.

  • Фильтр в Поиск переключателей… поле для имени старого переключателя.

  • Обратите внимание на конфигурацию локального переопределения. Сохраните в текстовом редакторе для использования на шаге 5.

  • В дочерней сети перейдите на страницу Switch> Monitor> Switch ports .

  • В поле Поиск переключателей… отфильтруйте по имени старого переключателя и выберите параметры столбца ниже.

  • Затем сделайте снимки экрана с конфигурациями портов или скопируйте и вставьте их в электронную таблицу или текстовый редактор.
  1. Настройте сменный переключатель.
  • На странице «Коммутатор »> «Монитор»> «Порты коммутатора » дочерней сети настройте порты коммутатора нового коммутатора на основе конфигурации, собранной на шаге 4.

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

  1. Выключите старый переключатель.
  2. Отменить привязку Отключиться от профиля.
  • На странице сведений о профиле шаблона установите флажок рядом со старым переключателем, а затем нажмите кнопку Отменить привязку .
  1. Добавьте новый коммутатор в стек.
  • Убедившись, что микропрограмма нового коммутатора обновлена, как указано в шаге 3, выключите новый коммутатор.

  • В дочерней сети перейдите на страницу Switch> Monitor> Switch stacks .

  • Щелкните нужную стопку.

  • Щелкните вкладку Управление участниками .

  • В разделе Добавить участников установите флажок рядом с новым переключателем, а затем нажмите кнопку Добавить переключатели .

  1. Удалите старый коммутатор из стека.
  • В дочерней сети перейдите на страницу Switch> Monitor> Switch stacks .

  • Щелкните нужную стопку.

  • Щелкните вкладку Управление участниками .

  • Установите флажок рядом со старым переключателем, а затем нажмите кнопку Удалить переключатели .

  1. Выполните физическое подключение нового коммутатора и установите его в стопку.
  1. Включите новый коммутатор.

Общие предупреждения

Убедитесь, что все элементы стека настроены на приборной панели, подключены к сети и подключены через их порты стекирования. При правильном подключении и настройке ошибка исчезнет в течение 20-30 минут. Если ошибка не исчезнет, ​​обратитесь в службу технической поддержки Cisco Meraki для дальнейшего устранения неполадок.

Текущие элементы стека этого коммутатора отличаются от конфигурации приборной панели.

Эта ошибка может возникнуть в следующих случаях:

  • Элементы стека настраиваются на панели управления, но не все элементы подключены через свои порты стекирования.
  • Элемент стека неисправен или отключен.
Этот коммутатор не подключен к стеку.

Эта ошибка может возникнуть в следующих случаях:

  • Коммутатор настроен на приборной панели как член стека, но не подключен к стеку.
Этот коммутатор не имеет конфигурации стека.

Эта ошибка может возникнуть в следующих случаях:

  • Коммутатор физически подключен как стек, но не настроен на приборной панели как член стека.

.

Стекирование коммутаторов Cisco 3650/3850 | СИ ДАРЛИНГТОН

Коммутаторы

«стекирование» подразумевают соединение нескольких коммутаторов вместе с помощью специальных портов StackWise на задней панели коммутатора.

Каждый коммутатор в стеке относится к члену стека. Члены работают вместе как единая система, административно представляясь как единый коммутатор. Стек коммутаторов из 3650/3850 (обратите внимание, что вы не можете смешивать их в стеке) может иметь до девяти коммутаторов с возможностью стекирования, подключенных через их стековые порты.

Альтернативным способом соединения коммутаторов было бы последовательное соединение коммутаторов с использованием портов на передней панели коммутатора. Помимо косметики, использование stackwise — лучший вариант по ряду причин:

  • не использует существующие порты переключения
  • по стеку максимизирует полосу пропускания между коммутаторами в стеке (160G)
  • все коммутаторы в стеке отображаются как один коммутатор на cli
  • с возможностью горячей замены / замены

Как наиболее эффективно объединить эти коммутаторы в стек? Я рада, что вы спросили.

Мы рассмотрим три области.

  1. Настройка стека новых коммутаторов
  2. Добавление или замена коммутатора в существующем стеке
  3. Обновление iOS

Настроить новый стек


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


Сначала физически подключите коммутаторы с помощью многослойных кабелей. Вот рекомендация Cisco:

————— 1 ——- 2 ————————————–

Каждый коммутатор имеет два порта стека, к которым подключены кабели стека. Если смотреть сзади, то порт стека слева — это Порт1, а порт справа — Порт2. Это верно для всех коммутаторов в стеке.

Эти два порта стека на каждом коммутаторе подключены к своему соседу, который определен как физически расположенный сверху и снизу.Верхний и нижний коммутаторы в стеке являются соседями для этой связи.

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

В нашу лабораторию. У нас есть стек из 3 x 3650, подключенных, как указано выше.

 Switch # показать стек-порты коммутатора
Коммутатор № Port1 Port2
----------------------------
1 ОК ОК
2 ОК ОК
3 ОК ОК

Переключатель # 

ОК. Мы проверили подключение на каждом из портов стека.

Концепция

: роли стека коммутаторов

Актив — он же мастер. Управляет стеком. Удерживает настройки запуска и запуска для стека. Только один активный коммутатор в стеке. Резервный — «резервное копирование активно», если есть проблема. Только один резервный коммутатор в стеке. Член — коммутатор в стеке, который не является активным или резервным коммутатором. Все остальные коммутаторы в стеке выполняют эту роль. Как и в случае выбора OSPF DR, мастер стека не вытесняет.Это означает, что для разработки желаемых ролей стека порядок включения коммутаторов может повлиять на то, какой коммутатор в стеке станет активным, то есть главным коммутатором (хотя, если бы мы действительно использовали этот метод, это довольно плохой способ сделать это — см. примечание 2 ниже). Принимая во внимание вышеприведенные выходные данные, в нашей лаборатории коммутаторы физически сгруппированы следующим образом:

В нашей лаборатории переключатели были извлечены из герметичных коробок, подключены к сети рекомендованным способом и включены одновременно.

 Переключатель # Показать переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                          H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f45.2380 1 V01 Готово
 2 Режим ожидания 74a0.2f58.7180 1 V01 Готов
 3 Member a0ec.f936.4d00 1 V01 Готов

Переключатель #

 

Почему роли переключателя соответствуют вышеприведенным выходным данным переключателя шоу?

Ответ состоит в том, что если все приоритеты коммутатора будут равны, коммутатор с САМЫМ НИЗКИМ MAC-адресом будет выигрывать и принимает активную роль.Макинтош следующего нижнего уровня в стеке берет на себя роль резервного, то есть он становится активным, если текущий активный выйдет из строя (в этом случае повторное избрание избегается и нет прерывания обслуживания). Другие коммутаторы в стеке принимают на себя роль члена до максимального общего размера стека в 9 коммутаторов.

Стек коммутаторов будет нормально работать в этой конфигурации с одним багбаром…

Концепция

: Номер переключателя (номер участника)

Обратите внимание на первый столбец в выходных данных переключателя шоу выше.По умолчанию коммутатор будет иметь номер члена по умолчанию 1 (см. Примечание 1 ниже). Обратите внимание, что номера участников были получены из роли коммутатора, причем активная роль принимает номер участника 1. Именно номер участника определяет нумерацию интерфейса для коммутатора в стеке.

Номер элемента 1 означает, что интерфейсы на этом индивидуальном коммутаторе будут Gi1 / 0 / 1-48. Однако в нашей лаборатории этот коммутатор физически является вторым физическим коммутатором в стеке! Точно так же Gi2 / 0 / 1-48 находятся на резервном коммутаторе, физически это первый коммутатор в стеке.Чтобы сделать администрирование коммутаторов менее запутанным, давайте изменим номер элемента в стеке, чтобы он соответствовал физическому стекам коммутаторов.

 Switch # переключатель 1 изменить номер 2
ВНИМАНИЕ: изменение номера переключателя может привести к изменению конфигурации этого переключателя.
переключатель. Конфигурация интерфейса, связанная со старым номером коммутатора, будет
остаются как подготовленная конфигурация. Вы хотите продолжить? [Да / нет] г
Switch # переключатель 2 перенумеровать 1
ВНИМАНИЕ: изменение номера переключателя может привести к изменению конфигурации этого переключателя.
переключатель.Конфигурация интерфейса, связанная со старым номером коммутатора, будет
остаются как подготовленная конфигурация. Вы хотите продолжить? [Да / нет] г
Switch # показать переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                           H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f45.2380 1 V01 Готово
 2 Ожидание 74a0.2f58.7180 1 V01 Готово
 3 Member a0ec.f936.4d00 1 V01 Готов

Переключатель # wr
Конфигурация здания ...
Сжатая конфигурация с 6558 байтов до 2242 байтов [OK]

Switch # показать переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                           H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активный 74a0.2f45.2380 1 V01 Готово
 2 Режим ожидания 74a0.2f58.7180 1 V01 Готов
 3 Участник a0ec.f936.4d00 1 V01 Готов 
 Switch # reload
На активном модуле выдается команда Reload, это перезагрузит весь стек
Продолжить перезагрузку? [подтвердить] y
<снип>
Нажмите RETURN, чтобы начать!


Switch> ru
Переключатель # sh переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                            H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
 1 Резервный 74a0.2f58.7180 1 V01 Готово
* 2 Активно 74a0.2f45.2380 1 V01 Готово
 3 Member a0ec.f936.4d00 1 V01 Готов

Переключатель # 

Обратите внимание, что хотя наши исходные номера участников были получены из роли коммутатора, изменение номеров участников не влияет на выбор активного / резервного. В этом случае роли Active и Standby по-прежнему выбираются с использованием MAC-адреса, все значения приоритета равны.

Поскольку наша нумерация интерфейсов фиксируется путем изменения номера элемента, согласования нумерации логического коммутатора с физической, стоит отметить, что технически не имеет значения, какой коммутатор активен, а какой резервный.По соглашению эти роли настраиваются как физический коммутатор 1 и коммутатор 2 в стеке соответственно.

Концепция

: приоритет переключения

Каждый коммутатор в стеке имеет значение приоритета от 1 до 15, по умолчанию 1 из коробки. Вместо того, чтобы использовать устройство разрешения конфликтов MAC-адресов во время выбора активного и резервного коммутаторов, мы можем вручную спроектировать, какой коммутатор мы хотим взять на себя эти роли переключателя, изменив значение приоритета. Чем выше, тем лучше. Давайте изменим приоритет физического переключателя 1 в верхней части нашего стека на 15, чтобы убедиться, что он берет на себя активную роль.

 # переключатель переключателя 1 приоритет 15
ВНИМАНИЕ: изменение приоритета переключателя может привести к изменению конфигурации для этого
переключатель. Вы хотите продолжить? [Да / нет] г
Переключатель # sh переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                            H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
 1 Резервный 74a0.2f58.7180 15 V01 Готово
* 2 Активный 74a0.2f45.2380 1 V01 Готово
 3 Member a0ec.f936.4d00 1 V01 Готов

Переключатель # 

Обратите внимание, что хотя значение приоритета не изменилось, роль не изменилась, выборы не являются приоритетными. Перезагрузка вызовет повторный выбор с использованием измененных значений приоритета. Для краткости, давайте также изменим значения приоритета физического переключателя 2 и 3, а затем перезагрузим весь стек.

 Переключатель # переключатель 2 приоритет 14
ВНИМАНИЕ: изменение приоритета переключателя может привести к изменению конфигурации для этого
переключатель.Вы хотите продолжить? [Да / нет] г
Переключатель # переключатель 3 приоритет 13
ВНИМАНИЕ: изменение приоритета переключателя может привести к изменению конфигурации для этого
переключатель. Вы хотите продолжить? [Да / нет] г
Переключатель # sh переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                            H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
 1 Резервный 74a0.2f58.7180 15 V01 Готово
* 2 Активно 74a0.2f45.2380 14 V01 Готово
 3 Member a0ec.f936.4d00 13 V01 Готово

Switch # reload
<снип>
Нажмите RETURN, чтобы начать.

Переключатель> переключатель sh
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                            H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активный 74a0.2f58.7180 15 V01 Готово
 2 Ожидание 74a0.2f45.2380 14 V01 Готово
 3 Участник a0ec.f936.4d00 13 V01 Готов 
 Переключатель> 

Обратите внимание, что, устанавливая значение приоритета физического переключателя 1 на приоритет 15, физического переключателя 2 на приоритет 14 и т. Д., Мы также влияем на номер элемента логического коммутатора, чтобы он соответствовал физическим коммутаторам. Это приведет к правильной нумерации интерфейсов. Итак, если нам нужен быстрый и простой способ настройки стека коммутаторов, приоритет — это единственное значение, которое нужно изменить (см. Здесь краткое руководство по настройке стека с использованием только приоритета)

Однако лучшее понимание ролей коммутаторов и номеров участников поможет в устранении любых неполадок при инициализации или внесении изменений в существующие стеки коммутаторов.

Краткое руководство: подготовка нового стека

Шаг 1 Сложите и сложите их. Физически установите все коммутаторы, которые должны быть объединены в стек, в состоянии выключено питание . Подсоедините все кабели, расположенные в виде стопки. Я упоминал, что переключатели не включаются?

Шаг 2 Включите физический коммутатор 1 (верх стека). Вставьте USB-накопитель с предпочитаемой операционной системой iOS в USB-разъем на передней панели коммутатора.

 Переключатель # copy usbflash0: cat3k_caa-Universalk9.SPA.03.07.03.E.152-3.E3.bin flash:
Целевое имя файла [cat3k_caa-universalalk9.SPA.03.07.03.E.152-3.E3.bin]?
Выполняется копирование ...
322991728 байт скопировано за 52,370 сек (6167495 байт / сек)

Переключатель # verify / md5 flash: cat3k_caa-Universalk9.SPA.03.07.03.E.152-3.E3.bin
...Готово!
verify / md5 (flash: cat3k_caa-Universealk9.SPA.03.07.03.E.152-3.E3.bin)
= 71d48b44bb5ec13d4b4d47d8c3dc9dd7 

Вы можете найти md5 файла на Cisco.com или взять его из файла с помощью программы проверки md5, например WinMd5 (доступны другие средства проверки md5).

Шаг 3 Включите автоматическое обновление IOS. Это будет использоваться другими членами коммутатора, присоединяющимися к стеку. По умолчанию это отключено.

 Switch (config) # включение автоматического обновления программного обеспечения 

Шаг 4 Измените приоритет физического коммутатора 1 на приоритет 15, сохраните. Теперь запустите обновление программного обеспечения, которое также перезагрузит коммутатор.

 Переключатель # переключатель sh
ВНИМАНИЕ: изменение приоритета переключателя может привести к изменению конфигурации для этого
переключатель.Вы хотите продолжить? [Да / нет] г
Переключатель # sh переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                   H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f45.2380 1 V01 Готово

Switch # переключатель 1 приоритет 15
ПРЕДУПРЕЖДЕНИЕ. Изменение приоритета переключателя может привести к изменению конфигурации этого переключателя. Вы хотите продолжить? [Да / нет] г
Switch # sh switch ВНИМАНИЕ: изменение приоритета переключения может привести к конфигурации
изменение для этого переключателя.Вы хотите продолжить? [Да / нет] г
Переключатель # sh переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                   H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f45.2380 15 V01 Готово

Переключатель #
Переключатель # wr
Switch # файл установки программного обеспечения
флэш: cat3k_caa-universalalk9.SPA.03.07.03.E.152-3.E3.bin
Подготовка к установке...
[1]: Начало операции установки
[1]: Расширяемый пакет flash: cat3k_caa-universalalk9.SPA.03.07.03.E.152-3.E3.bin
[1]: Копирование файлов пакета
[1]: файлы пакета скопированы
[1]: Завершена флэш-память расширяемого пакета: cat3k_caa-universalalk9.SPA.03.07.03.E.152-3.E3.bin
[1]: Проверка и копирование расширенных файлов пакета во флэш-память:
[1]: Проверены и скопированы расширенные файлы пакетов во флэш-память:
[1]: Запуск проверки совместимости
[1]: проверка совместимости завершена.
[1]: Запуск предустановочной обработки приложения
[1]: Завершена предустановочная обработка приложения.
[1]: Список старых файлов: Удалена cat3k_caa-base.SPA.03.06.00E.pkg Удалено cat3k_caa-drivers.SPA.03.06.00E.pkg Удалено cat3k_caa-infra.SPA.03.06.00E.pkg Удалено cat3k_caa-iosd-Universealk9.SPA.152-2.E.pkg Удалено cat3k_caa- platform.SPA.03.06.00E.pkg Удален cat3k_caa-wcm.SPA.10.2.102.0.pkg
[1]: Новый список файлов: Добавлен cat3k_caa-base.SPA.03.07.03E.pkg Добавлен cat3k_caa-drivers.SPA.03.07.03E.pkg Добавлен cat3k_caa-infra.SPA.03.07.03E.pkg Добавлен cat3k_caa-iosd-Universalk9 .SPA.152-3.E3.pkg Добавлен cat3k_caa-platform.SPA.03.07.03E.pkg Добавлен cat3k_caa-wcm.SPA.10.3.130.0.pkg
[1]: Создание ожидающего файла инициализации
[1]: установка программного обеспечения завершена. Новое программное обеспечение загрузится при перезагрузке.
[1]: Фиксация файла подготовки
[1]: Вы хотите продолжить перезагрузку? [да / нет]: да
[1]: Переключатель перезагрузки №

Шаг 5 Включите физический переключатель 2 (следующий выключен). Это будет резервный коммутатор для стека. Коммутатор перезагрузится дважды, второй раз из-за автоматического обновления IOS, прежде чем он присоединится к стеку.

 Переключатель # переключатель sh
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - Локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                   H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f45.2380 15 V01 Готово
2 Режим ожидания 74a0.2f58.7180 1 V01 Готов

 

Теперь измените приоритет второго физического коммутатора на 14

 Переключатель # переключатель 2 приоритет 14
ВНИМАНИЕ: изменение приоритета переключателя может привести к изменению конфигурации для этого
переключатель.Вы хотите продолжить? [Да / нет] г
Переключатель # sh переключатель
Mac-адрес коммутатора / стека: 74a0.2f45.2380 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                   H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f45.2380 15 V01 Готово
2 Режим ожидания 74a0.2f58.7180 14 V01 Готов 

Шаг 6 Продолжите работу по стеку, включив каждый дополнительный коммутатор-член, по одному.Нет необходимости дожидаться полной загрузки каждого коммутатора перед включением следующего, поскольку коммутатор, присоединяющийся к стеку, займет наименьший доступный номер участника . Чтобы гарантировать, что этот порядок сохраняется после перезагрузки, продолжайте уменьшать приоритет коммутатора, то есть физический коммутатор 3 с приоритетом 13, переключатель 4 с приоритетом 12 и т. Д. При подключении каждого коммутатора. После настройки всех коммутаторов-членов сохраните и перезагрузите весь стек. Проверить.

Изменение существующего стека

Замена или добавление коммутатора в существующий стек

Ловушка 1: Добавление нового коммутатора, который уже включен, в стек (т. Е.e перед подключением к нему кабелей стека) приведет к перезагрузке всего стека и, возможно, переизбранию ролей (см. примечание 3). Для бесперебойного обслуживания убедитесь, что добавляемый или удаляемый коммутатор выключен / выключен, прежде чем подключать к нему или отключать кабели стека. Это также сводит к минимуму риск случайного разделения стека при отсоединении стековых кабелей, в зависимости от того, как они подключены.

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

Добавление нескольких коммутаторов в существующий стек

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

 Switch # reload slot [номер коммутатора] 

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

Удаление конфигурации стека с коммутатора

Вы когда-нибудь включали коммутатор, снятый с производства, только для того, чтобы обнаружить, что на нем установлена ​​старая конфигурация стека, а номера интерфейсов начинаются с gi3 / 0/1? Раздражает. Вы когда-нибудь продолжали работать с ним в этом состоянии, несмотря на то, что не могли вспомнить команды для сброса конфигурации стека? Не будь этим парнем.

Есть два способа решить эту проблему.

Вариант 1: перейти на ядерную программу.Заводские настройки переключателя

Примечание. Эта опция указана в документации Cisco, однако в моем тестировании она не сбрасывала приоритет стека на 1, т. Е. Значение перед заводскими настройками было сохранено.

Шаг 1 Нет необходимости выключать и снова включать питание. Удалите загрузочную конфигурацию, если она существует (см. Примечание 4 ниже). Пока переключатель находится под напряжением, нажмите и удерживайте кнопку режима. Светодиоды переключателя начнут мигать примерно через 3 секунды.

Шаг 2 Продолжайте удерживать кнопку Mode.Светодиоды перестают мигать еще через 7 секунд, а затем переключатель перезапускается.

Вариант 2: перенастроить существующую конфигурацию стека

Невозможно отключить или сбросить функцию стека на 3560/3850. Даже автономный коммутатор работает в стеке, хотя и сам по себе. Следующая команда присутствует в коммутаторе, который только что был установлен на заводе по умолчанию и включен автономно.

 переключатель 1 положение ws-c3650-48pd 

Проверка

 Переключатель # Показать переключатель
Mac-адрес коммутатора / стека: 74a0.2fc4.4600 - Локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
                                             H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2fc4.4600 1 V01 Готово

Переключатель # 

Вот коммутатор, удаленный из двух.

 Switch # show run | в положении
переключатель 1 положение ws-c3650-48pd
переключатель 2 положения ws-c3650-48pd 
 Переключатель # переключатель sh
Mac-адрес коммутатора / стека: 74a0.2f59.dd80 - Локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
 H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f59.dd80 14 V01 Готово
 2 Участник 0000.0000.0000 0 0 Предоставлено
 

Provisioned означает, что коммутатор был там, но его больше нет. Мы можем отключить резервный коммутатор, и при следующей перезагрузке его больше не будет.

 Switch (config) # no switch 2 provision ws-c3650-48pd
Switch (config) #end
Переключатель # sh переключатель
* 22 июня, 23:29:14.255:% SYS-5-CONFIG_I: настраивается с консоли консольным переключателем
Mac-адрес коммутатора / стека: 74a0.2f59.dd80 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
 H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f59.dd80 14 V01 Готово
 2 Участник 0000.0000.0000 0 0 Не предусмотрено

Переключатель # 

удаляет старую конфигурацию стека.

 Номер переключателя приоритет переключателя 1 1 

восстанавливает приоритет по умолчанию.Ни одно из наших изменений не вступит в силу до перезагрузки

.

 Switch # reload
<снип>
 
 Нажмите RETURN, чтобы начать. 
 Переключатель # переключатель sh
* 22 июня 23:29: 14.255:% SYS-5-CONFIG_I: настраивается с консоли консольным переключателем
Mac-адрес коммутатора / стека: 74a0.2f59.dd80 - локальный Mac-адрес
Время ожидания постоянства Mac: неограниченно
 H / W ток
Switch # Роль Mac-адрес Приоритет Версия Состояние
-------------------------------------------------- ----------
* 1 Активно 74a0.2f59.dd80 14 V01 Готово 
 

Для простой настройки стека измените значение приоритета коммутатора.

Помните обо всех параметрах конфигурации стека (т.е. не только о приоритете), которые могут повлиять на топологию стека.

Обратите внимание на порядок работы при внесении изменений в стеки коммутатора, чтобы минимизировать нарушения.

Банкноты

1. Кнопка режима на передней панели коммутатора полезна не только для проверки приоритета стека. Посмотрите на индикаторы портов на последних двух портах коммутатора (10 гигабайт или порты sfp). Если оба горят, этот визуальный индикатор показывает, что коммутатор работает на полной полосе пропускания.Мы также можем проверить это на cli

 Switch # показать скорость стека коммутатора

Скорость кольца стека: 160 г
Конфигурация кольца стека: вниз
Протокол кольцевого стека: StackWise 

2. Сначала включите выключатель, который вы хотите активировать самостоятельно. Это скачки на одну лошадь. Любые коммутаторы, включенные через 2 минуты после этого, не будут участвовать в выборах. Обратите внимание, что такой подход не гарантирует стабильную топологию стека при перезагрузке. Последнее замечание о поведении без предупреждения. Если активный коммутатор удаляется из стека, резервный коммутатор становится активным.Любой коммутатор, впоследствии повторно вставленный в стек с более высоким приоритетом (даже если впоследствии будет повторно вставлен исходный активный коммутатор), не приведет к освобождению активного коммутатора от своей роли или срабатыванию выборов.

3. Результат соединения двух автономных коммутаторов с питанием друг от друга с помощью одного стека. Несмотря на разные приоритеты, каждый из них вызывает слияние стека и перезагружает оба.

 Переключатель #
* 22 июня, 21: 13: 59.869:% STACKMGR-1-STACK_LINK_CHANGE: 1 stack-mgr: порт стека 2 на коммутаторе 1 активен
* 22 июня, 21:14:00.252:% IOSXE-3-PLATFORM: 1 стек процесса-mgr:: -Traceback = 1 # 87f75377a54ddceb043862d594ac8de7: 54DA2000 + 9B564: 54DA2000 + 1F854: 54DA2000 + 67B54: 54DA2000 + 5E5DCU2000: 54DA2000 + 5E5Cutils + 5e5cutil2 + DA3C pthread: 2AD53000 + 5DC8
* 22 июня 21: 14: 00.262:% IOSXE-3-PLATFORM: 1 диспетчер стека процессов:: -Traceback = 1 # 87f75377a54ddceb043862d594ac8de7: 54DA2000 + 1F854: 54DA2000 + 67B54: show
<Среда, 22 июня, 21:14:00 2016> Сообщение от sysmgr: Код причины: [4] Причина сброса: сброс / перезагрузка запрошены [менеджером стека].[объединение стека]

Размонтирование файловых систем ng3k ...
Размонтирован / dev / sda3 ...
Предупреждение! - некоторые файловые системы ng3k могут быть неправильно размонтированы ...
Пожалуйста, подождите, пока перезагружаете систему ...
Перезапуск системы.

Загрузка ... 

4. Вывод нажатия кнопки режима до и после стирания start-config:

 Переключатель #
* 22 июня 20:37: 36.950:% EXPRESS_SETUP-6-MODE_BUTTON_RESET_IGNORED: кнопка режима нажата более 10 секунд, и конфигурация запуска присутствует, следовательно, не перезагружается
Переключатель # erase startup-config
Стирание файловой системы NVRAM приведет к удалению всех файлов конфигурации! Продолжать? [подтвердить]
[В ПОРЯДКЕ]
Стирание NVRAM: полное
Переключатель #
* 22 июня, 20:38:06.795:% SYS-7-NV_BLOCK_INIT: инициализирована геометрия NVRAM
Переключатель #
consoleless_setup_process: вход в режим настройки
* 22 июня 20:38: 15.625:% EXPRESS_SETUP-6-MODE_ENTERED:
* 22 июня 20:38: 40.953:% EXPRESS_SETUP-5-CONFIG_IS_RESET: конфигурация сброшена, и система теперь перезагружается
* 22 июня 20: 38: 46.209:% SYS-5-RELOAD: перезагрузка запрошена процессом под управлением NGWC. Причина перезагрузки: перезагрузка из-за быстрой настройки. 

Список литературы

Руководство по установке аппаратного обеспечения коммутатора

Catalyst 3650

Catalyst 3650 Руководство по настройке диспетчера стека и высокой доступности

Нравится:

Нравится Загрузка…

.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *