Обратная польская нотация

Алгоритмы и методы: Обратная польская запись

Обратная польская нотация

Как правило арифметические выражения удобно преобразовывать в обратную польскую запись (ОПЗ), чтобы избавиться от скобок, содержащихся в выражении. Выражения, преобразованные в ОПЗ, можно вычислять последовательно, слева направо.

Существует два наиболее известных способа преобразования в ОПЗ. Рассмотрим коротко каждый из них:

1. Преобразование выражения в ОПЗ с использованием стека

Нам понадобится стек для переменных типа char, т.к. исходное выражение мы получаем в виде строки.

Рассматриваем поочередно каждый символ:1. Если этот символ — число (или переменная), то просто помещаем его в выходную строку.2. Если символ — знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3).

Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка.

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

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

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

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

Рассмотрим алгоритм на примере простейшего выражения:Дано выражение:

a + ( b — c ) * d

Рассмотрим поочередно все символы:

Символ Действие Состояние выходной строки после совершенного действия Состояние стека после совершенного действия
'a' — переменная. Помещаем ее в выходную строкупуст 
'+' — знак операции. Помещаем его в стек (поскольку стек пуст, приоритеты можно не проверять)
'(' — открывающая скобка. Помещаем в стек.+ ( 
'b' — переменная. Помещаем ее в выходную строкуa b + ( 
'-' — знак операции, который имеет приоритет 2. Проверяем стек: на вершине находится символ '(', приоритет которого равен 1. Следовательно мы должны просто поместить текущий символ '-' в стек.a b + ( — 
'c' — переменная. Помещаем ее в выходную строкуa b c + ( —
')' — закрывающая скобка. Извлекаем из стека в выходную строку все символы, пока не встретим открывающую скобку. Затем уничтожаем обе скобки.a b c — 
'*' — знак операции, который имеет приоритет 3. Проверяем стек: на вершине находится символ '+', приоритет которого равен 2, т.е. меньший, чем приоритет текущего символа '*'. Следовательно мы должны просто поместить текущий символ '*' в стек.a b c — + * 
'd' — переменная. Помещаем ее в выходную строкуa b c — d + * 

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

Поскольку стек — это структура, организованная по принципу LIFO, сначала извлекается символ '*', затем символ '+'.Итак, мы получили конечный результат:

a b c — d * +

Реализацию алгоритма можно скачать здесь.
Этот алгоритм также используется в программе Calc3, которая находится здесь (см. файл CPPNCalc.cpp).

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

сохраняет их во временной переменной и помещает в выходную строку, когда к ней вернется управление после вызова функции mult_div()). Функция begin() вызывает функцию mult_div(), обрабатывающую знаки деления и умножения (т.е. сохраняет их во временной переменной и помещает в выходную строку, когда к ней вернется управление после вызова функции symbol())..

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

Если она не дожидаестя закрывающей скобки, это означает, что в выражении содержится синтаксическая ошибка.

Если функция symbol() получает переменную, то помещает ее в выходную строку.

Рассмотрим работу этих функций на примере исходного выражения:
a + ( b — c ) * d

Передачу управления от одной функции к другой (т.е. вызов функции или возвращение управления вызвавшей функции) обозначим знаком —>

  1. Текущим символом является 'a'. Преобразование начинается с вызова функции begin(). Далее получаем цепочку вызовов begin() —> mult_div() —> symbol().

    Функция symbol() помещает символ 'a' в выходную строку, заменяет текущий символ на '+' и возвращает управление. Состояние выходной строки: a

  2. Текущим символом является '+'. symbol() —> mult_div() —> begin(). Функция begin() запоминает текущий символ во временной переменной и заменяет его на '('.

    Состояние выходной строки: a

  3. Текущим символом является '('. begin() —> mult_div() —> symbol(). Функция symbol() заменяет текущий символ на 'b' и вызывает функцию begin(). Состояние выходной строки: a
  4. Текущим символом является 'b'. symbol()—> begin() —> mult_div() —> symbol().

    Функция symbol() помещает символ 'b' в выходную строку, заменяет текущий символ на '-' и возвращает управление. Состояние выходной строки: a b

  5. Текущим символом является '-'. symbol() —> mult_div() —> begin().

    Функция begin() запоминает текущий символ во временной переменной (поскольку эта переменная — локальная, это, конечно, не означает потерю символа '+', сохраненного ранее) и заменяет текущий символ на 'c'. Состояние выходной строки: a b

  6. Текущим символом является 'с'. begin() —> mult_div() —> symbol().

    Функция symbol() помещает символ 'с' в выходную строку, заменяет текущий символ на ')' и возвращает управление. Состояние выходной строки: a b c

  7. Текущим символом является ')'.

    Поскольку закрывающую скобку ни одна функция не обрабатывает, функции поочередно возвращают управление, пока оно не возвратится к функции symbol(), которая обрабатывала открывающую скобку, т.е. цепочка будет такой: symbol() —> mult_div() —> begin(). (здесь функция begin() помещает сохраненный символ '-' в выходную строку) begin() —> symbol().

    Далее функция symbol() заменяет текущий символ на '*' Состояние выходной строки: a b c —

  8. Текущим символом является '*'. symbol() —> mult_div() Функция mult_div() запоминает текущий символ во временной переменной и заменяет его на 'd' Состояние выходной строки: a b c —
  9. Текущим символом является 'd'.

    mult_div() —> symbol(). Функция symbol() помещает символ 'd' в выходную строку и возвращает управление. Состояние выходной строки: a b c — d

  10. Строка разобрана. Возвращение управления: symbol() —> mult_div() (здесь функция mult_div() помещает сохраненный символ '*' в выходную строку). Далее: mult_div() —> begin() (здесь функция begin() помещает сохраненный символ '+' в выходную строку) Состояние выходной строки: a b c — d * +

Реализация на С++ (для работы со строками и исключениями используются классы библиотеки VCL):
class TStr2PPN { AnsiString instr, outstr; //input & output strings char curc; //the current character

int iin; //the index of the input string

char nextChar(); //get the next character void begin(); //handle plus & minus void mult_div(); //handle multiplication & division

void symbol(); //handle characters & brackets

public: TStr2PPN() { //constructor iin = 1;

}

void convert(char *str); //convert to PPN AnsiString get_outstr(); //get the output string

};

//get the next characterinline char TStr2PPN::nextChar() { if(iin

Источник: http://www.interface.ru/home.asp?artid=1492

Обратная польская нотация

Обратная польская нотация

Передо мной стояли задачи:

  • перевести выражение в обратную польскую нотацию;
  • посчитать значение выражения.

Также я реализовала унарный минус, деление и функции cube(), sqrt(), pow10().

ВыражениеОбратная польская нотацияРезультат
15 * -(3 — 4)15 3 4 — u- *15
sqrt(4) + (8 * 0.5)4 sqrt 8 0.5 * +6
-cube(-3)3 u- cube u-27
92 / 1092 10 /9.2
pow10(2) — 95 + 4 * 82 pow10 95 — 4 8 * +37

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

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

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

  • если в записи встретили число, то кладём его в стэк;
  • если в записи встретили функцию или унарный минус, то :
    • вытаскиваем из стэка верхний элемент;
    • применяем функцию к нему;
    • кладём элемент обратно в стэк;
  • если в записи встретили бинарный оператор, то:
    • вытаскиваем из стэка два верхних элемента;
    • выполняем над ними операцию;
    • кладём в стэк результат выполнения операции;
  • выводим последний элемент стэка.

Код программы (http://ideone.com/c69iJg):

import java.util.*; import java.lang.*; import java.io.*; class ExpressionParser { private static String operators = «+-*/»; private static String delimiters = «() » + operators; public static boolean flag = true; private static boolean isDelimiter(String token) { if (token.length() != 1) return false; for (int i = 0; i < delimiters.length(); i++) { if (token.charAt(0) == delimiters.charAt(i)) return true; } return false; } private static boolean isOperator(String token) { if (token.equals("u-")) return true; for (int i = 0; i < operators.length(); i++) { if (token.charAt(0) == operators.charAt(i)) return true; } return false; } private static boolean isFunction(String token) { if (token.equals("sqrt") || token.equals("cube") || token.equals("pow10")) return true; return false; } private static int priority(String token) { if (token.equals("(")) return 1; if (token.equals("+") || token.equals("-")) return 2; if (token.equals("*") || token.equals("/")) return 3; return 4; } public static List parse(String infix) { List postfix = new ArrayList(); Deque stack = new ArrayDeque(); StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true); String prev = ""; String curr = ""; while (tokenizer.hasMoreTokens()) { curr = tokenizer.nextToken(); if (!tokenizer.hasMoreTokens() && isOperator(curr)) { System.out.println("Некорректное выражение."); flag = false; return postfix; } if (curr.equals(" ")) continue; if (isFunction(curr)) stack.push(curr); else if (isDelimiter(curr)) { if (curr.equals("(")) stack.push(curr); else if (curr.equals(")")) { while (!stack.peek().equals("(")) { postfix.add(stack.pop()); if (stack.isEmpty()) { System.out.println("Скобки не согласованы."); flag = false; return postfix; } } stack.pop(); if (!stack.isEmpty() && isFunction(stack.peek())) { postfix.add(stack.pop()); } } else { if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev) && !prev.equals(")")))) { // унарный минус curr = "u-"; } else { while (!stack.isEmpty() && (priority(curr)

Источник: https://java.mazurok.com/?p=454

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

Обратная польская нотация

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

Ведь существует прекрасный механизм, известный, как обратная польская запись. О том, что это такое и как с этим работать я и хочу вам рассказать. В математике существует древняя традиция помещать оператор между операндами (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. Теперь все могут написать свой калькулятор. С блэкджеком и скобками.

  • алгоритмы
  • обратная польская запись

Источник: https://habr.com/post/100869/

Обратная польская запись: алгоритм, методы и примеры

Обратная польская нотация

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

Инфиксная запись

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

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

В программировании использовать нотацию со знаками операций необязательно. Например, х + у можно записать в виде функции сложить (х, у), в которую компилятор в конце концов и преобразует инфиксную нотацию.

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

Трансляторы формул

Первый действительно успешный язык программирования Fortran стал таким в основном потому, что арифметические выражения (т. е. формулы) в нем преобразовывались (транслировались) в код, откуда и произошло его название – FORmula TRANslation.

До этого их приходилось записывать, например, в виде функций сложить (а, умножить (b, c)).

В Коболе проблема реализации автоматического преобразования формул считалась очень трудной, поскольку программистам приходилось писать такие вещи, как Add A To B Mutliply By C.

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

На самом деле следует умножить 3 на 4 и прибавить 2. Этот пример иллюстрирует, что вычисление инфиксного выражения часто требует изменения порядка операторов и их операндов. Кроме того, приходится использовать скобки, чтобы нотация выглядела более ясно.

Например, (2 + 3) * (4 + 5) нельзя записать без скобок, потому что 2 + 3 * 4 + 5 означает, что необходимо умножить 3 на 4 и добавить 2 и 5.

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

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

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

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

Так, выражение АВ + представляет собой пример обратной польской записи для A + B.

Неограниченное число операндов

Непосредственным преимуществом нотации является то, что она обобщается n-адическим оператором, а инфиксная нотация на самом деле работает только с двумя операндами, т. е. по своей природе подходит только для бинарных операций.

Так, например, ABC @ является обратным польским выражением с использованием триадического знака, который находит максимальное значение из A, B и C. В этом случае оператор действует на 3 операнда слева от себя и соответствует вызову функции @ (A, В, С).

Если попытаться записать символ @ в качестве инфиксного, например A @ BC или что-то подобное, то становится понятно, что это попросту не работает.

Приоритет задается порядком

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

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

То есть если вычисляется AB + C * по одному оператору за раз, то получится A B + C * -> (A B +) * C -> (A+B)*C.

Алгоритм вычисления

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

Например, в ОПН выражение 5 + 6 * 7 будет выглядеть как 5, 6, 7 *, +, и оно может быть вычислено просто путем сканирования слева направо и записи значений в стек. Каждый раз, когда встречается знак операции, выбираются 2 верхних элемента из машинной памяти, применяется оператор и результат возвращается в память.

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

Например:

  • S = () 5, 6, 7, *, + поместить 5 в стек.
  • S = (5) 6, 7, *, + поместить 6 в стек.
  • S = (5, 6) 7, *, + поместить 7 в стек.
  • S = (5, 6, 7) *, + выбрать 2 значения из стека, применить * и поместить результат в стек.
  • S = (5, 6 * 7) = (5, 42) + выбрать 2 значения из стека, применить + и поместить результат в стек.
  • S = (5 + 42) = (47) вычисление завершено, результат находится в вершине стека.

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

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

Примеры на языках программирования

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

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

toktype := num;

read(с);

if с in ['+', '-', '*', '/'] then begin

if eoln then cn := ' ' else read(cn);

if cn = ' ' then

case с of

'+': toktype := add; '-': toktype := sub;

'*': toktype := mul; '/': toktype := div

end

else begin

if с = '-' then sgn := -1 else error := с '+';

с := cn

end

end;

if (not error) and (toktype = num) then getnumber;

if toktype num then begin

у := рор; х := рор;

if not error then

case toktype of

add: z := х+у; sub: z := х-у; mul: z := х*у; div: z := х/у

end

push(z);

C-реализация обратной польской записи (приведен часть программы):

for (s = strtok(s, w); s; s = strtok(0, w)) {

a = strtod(s, &e);

if (e > s) push(a);

#define rpnop(x) printf(«%с:», *s), b = pop(), a = pop(), push(x)

else if (*s == '+') rpnop(a + b);

else if (*s == '-') rpnop(a — b);

else if (*s == '*') rpnop(a * b);

else if (*s == '/') rpnop(a / b);

#undef rpnop

}

Аппаратные реализации

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

Для сложения 2 и 3 в них необходимо ввести 2, затем 3 и нажать кнопку «плюс».

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

Компания Burroughs даже построила мэйнфрейм, у которого не было никакой другой оперативной памяти, кроме стека. Единственное, что делала машина, – применяла алгоритмы и методы обратной польской записи к центральному стеку. Все ее операции расценивались как операторы ОПН, действие которых распространялось на n верхних значений.

Например, команда Return брала адрес из вершины стека и т. д. Архитектура такой машины была простой, но недостаточно быстрой, чтобы конкурировать с более общими архитектурами.

Многие, однако, до сих пор сожалеют о том, что такой простой и элегантный подход к вычислениям, где каждая программа была выражением ОПН, не нашел своего продолжения.

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

Так в чем смысл шутки об обратной польской сосиске?

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

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

Но возможно, для этого потребуется слишком большой стек…

Источник: https://FB.ru/article/321181/obratnaya-polskaya-zapis-algoritm-metodyi-i-primeryi

Разбор выражений. Обратная польская нотация

Обратная польская нотация

добавлено: 11 Jun 2008 10:44
редактировано: 10 Sep 2012 14:08

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

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

Обратная польская нотация

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

Например, следующее выражение:

в обратной польской нотации записывается следующим образом:

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

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

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

Очевидно, этот простой алгоритм выполняется за , т.е. порядка длины выражения.

Разбор простейших выражений

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

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

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

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

Будем идти по строке слева направо. Если текущий элемент — цифра или переменная, то положим в стек значение этого числа/переменной. Если текущий элемент — открывающая скобка, то положим её в стек.

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

Наконец, если текущий элемент — операция, то, пока на вершине стека находится операция с таким же или большим приоритетом, будем выталкивать и выполнять её.

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

Вот реализация данного метода на примере обычных операций :

bool delim (char c) { return c == ' ';} bool is_op (char c) { return c=='+' || c=='-' || c=='*' || c=='/' || c=='%';} int priority (char op) { return op == '+' || op == '-' ? 1 : op == '*' || op == '/' || op == '%' ? 2 : -1;} void process_op (vector & st, char op) { int r = st.back(); st.pop_back(); int l = st.back(); st.pop_back(); switch (op) { case '+': st.push_back (l + r); break; case '-': st.push_back (l — r); break; case '*': st.push_back (l * r); break; case '/': st.push_back (l / r); break; case '%': st.push_back (l % r); break; }} int calc (string & s) { vector st; vector op; for (size_t i=0; i= priority(s[i])) process_op (st, op.back()), op.pop_back(); op.push_back (curop); } else { string operand; while (i = priority(curop)) process_op (st, op.back()), op.pop_back();

Правоассоциативность

Правоассоциативность оператора означает, что при равенстве приоритетов операторы вычисляются справа налево (соотвественно, левоассоциативность — когда слева направо).

Как уже было отмечено выше, унарные операторы обычно являются правоассоциативными. Другой пример — обычно операция возведения в степень считается правоассоциативной (действительно, abc обычно воспринимается как a(bc), а не (ab)c).

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

Таким образом, единственные отличия нужно внести в функцию calc:

int calc (string & s) {… while (!op.empty() && ( left_assoc(curop) && priority(op.back()) >= priority(curop) || !left_assoc(curop) && priority(op.back()) > priority(curop)))…}

Источник: https://e-maxx.ru/algo/expressions_parsing

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