Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Перевод из инфексной нотации в постфиксную

Автор: sidd 6.11.2010, 15:08

Вот это алгоритм из Википедии: Цитата     * Пока есть ещё символы для чтения:             * Читаем очередной символ.             * Если символ является числом, добавить его к выходной строке.             * Если символ является символом функции, помещаем его в стек.             * Если символ является открывающей скобкой, помещаем его в стек.             * Если символ является закрывающей скобкой:                 До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в выходную строку. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.             * Если символ является оператором о1, тогда:         1) пока…                 … (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…                 … (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…         … выталкиваем верхние элементы стека в выходную строку;         2) помещаем оператор o1 в стек.     * Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку. В стеке должны были остаться только символы операторов; если это не так, значит в выражении не согласованы скобки. Но я не могу понять, что такое символ функции и оператор o1. Я сначала думал, что символ функции — это просто оператор. Но тогда чем от обычных операторов отличается o1? Объясните, пожалуйста.

Автор: Pavia 6.11.2010, 19:40

sidd,  exp это три символа. exp, not, rand это функции. Для применения автомата введем новый набор символов. Где каждую функцию обозначим своим символом.  К примеру exp-"e", not-"n",rand- "r" Весь наш алфавит состоит из "0","1","2","3","4","5","6","7","8","9","+","-","*","e","n","r".  Зачем это нужно? Да просто по тому что магазинный автомат работает с алфавитом. Так проще понимать. Даже более того все числа которые есть в строке по хорошему надо представить как некоторый символ. Вопрос чем функция отличается от оператора? Функция всегда имеет наивысший приоритет и является право ассоциативной. Тогда она всегда помещается в стек.  Так как нет наиболее высшего оператора. Другими словами для функции условие  Цитата  * Если символ является оператором о1, тогда:         1) пока…                 … (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…                 … (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…         … выталкиваем верхние элементы стека в выходную строку; никогда не выполняется. Остается самое главное отличие функции от оператора. После функции всегда идут скобки. Почему оператор тут называется O1 ? Трудно сказать просто это списано из какой то книжке. Скорее всего индекс 1 . Взялся из грамматике. Все операторы у нас имеют по 1 символу поэтому в рассмотрении и участвует один символ O1 где 1 индекс.  Советую википедию не читать, а читать умные книжки. Вот тут не плохо описано.  http://www.intuit.ru/department/sa/compilersdev/ 1)Начни с Формальной грамматики.  2)Дальше перейди к конечным автоматом.   3)После автомат с магазинной памятью. Тут собственно и будет обратная польская нотация. Советую о функциях забыть и рассматривать польскую нотацию как метод избавления от скобок.  Грамматика очень проста. E="("E")"|число E=E"+"E |E"-"E|E"*"E| E"/"E Основное что тут надо уловить это приоритет операций и построение по грамматике автомата.  Понять почему запись выше может интерпретироваться по разному. И как от этого избавится. Доказать возможность построение автомата с магазинной память. Основной подход для построения автомата это рассмотреть все множество состояний в этом языке. Для этого существует множество подходов LL и RL. Но тут для наглядности лучше ручками разобрать. Понять что возможных состояний автомата может быть много и очень много. Тут не плохо бы знать динамическое программирование.  Оно поможет легко и просто построить автомат.

Автор: sidd 7.11.2010, 14:47

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)