Вычисление значения выражения

8. Q = {4} и W={}

>>Если пост понравился, в следующем напишу о том, как я делал небольшой функциональный язык и объектно-ориентированный язык.

Понравился пишите!!!

«Классика» — это алгоритм Дейкстры, который использует таки один стэк — операторов.
А операнды складываются в «выходную строку» вместе со знаками.
Потомучто, в частности, с переменными, сразу результат может не вычисляться, но транслироваться в какое-нибудь лямбда-выражение.

Ну и приоритет вроде обычно считается большим у тех операторов, чьё связывание операндов раньше. Тоесть у "*" приоритет выше чем у "+".
Хотя и обозначается традиционно меньшим числом.

> Суть метода 2х стеков (наверняка у него есть красивое научное название.)
Да, судя по всему, это вариант алгоритма Дейкстры «сортировочная станция» Преобразование из инфиксной нотации

2qmax, 2elw00d в общем это один и тот де алгоритм, только с немного разными реализациями… основной это, разумеется алгоритм Дейкстры

вместо стека операндов я иногда использую «выходную строку» или строю дерево. в зависимости от назначения алгоритма. :)

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

Пара вопросов автору:
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). В ваш теперешний парсер встроить такие возможности очень сложно (можно ли вообще). И править его очень опасно, так как тронув стек в одном месте, надо отследить, чтобы всё не посыпалось в другом.

Одним словом, ваш алгоритм я бы не стал использовать сам и не стал бы советовать другим.

W.Push(-)
у – приоритет выше чем у *, а значит, мы вытолкнем *. Для этого мы возьмём 2 последних операнда а на их место поставим результат операции A-B.
B < — Q.pop()
A < — Q.pop()
Q.push(A — B)

Я вот одного не могу понять, почему A-B? Мы же умножаем, т.е. получается что мы берем 2 и 3 и вычитаем, когда должны умножить.