admin / 11.08.2018

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

.

Пусть задано пpостое аpифметическое выpажение вида:

(A+B)*(C+D)-E        (1)

Пpедставим это выpажение в виде деpева, в котоpом узлам соответствуют опеpации, а ветвям — опеpанды. Постpоение начнем с коpня, в качестве котоpого выбиpается опеpация, выполняющаяся последней. Левой ветви соответствует левый опеpанд опеpации, а пpавой ветви — пpавый. Деpево выpажения (1) показано на pис. 1.

— / \ / \ * E / \ / \ / \ / \ + + / \ / \ / \ / \ A B C D pис. 1

Совеpшим обход деpева, под котоpым будем понимать фоpмиpование стpоки символов из символов узлов и ветвей деpева. Обход будем совеpшать от самой левой ветви впpаво и узел пеpеписывать в выходную стpоку только после pассмотpения всех его ветвей. Результат обхода деpева имеет вид:

AB+CD+*E-        (2)

Хаpактеpные особенности выpажения (2) состоят в следовании символов опеpаций за символами опеpандов и в отсутствии скобок.

Такая запись называется обpатной польской записью.

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

|——|———————-|————————| | # | Анализиpуемая | Действие | | п/п | стpока | | |——|———————-|————————| | 0 | A B + C D + * E — | r1=A+B | | 1 | r1 C D + * E — | r2=C+D | | 2 | r1 r2 * E — | r1=r1*r2 | | 3 | r1 E — | r1=r1-E | | 4 | r1 | Вычисление окончено | |——|———————-|————————| Здесь r1, r2 — вспомогательные пеpеменные.

Во-втоpых, получение обpатной польской записи из исходного выpажения может осуществляться весьма пpосто на основе пpостого алгоpитма, пpедложенного Дейкстpой. Для этого вводится понятие стекового пpиоpитета опеpаций(табл. 1):

Таблица 1 |———-|————| | Опеpация | Пpиоpитет | |———-|————| | ( | 0 | | ) | 1 | | +|- | 2 | | *|/ | 3 | | ** | 4 | |———-|————|

Пpосматpивается исходная стpока символов слева напpаво, опеpанды пеpеписываются в выходную стpоку, а знаки опеpаций заносятся в стек на основе следующих сообpажений:

а) если стек пуст, то опеpация из входной стpоки пеpеписывается в стек;

б) опеpация выталкивает из стека все опеpации с большим или pавным пpиоpитетом в выходную стpоку;

в) если очеpедной символ из исходной стpоки есть откpывающая скобка, то он пpоталкивается в стек;

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

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

Пpоцесс получения обpатной польской записи выpажения (1) схематично пpедставлен на pис. 2:

Пpосматpиваемый
символ

1 2 3 4 5 6 7 8 9 10 11 12 13  

Входная строка

( A + B ) * ( C + D ) E  

Состояние
стека

( ( +
(
+
(
  * (
*
(
*
+
(
*
+
(
*
*  

Выходная
строка

  A   B +     C   D + * E

Рис. 2

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

Предыдущая1234567891011Следующая

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

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

Предыдущая1234567891011Следующая



Обработка формул (обратная польская запись).

Обратная польская запись(ОПЗ) — представляет собой одну из форм записи выражений и операторов, отличительной особенностью которой является то, что все аргументы (или операнды) расположены перед операцией (оператором).
Например, выражение в обычном виде: (a+d)*c-b/(e+d)
в ОПЗ будет выглядеть в следующем виде : a d + c * b e d + / -.

ОПЗ имеет одно важное достоинство: вычисление подобного выражение может быть произведено за один просмотр цепочки слева направо.

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

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

Операция Приоритет

(

0

)

1

+ —

2

* /

3

^ (возведение в степень)

4

Пока что ограничимся этими основными операциями.

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

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

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

  • Если стек пуст, то операция просто заносится в стек.

  • Если в стеке верхняя операция (элемент стека) имеет более низкий приоритет, то рассматриваемая операция просто проталкивается в стек.

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

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

Сначала мы рассмотрим простой пример перевода в обратную польскую запись с дальнейшем ее вычислением.
Пусть имеется следующее выражение записанное в простой скобочной записи ((5+6)/(5*3))^3.

текущий символ выходная строка содержимое стека
(   (
(   ( (
5 5 ( (
+ 5 + ( (
6 5 6 + ( (
) 5 6 + (
/ 5 6 + / (
( 5 6 + ( / (
5 5 6 + 5 ( / (
* 5 6 + 5 * ( / (
3 5 6 + 5 3 * ( / (
) 5 6 + 5 3 * / (
) 5 6 + 5 3 * / стек пуст
^ 5 6 + 5 3 * / ^
3 5 6 + 5 3 * / 3 ^
конец строки 5 6 + 5 3 * / 3 ^ стек пуст

Следует отметить что символ ( — открывающая скобка никакие операции из стека не выталкивает, а просто попадает в голову стека. После разбора первоначальной строки мы получили следующее выражение, записанное в формате ОПЗ: 5 6 + 5 3 * / 3 ^.

Теперь продемонстрирую принцип вычисления подобного выражения. Просматриваем строку слева направо, пока не встретится признак операции, в нашем случае это третий символ операция сложения. Так как операция сложения производится с двумя операндами, то предыдущие два элемента записис представляют собой два слагаемых, т.е. это 5 и 6. Таким образом вычисляем 5 + 6 = 11 и результат подставляем на место операции, и при этом удаляем элементы 5 и 6 которые участвовали в операции. Таким образом получаем следующую строку: 11 5 3 * / 3 ^. Следующая операция — это операция умножения *, берем предыдущие два элемента и перемножаем их (5 * 3 = 15) и результат операции подставляем на место операции а операнды удаляем. Теперь мы получили следующую строку: 11 15 / 3 ^. По аналогичному принципу производится деление (11/15 = 0.733) и замещается результатом. Строка свернулачь к следующему виду: 0.733 3 ^. И теперь производим операция возведения в степень (0.733^3=0.394) и также замещаем ее результатом, и получим строку : 0.394. Так как в строке больше операций не осталось, то это и будет результатом выражения. Вместо цифр можно использовать и неизвестные, только в момент вычисления их следует заменять на какие-либо числовые значения (таким образом можно строить графики функций).
В ближайшее время мы разберем написание компонента, который вычисляет выражения и с помощью него построим приложение, которое будет выводить графики введенный функций. А пока Вы можете сами попытаться реализовать алгоритм перевода в ОПЗ и вычисление выражения. Если у вас появиться оригинальное программное решение этой задачи присылайте мне его, если оно действительно будет интересно, то возможно будет рассмотренно именно ваше программное решение или его часть, естественно с указанием приславщего автора.

IF…THEN…

mailto: sia@itt.net.ru

Польская инверсная запись

 

Вместо традиционного инфиксного (скобочного) представления арифметических и логических выражений в различных вычислителях часто используется польская инверсная запись (ПОЛИЗ), которая просто и точно указывает порядок выполнения операций без использования скобок. В этой записи, впервые примененной польским математиком Я.Лукашевичем, операторы располагаются непосредственно за операндами над которыми они выполняются в порядке их выполнения. Поэтому иногда ПОЛИЗ называют суффиксной или постфиксной записью. Например, A+B записывается как AB+, A*B+C – как AB*C+, A*(B+C/D) – как ABCD/+*, а A*B+C*D – как AB*CD*+.

Остановимся на простейших правилах, которые позволяют переводить в ПОЛИЗ вручную:

1). Идентификаторы и константы в ПОЛИЗе следуют в том же порядке, что и в инфиксной записи.

2). Операторы в ПОЛИЗе следуют в том порядке, в каком они должны вычисляться (слева направо).

3). Операторы располагаются непосредственно за своими операндами.

Таким образом, мы могли бы записать следующие синтаксические правила:

<операнд>::=идентификаторôконстантаô<операнд><операнд><оператор>

<оператор>::=+ô-ô*ô/ô¼

Унарный минус и другие унарные операторы можно представить двумя способами: либо записывать их бинарными операторами, то есть вместо -B писать 0-B, либо для унарного минуса можно ввести новый специальный символ, например @, и использовать еще одно синтаксическое правило <:операнд>::=<операнд>@. Таким образом выражение A+(-B+C*D) мы могли бы записать AB@CD*++.

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

ПОЛИЗ расширяется достаточно просто. Нужно только придерживаться правила, что за операндами следует соответствующий им оператор. Так присваивание <переменная>:=<выражение> в ПОЛИЗе примет вид <переменная><выражение>:=. Например, присваивание А:=B*C+D*100 запишется в ПОЛИЗе как АBC*D100*+:=.

Индексированную переменную в ПОЛИЗе, а точнее вычисление ее адреса можно представить в виде:

идентификатор<индексные выражения>константа[ ,

где [ – обозначает знак операции вычисления индекса, идентификатор – имя (базовый адрес) индексированной переменной, а константа – количество индексов (мерность массива).

Так переменную A[i,j+k] можно представить в виде Аijk+2[ .

Условный оператор

IF <выр> THEN <инстр 1> ELSE <инстр 2>

в ПОЛИЗе будет иметь вид:

<выр> < m > УПЛ <инстр 1> < n > БП <инстр 2> , где

· <выр> – логическое выражение (условие), которое может принимать значения – 0 (FALSE, ложь) или 1 (TRUE, истина);

· < m > – номер (место, позиция, индекс) символа ПОЛИЗа, с которого начинается <инстр 2>;

· УПЛ (Условный Переход по Лжи) – оператор с двумя операндами <выр> и < m >, смысл которого состоит в том, что он изменяет традиционный порядок вычислений и осуществляет переход на символ строки ПОЛИЗа с номером < m >, если (и только если) <выр> – ложно (равно 0);

· < n > – номер символа, следующего за <инстр 2>;

· БП (Безусловный Переход) – оператор с одним операндом < n >, который также изменяет порядок вычислений по ПОЛИЗу и осуществляет переход на символ с номером < n >.

Операторы условного и безусловного перехода, как в свое время было показано Дейкстрой, составляют основу внутреннего представления любой структурной управляющей конструкции (циклов типа FOR, WHILE, REPEAT, оператора выбора и т.п.). В рассматриваемых нами примерах потребуется только один условный оператор – УПЛ, хотя никто не мешает определить целую группу таких операторов (смотри, например, мнемонику команды условного перехода языка ассемблера для ПЭВМ с процессором Intel 8086).

Пример 7.1.

В заключении раздела рассмотрим пример перевода в ПОЛИЗ фрагмента программы, включающего условный оператор:

IF (x<y) AND (a< >0) THEN b:=a+b*c ELSE b:=(a+b)*c; x:=a*b+c*d;

Ниже приведена строка ПОЛИЗа для этого оператора, где над символами указаны номера их позиций в полученной строке:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

xy< a 0 < > AND 19 УПЛ b a b c * + := 26 БП b a b + c * := x a b * c d * + :=

 

Интерпретация ПОЛИЗа

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

 

1).

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

Если сканируемый символ идентификатор или константа, то соответствующее им значение заносится в стек и осуществляется переход к следующему символу строки ПОЛИЗа. Это соответствует использованию правила <:операнд>::=идентификаторôконстанта

 

2). Если сканируемый символ унарный оператор, то он применяется к верхнему операнду в стеке, который затем заменяется на полученный результат. С точки зрения семантики это соответствует применению правила

<:операнд>::= <операнд><оператор>.

 

3). Если сканируемый символ бинарный арифметический или логический оператор, то он применяется к двум верхним операндам в стеке, и затем они заменяются на полученный результат. Это соответствует использованию правила <:операнд>::= <операнд><операнд><оператор>.

Одно из исключений – бинарный оператор присваивания, который в ПОЛИЗе имеет вид <пер><выр>:=. После его выполнения и <пер>, и <выр> должны быть исключены из стека, так как оператор ‘:=’ не имеет результирующего значения. При этом в стеке должно находится не значение <пер>, а ее адрес, так как значение <выр> должно сохраняться по адресу <пер>.

 

4). Бинарный оператор УПЛ, операндами которого является уже вычисленное значение логического выражения <выр> и номер символа строки ПОЛИЗа – <m>, также удаляет оба операнда из стека и не формирует в нем результата. Его действие состоит в том, что он анализирует значение выражения, и если оно равно 1 (истинно), то следующим сканируется символ, расположенный сразу за УПЛ. Если же значение выражения – 0 (ложно), то мы перемещаемся по строке ПОЛИЗа к символу, позиция которого указана в операнде <m>.

 

5). Унарный оператор БП, удаляя свой параметр, – номер символа < n > из стека, просто переводит сканирование к указанной позиции ПОЛИЗа.

 

Пример 7.2.

 

На рис. 7.1 показан пример интерпретации строки ПОЛИЗа AB@CD*++ , полученной из инфиксного выражения A+(-B+C*D). Значения в стеке отделены друг от друга вертикальной чертой.

 

 


На главную

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

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

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

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

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

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

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

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

Рассмотрим алгоритм на примере простейшего выражения:
Дано выражение:
a + ( b — c ) * d

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

Символ Действие Состояние выходной строки после совершенного действия Состояние стека после совершенного действия
a ‘a’ — переменная. Помещаем ее в выходную строку a пуст
+ ‘+’ — знак операции. Помещаем его в стек (поскольку стек пуст, приоритеты можно не проверять) a +
( ‘(‘ — открывающая скобка. Помещаем в стек. a + (
b ‘b’ — переменная. Помещаем ее в выходную строку a b + (
‘-‘ — знак операции, который имеет приоритет 2. Проверяем стек: на вершине находится символ ‘(‘, приоритет которого равен 1. Следовательно мы должны просто поместить текущий символ ‘-‘ в стек. a b + ( —
c ‘c’ — переменная. Помещаем ее в выходную строку a b c + ( —
) ‘)’ — закрывающая скобка. Извлекаем из стека в выходную строку все символы, пока не встретим открывающую скобку. Затем уничтожаем обе скобки. a b c — +
* ‘*’ — знак операции, который имеет приоритет 3. Проверяем стек: на вершине находится символ ‘+’, приоритет которого равен 2, т.е. меньший, чем приоритет текущего символа ‘*’. Следовательно мы должны просто поместить текущий символ ‘*’ в стек. a b c — + *
d ‘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 character
inline char TStr2PPN::nextChar() {
if(iin <= instr.Length()) return curc = instr[iin++];
return curc = ‘\0’;
}

//get the output string
inline AnsiString TStr2PPN::get_outstr(){return outstr;}

//convert to PPN
void TStr2PPN::convert(char *str) {
try {
instr = str;
outstr.SetLength(0);
iin = 1;
nextChar();
//begin the convertation
begin();
if(iin != (instr.Length()+1) || curc != ‘\0’) {
throw Exception(«Syntax error»);
}
if(!isalpha(instr[instr.Length()]) && instr[instr.Length()]!=’)’) {
throw Exception(«Syntax error»);
}
}
catch(…) {throw;}
}

//handle plus & minus
void TStr2PPN::begin() {
try {
mult_div();
while(curc==’+’ || curc==’-‘) {
char temp = curc;
nextChar();
mult_div();
outstr += temp;
}
}
catch(…) {throw;}
}

//handle multiplication & division
void TStr2PPN::mult_div() {
try {
symbol();
while(curc==’*’ || curc==’/’) {
char temp = curc;
nextChar();
symbol();
outstr += temp;
}
}
catch(…) {throw;}
}

//handle characters
void TStr2PPN::symbol() {
try {
if(curc=='(‘) {
nextChar();
begin();
if(curc!=’)’) {
throw Exception(«Error: wrong number of brackets»);
}
else nextChar();
}
else
if(isalpha(curc)) {
outstr += curc;
nextChar();
}
else {throw Exception(«Syntax error»);}
}
catch(…) {throw;}
}

Скачать реализацию на С++

3. Алгоритм вычисления выражения, записанного в ОПЗ
Для реализации этого алгоритма используется стек для чисел (или для переменных, если они встречаются в исходном выражении). Алгоритм очень прост. В качестве входной строки мы теперь рассматриваем выражение, записанное в ОПЗ:
1. Если очередной символ входной строки — число, то кладем его в стек.
2. Если очередной символ — знак операции, то извлекаем из стека два верхних числа, используем их в качестве операндов для этой операции, затем кладем результат обратно в стек.
Когда вся входная строка будет разобрана в стеке должно остаться одно число, которое и будет результатом данного выражения.

Рассмотрим этот алгоритм на примере выражения:
7 5 2 — 4 * +

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

Символ Действие Состояние стека после совершенного действия
7 ‘7’ — число. Помещаем его в стек. 7
5 ‘5’ — число. Помещаем его в стек. 7 5
2 ‘2’ — число. Помещаем его в стек. 7 5 2
‘-‘ — знак операции. Извлекаем из стека 2 верхних числа ( 5 и 2 ) и совершаем операцию 5 — 2 = 3, результат которой помещаем в стек 7 3
4 ‘4’ — число. Помещаем его в стек. 7 3 4
* ‘*’ — знак операции. Извлекаем из стека 2 верхних числа ( 3 и 4 ) и совершаем операцию 3 * 4 = 12, результат которой помещаем в стек 7 12
+ ‘+’ — знак операции. Извлекаем из стека 2 верхних числа ( 7 и 12 ) и совершаем операцию 7 + 12 = 19, результат которой помещаем в стек 19

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

Реализация на С++:

int calculate(string str_in) {
Stack<int> val_stack; //стек
int n1, n2, res;

for(i = 0; i<str_in.length(); ++i) {
if(isNumber(str_out[i])) {
val_stack.push(str_out[i]);
}
else {
n2 = val_stack.pop();
n1 = val_stack.pop();
switch(str_out[i]) {
case ‘+’: res = n1 + n2; break;
case ‘-‘: res = n1 — n2; break;
case ‘*’: res = n1 * n2; break;
case ‘/’: res = n1 / n2; break;
default: cout<<«Ошибка !\n»;
}
val_stack.push(res);
}
}
return val_stack.pop();
}

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

На главную

Хостинг от uCoz

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*