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

    В продолжение поста Компилятор выражений. По просьбам читающих. Специально для michurin

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

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

    Мы будем идти слева на право, добавляя операнды в один стек, а операции в другой. При каждом добавлении новой операции мы будем пытаться вытолкнуть из стека старые, руководствуясь приоритетами операций. (важно заметить, что тут как раз — таки и можно извратиться и сделать всё в 1 стеке, но мы будем придерживаться классики)

    Так как слова Operator и Operand очень похожи, то вместо Operator мы будем использовать Function.
    Стек Операндов будет называться Q
    Стек Операторов W

    Простой пример:
    2 + 2 * 3 — 4
    1. Q.Push(2) Добавляем в стек Q операнд 2
    2. W.Push(+) Добавляем в стек W операцию +
    3. Q.Push(2)
    4. W.Push(*). Сейчас в W у нас находятся операции + и *. Так как у + приоритет выше, то * не может вытолкнуть его из стека.
    5. Q.Push(3)
    6. W.Push(-)
      у – приоритет выше чем у *, а значит, мы вытолкнем *. Для этого мы возьмём 2 последних операнда а на их место поставим результат операции A-B.
      B <- Q.pop()
      A <- Q.pop()
      Q.push(A - B)
      так мы будем повторять пока не наткнемся на операцию, которую не сможем вытолкнуть.
    7. В итоге у нас останется Q = {8, 4} и W={-}
      обычно, чтобы не разругивать последний шаг, всё выражение берется в скобки и последняя скобка выталкивает все оставшиеся операции.
    8. Q = {4} и W={}

    Для примера возьмем операции + — * / и взятие в скобки.
    у * и / приоритет будет равен 1
    у + и – будет равен 2
    у открывающейся скобки приоритет -1 и она никого не выталкивает.
    Закрывающаяся скобка выталкивает все операции до первой открывающейся.

    Пример: 2 + 1 – 6 / (1 + 2)
    Рассмотрим пример по шагам:
    1. Q.push(2)
      Q = {2}
      W = { }
    2. W.push(+)
      Q = {2}
      W = {+}
    3. Q.push(1)
      Q = {2, 1}
      W = {+}
    4. W.push(-)
      у операций + и – приоритет равный, следовательно выталкиваем +
      Q = {3}
      W = {-}
    5. Q.push(6)
      Q = {3, 6}
      W = {-}
    6. W.push( / )
      Q = {3, 6}
      W = {-, /}
    7. W.push( ( )
      открывающаяся скобка никого не выталкивает, а просто добавляет себя в стек операций
      Q = {3, 6}
      W = {-, /, (}
    8. Q.push(1)
      Q = {3, 6, 1}
      W = {-, /, (}
    9. W.push(+)
      открывающуюся скобку может вытолкнуть только закрывающаяся. ничего не делаем.
      Q = {3, 6, 1}
      W = {-, /, (, +}
    10. Q.push(2)
      Q = {3, 6, 1, 2}
      W = {-, /, (, +}
    11. W.push( ) )
      Закрывающаяся скобка выталкивает все операции до первой открывающейся
      такая операция почти всегда одна (зависит от реализации)
      Q = {3, 6, 3}
      W = {-, /}
    12. Вот на этом шаге мы или сами разруливаем концовку или изначально оборачиваем выражение в круглые скобки, чтобы вытолкнуть все оставшиеся операции
      Q = {3, 2, 3}
      W = {-, /}
    13. Q = {1}
      W = {}
      результатом будет последнее число в стеке. Если там больше чем 1 число – значит, мы неправильно написали алгоритм или получили на вход кривое выражение.

    Чтобы не заморачиваться с унарными операциями мы воспользуемся тем, что любую унарную можно превратить в бинарную. к примеру, добавить в качестве второго операнда единицу (нейтральный элемент)
    т.е. вместо (-2) у нас будет (0 – 2)

    Алгоритм на С#:

    public static double Calc(string s)
    {
        s = '(' + s + ')';
        Stack<double> Operands = new Stack<double>();
        Stack<char> Functions = new Stack<char>();
        int pos = 0;
        object token;
        object prevToken = 'Ы';

        do
        {
            token = getToken(s, ref pos);
            // разрливаем унарный + и -
            if (token is char && prevToken is char &&
                // если эту сточку заменить на (char)prevToken != ')' &&
                // то можно будет писать (2 * -5) или даже (2 - -4)
                // но нужно будет ввести ещё одну проверку так, как запись 2 + -+-+-+2 тоже будет работать :)
                (char)prevToken == '(' &&
                ((char)token == '+' || (char)token == '-'))
                Operands.Push(0); // Добавляем нулевой элемент

            if (token is double) // Если операнд
            {
                Operands.Push((double)token); // то просто кидаем в стек
            }
            // в данном случае у нас только числа и операции. но можно добавить функции, переменные и т.д. и т.п.
            else if (token is char) // Если операция
            {
                if ((char)token == ')')
                {
                    // Скобка - исключение из правил. выталкивает все операции до первой открывающейся
                    while (Functions.Count > 0 && Functions.Peek() != '(')
                        popFunction(Operands, Functions);
                    Functions.Pop(); // Удаляем саму скобку "("
                }
                else
                {
                    while (canPop((char)token, Functions)) // Если можно вытолкнуть
                        popFunction(Operands, Functions); // то выталкиваем

                    Functions.Push((char)token); // Кидаем новую операцию в стек
                }
            }
            prevToken = token;
        }
        while (token != null);

        if (Operands.Count > 1 || Functions.Count > 0)
            throw new Exception("Ошибка в разборе выражения");

        return Operands.Pop();
    }

    private static void popFunction(Stack<double> Operands, Stack<char> Functions)
    {
        double B = Operands.Pop();
        double A = Operands.Pop();
        switch (Functions.Pop())
        {
            case '+': Operands.Push(A + B);
                break;
            case '-': Operands.Push(A - B);
                break;
            case '*': Operands.Push(A * B);
                break;
            case '/': Operands.Push(A / B);
                break;
        }
    }

    private static bool canPop(char op1, Stack<char> Functions)
    {
        if (Functions.Count == 0)
            return false;
        int p1 = getPriority(op1);
        int p2 = getPriority(Functions.Peek());

        return p1 >= 0 && p2 >= 0 && p1 >= p2;
    }

    private static int getPriority(char op)
    {
        switch (op)
        {
            case '(':
                return -1; // не выталкивает сам и не дает вытолкнуть себя другим
            case '*': case '/':
                return 1;
            case '+': case '-':
                return 2;
            default:
                throw new Exception("недопустимая операция");
        }
    }

    private static object getToken(string s, ref int pos)
    {
        readWhiteSpace(s, ref pos);

        if (pos == s.Length) // конец строки
            return null;
        if (char.IsDigit(s[pos]))
            return Convert.ToDouble(readDouble(s, ref pos));
        else
            return readFunction(s, ref pos);
    }

    private static char readFunction(string s, ref int pos)
    {
        // в данном случае все операции состоят из одного символа
        // но мы можем усложнить код добавив == && || mod div и ещё чегонить
        return s[pos++];
    }

    private static string readDouble(string s, ref int pos)
    {
        string res = "";
        while (pos < s.Length && (char.IsDigit(s[pos]) || s[pos] == '.'))
            res += s[pos++];

        return res;
    }

    // Считывает все проблемы и прочие левые символы.
    private static void readWhiteSpace(string s, ref int pos)
    {
        while (pos < s.Length && char.IsWhiteSpace(s[pos]))
            pos++;
    }


    * This source code was highlighted with Source Code Highlighter.


    Это элементарный пример, который поддерживает всего 4 операции. Но его очень легко дополнить операциями && || ^ & | div mod просто задав им приоритет и написав реализацию.

    Можно добавить переменные. Этим же алгоритмом можно строить и деревья. При том, деревья будут максимально вычисленные. т.е постоянные ветки (не содержащие переменных) можно будет вычисляться заранее.

    Очень легко добавляется оператор запятая.
    (2, 4 + 5, 4) превратится в массив {2, 9, 4}

    Функции F(x1, x2, …, xn) это унарная операция над массивом {x1, x2, …, xn}

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

    Comments 36

      0
      8. Q = {4} и W={}
        0
        и ещё непонятен момент
        добавить в качестве второго операнда единицу (нейтральный элемент)
        Вы имели в виду ноль?

        Кстати интересный метод, хотя для меня наверное все интересные, ибо я не программист =)
          +3
          В общем да — я имел в виду ноль.
          но ноль только в операциях + и — в операциях * и / вместо нуля будет единица.

          в математике, Единица (Нейтральный элемент бинарной операции) — элемент, который оставляет любой другой элемент неизменным при применении этой бинарной операции к этим двум элементам

          поэтому то я и выделил единицу курсивом :)

          к примеру, для операции «запятая» я делал единицей — null
          (2,,, 4) = {2, null, null, 4}
            0
            Спасибо что просветили =)
        +1
        >>Если пост понравился, в следующем напишу о том, как я делал небольшой функциональный язык и объектно-ориентированный язык.

        Понравился пишите!!!
          +1
          Я уже вас моментально выделяю из всех пользователей без юзерпика по наличию трех восклицательных знаков.
            0
            >>Если пост понравился, в следующем напишу о том, как я делал небольшой функциональный язык и объектно-ориентированный язык.
            Эх на пару месяцов бы раньше и не пришлось бы самому долго разбираться в этом алгоритме…

            А про то как написать собственный компилятор для собственного функционального языка есть хорошая книга «Алгоритмы, языки, автоматы» Максима Мозгового.

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

              Ну и приоритет вроде обычно считается большим у тех операторов, чьё связывание операндов раньше. Тоесть у "*" приоритет выше чем у "+".
              Хотя и обозначается традиционно меньшим числом.
                +7
                > Суть метода 2х стеков (наверняка у него есть красивое научное название.)
                Да, судя по всему, это вариант алгоритма Дейкстры «сортировочная станция» Преобразование из инфиксной нотации
                  –1
                  Этот метод обычно называют Обратной Польской Нотацией или Постфиксной формой записи.
                  Мне ближе второе.
                    +1
                    Обратная польская нотация, постфиксная запись, ПОЛИЗ (польская инверсная запись) — это способ представления выражений, а мы говорим об алгоритме его получения из обычной, инфиксной записи.
                  0
                  2qmax, 2elw00d в общем это один и тот де алгоритм, только с немного разными реализациями… основной это, разумеется алгоритм Дейкстры

                  вместо стека операндов я иногда использую «выходную строку» или строю дерево. в зависимости от назначения алгоритма. :)
                    0
                    а с унарными операциями в чем проблема? они тоже имеют приоритет. по логике алгоритма очень большой. ввести у оператора параметр арность и брать из стека нужное количество операндов.
                      0
                      а зачем такие танцы с бубном, когда эта проблема решается одной строчкой :)

                      все n-арные операторы легко разруливаются бинарными и унарными операциями над списками.
                        0
                        Ну тут хороший вопрос — в каком случае это является танцами с бубнами. Помнится писал задачу в которой было много операцийс различной арностью, и 2 и 1 и 3 ;) И по моему введения для операции арность (раз уж у нее есть приоритет) гораздо легче, чем вставки для каждой операции «строчек» с приведением ее к чему либо другому.
                          0
                          Приведи пример 3-арной, 4-арной операции. Т.е. как она записываться буит :)
                          Я даж с кем-то на эту тему спорил у вас в педе гагарина :)
                          пришли в итоге к тому, что n-арные, где n >= 3 проще всего представлять как функцию F(x1, x2,… xn)
                    • UFO just landed and posted this here
                        0
                        Аналогично :-) Рекурсивный спуск на ФЯ рисуется очень быстро, плюс алгебраические типы и сопоставление с образцом для работы с AST. Получается хороший молоток для широкого класса гвоздей :-) Комбинаторы парсеров и что-то типа camlp4 — отдельная красивая песня.
                      • UFO just landed and posted this here
                        • UFO just landed and posted this here
                            +1
                            Уверен, что на хабре нашлись на те, кому этот алгоритм был интересен. Собственно для них я и писал.
                            В нем нет ничего нового, но далеко не все про него знают.
                            Я его знаю класса с 9ого. Удивлен, что ты его только на 3ем курсе асилил :)

                            Я думаю, чем новости с ЛенИздат постить, лучше уж попытаться объяснить интересный алгоритм, авось кому и пригодится. Ведь так? :)
                            • UFO just landed and posted this here
                                0
                                Хм… а это идея :)

                                Сделать цикл статей о доказательствах теорем, которые мы со школьных лет считаем аксиомами.
                                Все знают, что квадрат гипотенузы равен сумме квадратов катетов. Но, уверен, не все сходу доказать хотя бы одно из нескольких сотен доказательств.

                                Разумеется, этот материал есть в википедии и сотнях других источниках, но раз уж мы новости с других сайтов копируем – давайте будем писать о чем-то давно забытом, но не менее интересном :)

                                Народ же пишет для начинающих про языки программирования :) новичкам это нужно и важно, а нам (тем кто знает) тоже не помешает прочитать и, может быть, что-то интересное вспомнить или по-другому взглянуть на то, что всегда знал.
                          +1
                          Пара вопросов автору:
                          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. Я не программер, но для меня подобные статьи очень даже интересны, для расширения кругозора, например ))
                            +2
                            1) мой касяк. разумеется там должно быть Q.pop()

                            2) Нет. На том шаге должен быть +.
                            Как выяснилось, я потерял по дороге деление (уже поправил).
                            в общем если взять все push из каждого шага, то должно получиться выражение, которое мы разбираем.

                            +1 вам в карму, за внимательное чтение :)
                            0
                            Проблема в том, что код со стеком трудно распаралеливается суперскалярными процессорами.
                            Лучше «компилировать» формулу в «линейный вид», с несколькими виртуальными переменными.
                            • UFO just landed and posted this here
                                +2
                                Здравствуйте!

                                Вы просили меня прокомментировать с удовольствием.

                                Во-первых, спасибо за статью! Она лучше многих, я действительно так думаю, хотя вещи, которые я сейчас напишу могут вам не понравиться :-)

                                К делу.

                                Прежде всего, я бы советовал вам, почитать что-нибудь про грамматики. Тогда вместо наивных фраз любое сложно выражение (кстати, опечатка), вы могли бы написать грамматика класса LL(1) или что-то в этом духе. Когда вы говорите о разборе выражения, уместно классифицировать его грамматику, иначе звучит диковато и безграмотно (есть выражения, за разбор которых вы получите большие премии от видных математических обществ. есть выражения, которые невозможно разобрать и это доказано).

                                Далее. Зачем два стека? Вы же точно знаете, как чередуются операции и операнды! Чтобы соблюсти это чередование вы даже добавляете 0 к унарным операциям. Всё можно было бы положить в один стек.

                                О работе работе со стеком. Ваш алгоритм заставляет вас работать не только с верхушкой стека. Это дополнительное усложнение и источник ошибок. (Кстати, судя по обсуждению, вы не смогли избежать ошибок. А я вас предупреждал об это ещё до публикации этого поста. Работа со стеком требует большой аккуратности)

                                А теперь вспомним как работает алгоритм рекурсивного спуска. Вспомним, что локальные переменные хранятся в стеке. И что мы видим? Тот же стек, но! 1) он один 2) алгоритм не требует (и даже не позволяет) заглядывать под вершину стека 3) нет никаких проблем с унарными операторами и более сложными грамматиками 4) и самое главное нет необходимости работать со стеком руками! ошибки просто невозможны.

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

                                Если бы вы использовали рекурсивный спуск, вы застраховались бы от многих ошибок и получили бы универсальный парсер, в который можно было бы легко встроить, скажем, функции или операции с тремя операндами (типа А?B:C). В ваш теперешний парсер встроить такие возможности очень сложно (можно ли вообще). И править его очень опасно, так как тронув стек в одном месте, надо отследить, чтобы всё не посыпалось в другом.

                                Одним словом, ваш алгоритм я бы не стал использовать сам и не стал бы советовать другим.
                                  0
                                  PS
                                  странно запостилось — пропали все тире и кавычки :-/
                                  но, вроде, и так всё понятно.
                                    0
                                    Фуф… написал вам большой гневный комментарий с указанием на ваши ошибки… но потом зашёл на michurin.com.ru/ и понял, что спорить с вам в принципе бесполезно…

                                    Я понимаю, что вы меня старше на 11 лет и когда вы во всю уже работали я даже ещё и комп то в глаза не видел… но… вы не программист в полном смысле этого слова. Вы просто очень хороший системный администратор. :)
                                    Вы даже не понимаете что Stack и, так называемый, стек локальных переменных это 2 совершенно разные вещи…

                                    Предлагаю избавить хабрапользователей от нашей беседы и, если вы всё-таки считаете, что я не прав – писать мне в личку, icq или скайп
                                      0
                                      это «разные вещи», которые работают одинаково (возможно поэтому они и называются одинаково :-)); и именно на этом я и предлагаю сыграть :-)

                                      И всё же… я вам очень советую не читать мои комменты, не читать мои странички,… а почитать хорошие книжки; можно начать с этой ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf (есть более новая версия этой книги, но я что-то не смог её нагуглить). Я вижу, как вам нравится эта тема. Поверьте! Чтение этой (и других) книжки доставит вам на много больше удовольствия, чем попытки меня в чём-то убедить! Удачи!
                                        0
                                        не… 2 стека всё равно круче :)
                                        и открою вам секрет — в одной из моих программ (IVROS) я двумя стеками строю дерево ;)

                                        З.Ы. сейчас IVROS используется более чем в 30 банках и налоговых по Оренбургской области.
                                          0
                                          И всё же почитайте книжки. Кстати, есть довольно древний алгоритм Бауэра и Замельзона в котором используются два стека. Возможно, он вам будет более симпатичен, чем более современные подходы… Почитайте! Уверяю вас — вам понравится!
                                            0
                                            ды читал я их :) ещё в школе :) я бывший олимпиадник в универе, мне без книжек никуда :)
                                    0
                                    W.Push(-)
                                    у – приоритет выше чем у *, а значит, мы вытолкнем *. Для этого мы возьмём 2 последних операнда а на их место поставим результат операции A-B.
                                    B < — Q.pop()
                                    A < — Q.pop()
                                    Q.push(A — B)

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

                                    Only users with full accounts can post comments. Log in, please.