2015-04-08
3922
Для преобразования скобочных выражений воспользуемся способом голландского ученого Дикстры. Его метод основан на использовании стека с приоритетами, позволяющего изменить порядок следования знаков операций в выражении так, что получается обратная польская запись. Простейший вариант этого метода применим только к простым арифметическим и логическим выражениям, содержащим переменные, знаки арифметических и логических операций, знаки операций отношения и круглые скобки. Каждому символу, входящему в выражение, присваивается приоритет, приведенный в таблице ниже.
Арифметическое или логическое выражение рассматривается как входная строка символов. Операнды переписываются в выходную строку, а знаки операций помещаются сначала в стек операций. Если приоритет входного знака равен нулю или больше приоритета знака, находящегося в вершине стека, то новый знак добавляется к вершине стека. В противном случае из стека «выталкивается» и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами, большими или равными приоритету входного знака. После этого входной знак добавляется к вершине стека. Особенности имеет лишь обработка скобок. Открывающая круглая скобка, имеющая приоритет нуль, записывается в вершину стека и не выталкивает ни одного знака. В то же время ее не может вытолкнуть ни один знак, кроме закрывающей скобки. Ее появление вызывает выталкивание всех знаков до ближайшей открывающей скобки включительно. Скобки взаимно уничтожаются и в выходную строку не переносятся. По завершении просмотра всех символов входной строки происходит выталкивание оставшихся в стеке символов и добавление их к выходной строке.
Ниже приведены два примера преобразования инфиксных выражений в обратные польские.
Пример 1.
Пример 2.
Алгоритм преобразования выражения из инфиксной формы в префиксную запись рассмотрим на примере выражения a+b/(c-d).
1. Необходимо переписать выражение справа налево: (d-c)/b+a;
2. Воспользовавшись алгоритмом постфиксной трансляции, получим: dc-b/a+;
3. Полученную строку требуется записать справа налево, в результате чего получается выражение в префиксном виде: +a/b-cd.
