Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
8. Q = {4} и W={}
и ещё непонятен момент
добавить в качестве второго операнда единицу (нейтральный элемент)
Вы имели в виду ноль?
Кстати интересный метод, хотя для меня наверное все интересные, ибо я не программист =)
добавить в качестве второго операнда единицу (нейтральный элемент)
Вы имели в виду ноль?
Кстати интересный метод, хотя для меня наверное все интересные, ибо я не программист =)
В общем да — я имел в виду ноль.
но ноль только в операциях + и — в операциях * и / вместо нуля будет единица.
в математике, Единица (Нейтральный элемент бинарной операции) — элемент, который оставляет любой другой элемент неизменным при применении этой бинарной операции к этим двум элементам
поэтому то я и выделил единицу курсивом :)
к примеру, для операции «запятая» я делал единицей — null
(2,,, 4) = {2, null, null, 4}
но ноль только в операциях + и — в операциях * и / вместо нуля будет единица.
в математике, Единица (Нейтральный элемент бинарной операции) — элемент, который оставляет любой другой элемент неизменным при применении этой бинарной операции к этим двум элементам
поэтому то я и выделил единицу курсивом :)
к примеру, для операции «запятая» я делал единицей — null
(2,,, 4) = {2, null, null, 4}
>>Если пост понравился, в следующем напишу о том, как я делал небольшой функциональный язык и объектно-ориентированный язык.
Понравился пишите!!!
Понравился пишите!!!
Я уже вас моментально выделяю из всех пользователей без юзерпика по наличию трех восклицательных знаков.
>>Если пост понравился, в следующем напишу о том, как я делал небольшой функциональный язык и объектно-ориентированный язык.
Эх на пару месяцов бы раньше и не пришлось бы самому долго разбираться в этом алгоритме…
А про то как написать собственный компилятор для собственного функционального языка есть хорошая книга «Алгоритмы, языки, автоматы» Максима Мозгового.
Baks, интересно посмотреть вашу версию.
Эх на пару месяцов бы раньше и не пришлось бы самому долго разбираться в этом алгоритме…
А про то как написать собственный компилятор для собственного функционального языка есть хорошая книга «Алгоритмы, языки, автоматы» Максима Мозгового.
Baks, интересно посмотреть вашу версию.
Присоединяюсь к прозьбе. Обязательно пишите.
Подобные примеры знаю, но они основаны на рекурсии.
Ваш метод вычисления выражений так же мне знаком по старому журналу Квант. Хотя конечно это алгоритм Дейкстры.
В общем — Приятно перечитывать классику в новом исполнении.
Подобные примеры знаю, но они основаны на рекурсии.
Ваш метод вычисления выражений так же мне знаком по старому журналу Квант. Хотя конечно это алгоритм Дейкстры.
В общем — Приятно перечитывать классику в новом исполнении.
«Классика» — это алгоритм Дейкстры, который использует таки один стэк — операторов.
А операнды складываются в «выходную строку» вместе со знаками.
Потомучто, в частности, с переменными, сразу результат может не вычисляться, но транслироваться в какое-нибудь лямбда-выражение.
Ну и приоритет вроде обычно считается большим у тех операторов, чьё связывание операндов раньше. Тоесть у "*" приоритет выше чем у "+".
Хотя и обозначается традиционно меньшим числом.
А операнды складываются в «выходную строку» вместе со знаками.
Потомучто, в частности, с переменными, сразу результат может не вычисляться, но транслироваться в какое-нибудь лямбда-выражение.
Ну и приоритет вроде обычно считается большим у тех операторов, чьё связывание операндов раньше. Тоесть у "*" приоритет выше чем у "+".
Хотя и обозначается традиционно меньшим числом.
> Суть метода 2х стеков (наверняка у него есть красивое научное название.)
Да, судя по всему, это вариант алгоритма Дейкстры «сортировочная станция» Преобразование из инфиксной нотации
Да, судя по всему, это вариант алгоритма Дейкстры «сортировочная станция» Преобразование из инфиксной нотации
2qmax, 2elw00d в общем это один и тот де алгоритм, только с немного разными реализациями… основной это, разумеется алгоритм Дейкстры
вместо стека операндов я иногда использую «выходную строку» или строю дерево. в зависимости от назначения алгоритма. :)
вместо стека операндов я иногда использую «выходную строку» или строю дерево. в зависимости от назначения алгоритма. :)
а с унарными операциями в чем проблема? они тоже имеют приоритет. по логике алгоритма очень большой. ввести у оператора параметр арность и брать из стека нужное количество операндов.
а зачем такие танцы с бубном, когда эта проблема решается одной строчкой :)
все n-арные операторы легко разруливаются бинарными и унарными операциями над списками.
все n-арные операторы легко разруливаются бинарными и унарными операциями над списками.
Ну тут хороший вопрос — в каком случае это является танцами с бубнами. Помнится писал задачу в которой было много операцийс различной арностью, и 2 и 1 и 3 ;) И по моему введения для операции арность (раз уж у нее есть приоритет) гораздо легче, чем вставки для каждой операции «строчек» с приведением ее к чему либо другому.
Уверен, что на хабре нашлись на те, кому этот алгоритм был интересен. Собственно для них я и писал.
В нем нет ничего нового, но далеко не все про него знают.
Я его знаю класса с 9ого. Удивлен, что ты его только на 3ем курсе асилил :)
Я думаю, чем новости с ЛенИздат постить, лучше уж попытаться объяснить интересный алгоритм, авось кому и пригодится. Ведь так? :)
В нем нет ничего нового, но далеко не все про него знают.
Я его знаю класса с 9ого. Удивлен, что ты его только на 3ем курсе асилил :)
Я думаю, чем новости с ЛенИздат постить, лучше уж попытаться объяснить интересный алгоритм, авось кому и пригодится. Ведь так? :)
Хм… а это идея :)
Сделать цикл статей о доказательствах теорем, которые мы со школьных лет считаем аксиомами.
Все знают, что квадрат гипотенузы равен сумме квадратов катетов. Но, уверен, не все сходу доказать хотя бы одно из нескольких сотен доказательств.
Разумеется, этот материал есть в википедии и сотнях других источниках, но раз уж мы новости с других сайтов копируем – давайте будем писать о чем-то давно забытом, но не менее интересном :)
Народ же пишет для начинающих про языки программирования :) новичкам это нужно и важно, а нам (тем кто знает) тоже не помешает прочитать и, может быть, что-то интересное вспомнить или по-другому взглянуть на то, что всегда знал.
Сделать цикл статей о доказательствах теорем, которые мы со школьных лет считаем аксиомами.
Все знают, что квадрат гипотенузы равен сумме квадратов катетов. Но, уверен, не все сходу доказать хотя бы одно из нескольких сотен доказательств.
Разумеется, этот материал есть в википедии и сотнях других источниках, но раз уж мы новости с других сайтов копируем – давайте будем писать о чем-то давно забытом, но не менее интересном :)
Народ же пишет для начинающих про языки программирования :) новичкам это нужно и важно, а нам (тем кто знает) тоже не помешает прочитать и, может быть, что-то интересное вспомнить или по-другому взглянуть на то, что всегда знал.
Пара вопросов автору:
1) у вас в первом примере, который
в 6-м шаге сказано:
но ведь в W у нас храняться операторы (не цифры), какой тогда смысл в A — B (или я чего-то недопонял)?
2) Во 2-м примере, шаг 8 наверно должно быть W.push( ) )?
P.S. Я не программер, но для меня подобные статьи очень даже интересны, для расширения кругозора, например ))
1) у вас в первом примере, который
Простой пример:
2 + 2 * 3 — 4
в 6-м шаге сказано:
B < — W.pop()
A < — W.pop()
Q.push(A — B)
но ведь в W у нас храняться операторы (не цифры), какой тогда смысл в A — B (или я чего-то недопонял)?
2) Во 2-м примере, шаг 8 наверно должно быть W.push( ) )?
P.S. Я не программер, но для меня подобные статьи очень даже интересны, для расширения кругозора, например ))
Проблема в том, что код со стеком трудно распаралеливается суперскалярными процессорами.
Лучше «компилировать» формулу в «линейный вид», с несколькими виртуальными переменными.
Лучше «компилировать» формулу в «линейный вид», с несколькими виртуальными переменными.
Здравствуйте!
Вы просили меня прокомментировать с удовольствием.
Во-первых, спасибо за статью! Она лучше многих, я действительно так думаю, хотя вещи, которые я сейчас напишу могут вам не понравиться :-)
К делу.
Прежде всего, я бы советовал вам, почитать что-нибудь про грамматики. Тогда вместо наивных фраз любое сложно выражение (кстати, опечатка), вы могли бы написать грамматика класса LL(1) или что-то в этом духе. Когда вы говорите о разборе выражения, уместно классифицировать его грамматику, иначе звучит диковато и безграмотно (есть выражения, за разбор которых вы получите большие премии от видных математических обществ. есть выражения, которые невозможно разобрать и это доказано).
Далее. Зачем два стека? Вы же точно знаете, как чередуются операции и операнды! Чтобы соблюсти это чередование вы даже добавляете 0 к унарным операциям. Всё можно было бы положить в один стек.
О работе работе со стеком. Ваш алгоритм заставляет вас работать не только с верхушкой стека. Это дополнительное усложнение и источник ошибок. (Кстати, судя по обсуждению, вы не смогли избежать ошибок. А я вас предупреждал об это ещё до публикации этого поста. Работа со стеком требует большой аккуратности)
А теперь вспомним как работает алгоритм рекурсивного спуска. Вспомним, что локальные переменные хранятся в стеке. И что мы видим? Тот же стек, но! 1) он один 2) алгоритм не требует (и даже не позволяет) заглядывать под вершину стека 3) нет никаких проблем с унарными операторами и более сложными грамматиками 4) и самое главное нет необходимости работать со стеком руками! ошибки просто невозможны.
Мне кажется, вы здесь сформулировали тот же алгоритм рекурсивного спуска но, развернули рекурсию и написали работу со стеком вручную, разделили стек на два (видимо интуитивно, вы отделили терминальные токены в один стек, а не-терминальные в другой, но в этом нет никакой необходимости) и добавили костыли в виде переформулирования унарных операций, чтобы сделать разбираемый случай ещё более частным.
Если бы вы использовали рекурсивный спуск, вы застраховались бы от многих ошибок и получили бы универсальный парсер, в который можно было бы легко встроить, скажем, функции или операции с тремя операндами (типа А?B:C). В ваш теперешний парсер встроить такие возможности очень сложно (можно ли вообще). И править его очень опасно, так как тронув стек в одном месте, надо отследить, чтобы всё не посыпалось в другом.
Одним словом, ваш алгоритм я бы не стал использовать сам и не стал бы советовать другим.
Вы просили меня прокомментировать с удовольствием.
Во-первых, спасибо за статью! Она лучше многих, я действительно так думаю, хотя вещи, которые я сейчас напишу могут вам не понравиться :-)
К делу.
Прежде всего, я бы советовал вам, почитать что-нибудь про грамматики. Тогда вместо наивных фраз любое сложно выражение (кстати, опечатка), вы могли бы написать грамматика класса LL(1) или что-то в этом духе. Когда вы говорите о разборе выражения, уместно классифицировать его грамматику, иначе звучит диковато и безграмотно (есть выражения, за разбор которых вы получите большие премии от видных математических обществ. есть выражения, которые невозможно разобрать и это доказано).
Далее. Зачем два стека? Вы же точно знаете, как чередуются операции и операнды! Чтобы соблюсти это чередование вы даже добавляете 0 к унарным операциям. Всё можно было бы положить в один стек.
О работе работе со стеком. Ваш алгоритм заставляет вас работать не только с верхушкой стека. Это дополнительное усложнение и источник ошибок. (Кстати, судя по обсуждению, вы не смогли избежать ошибок. А я вас предупреждал об это ещё до публикации этого поста. Работа со стеком требует большой аккуратности)
А теперь вспомним как работает алгоритм рекурсивного спуска. Вспомним, что локальные переменные хранятся в стеке. И что мы видим? Тот же стек, но! 1) он один 2) алгоритм не требует (и даже не позволяет) заглядывать под вершину стека 3) нет никаких проблем с унарными операторами и более сложными грамматиками 4) и самое главное нет необходимости работать со стеком руками! ошибки просто невозможны.
Мне кажется, вы здесь сформулировали тот же алгоритм рекурсивного спуска но, развернули рекурсию и написали работу со стеком вручную, разделили стек на два (видимо интуитивно, вы отделили терминальные токены в один стек, а не-терминальные в другой, но в этом нет никакой необходимости) и добавили костыли в виде переформулирования унарных операций, чтобы сделать разбираемый случай ещё более частным.
Если бы вы использовали рекурсивный спуск, вы застраховались бы от многих ошибок и получили бы универсальный парсер, в который можно было бы легко встроить, скажем, функции или операции с тремя операндами (типа А?B:C). В ваш теперешний парсер встроить такие возможности очень сложно (можно ли вообще). И править его очень опасно, так как тронув стек в одном месте, надо отследить, чтобы всё не посыпалось в другом.
Одним словом, ваш алгоритм я бы не стал использовать сам и не стал бы советовать другим.
PS
странно запостилось — пропали все тире и кавычки :-/
но, вроде, и так всё понятно.
странно запостилось — пропали все тире и кавычки :-/
но, вроде, и так всё понятно.
Фуф… написал вам большой гневный комментарий с указанием на ваши ошибки… но потом зашёл на michurin.com.ru/ и понял, что спорить с вам в принципе бесполезно…
Я понимаю, что вы меня старше на 11 лет и когда вы во всю уже работали я даже ещё и комп то в глаза не видел… но… вы не программист в полном смысле этого слова. Вы просто очень хороший системный администратор. :)
Вы даже не понимаете что Stack и, так называемый, стек локальных переменных это 2 совершенно разные вещи…
Предлагаю избавить хабрапользователей от нашей беседы и, если вы всё-таки считаете, что я не прав – писать мне в личку, icq или скайп
Я понимаю, что вы меня старше на 11 лет и когда вы во всю уже работали я даже ещё и комп то в глаза не видел… но… вы не программист в полном смысле этого слова. Вы просто очень хороший системный администратор. :)
Вы даже не понимаете что Stack и, так называемый, стек локальных переменных это 2 совершенно разные вещи…
Предлагаю избавить хабрапользователей от нашей беседы и, если вы всё-таки считаете, что я не прав – писать мне в личку, icq или скайп
это «разные вещи», которые работают одинаково (возможно поэтому они и называются одинаково :-)); и именно на этом я и предлагаю сыграть :-)
И всё же… я вам очень советую не читать мои комменты, не читать мои странички,… а почитать хорошие книжки; можно начать с этой ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf (есть более новая версия этой книги, но я что-то не смог её нагуглить). Я вижу, как вам нравится эта тема. Поверьте! Чтение этой (и других) книжки доставит вам на много больше удовольствия, чем попытки меня в чём-то убедить! Удачи!
И всё же… я вам очень советую не читать мои комменты, не читать мои странички,… а почитать хорошие книжки; можно начать с этой ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf (есть более новая версия этой книги, но я что-то не смог её нагуглить). Я вижу, как вам нравится эта тема. Поверьте! Чтение этой (и других) книжки доставит вам на много больше удовольствия, чем попытки меня в чём-то убедить! Удачи!
не… 2 стека всё равно круче :)
и открою вам секрет — в одной из моих программ (IVROS) я двумя стеками строю дерево ;)
З.Ы. сейчас IVROS используется более чем в 30 банках и налоговых по Оренбургской области.
и открою вам секрет — в одной из моих программ (IVROS) я двумя стеками строю дерево ;)
З.Ы. сейчас IVROS используется более чем в 30 банках и налоговых по Оренбургской области.
W.Push(-)
у – приоритет выше чем у *, а значит, мы вытолкнем *. Для этого мы возьмём 2 последних операнда а на их место поставим результат операции A-B.
B < — Q.pop()
A < — Q.pop()
Q.push(A — B)
Я вот одного не могу понять, почему A-B? Мы же умножаем, т.е. получается что мы берем 2 и 3 и вычитаем, когда должны умножить.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вычисление значения выражения