Обратная Польская Нотация

Мне больше нравится название на английском языке: Reverse Polish Notation (RPN), коим я и буду пользоваться.

Все мы с ранних классов, привыкли считать выражения такого вида 2 + 2 = ? или 2 * 2 + 2 = ?, может быть даже так (2 - 1) * 3 + 5 = ?. В нас буквально заложено понимание того, что каждая операция в приведенных выражениях имеет свой приоритет и это очень важно! В следствии чего дети всегда путали приоритеты или может быть вы не путали? Также усложняется читабельность ибо когда читал выражение, а потом увидел *, то сразу приходится в голове его перестраивать.

Более удобным видом описания мат. выражений является обратной польская запись (RPN), ее предложил польский математик Лукашевич. Она предлагает избавиться от приоритетов и убирает скобки. В общем выражение становится читать легче.

Давайте, попробуем перевести выше приведенные мной выражения в RPN, а делается это так:
2 + 2 в RPN будет 22+, то есть сначала идут операнды (их два), а затем операция, которую нужно над ними выполнить. Еще 2 * 2 + 2  22*2+, я знаю, что вам до сих привычней первый вид. Заметьте привычней, но не удобней. А теперь переведем (2 - 1) * 3 + 5 в RPN: 21-3*5+.

Помимо того, что мы избавились от скобок, так нам еще и не нужно запоминать приоритеты операций. Попробуем вычислить теперь последнее выражение 21-3*5+, по шагам:

1. 21- = 1, в итоге получаем 13*5+
2. 13* = 3, теперь rpn равняется 35+
3. 35+ = 8, что и является результатом выражения. 

Помимо того, что мы облегчили способ чтения математических выражений для себя, так и компьютеру, теперь будет считать их легче. 

Теперь перейдем к нашей задаче. Нам необходимо реализовать калькуляцию выражений вида (A+B)*C/D-E используя язык программирования C#. Также вместо переменных (A, B, C  и т.д.) мы будем использовать простые цифры (0-9).

По крайнее мере есть два алгоритма перевода выражений в обратную польскую запись RPN:

1. Используя бинарные деревья.
2. Используя стек.

Я покажу перевод выражений в обратную польскую запись на примере стека, после чего продемонстрирую вычисление мат. выражений с использованием RPN.

Для перевода обычного мат. выражения в rpn я написал простой класс Converter, я не буду приводить весь код класса, его вы сможете скачать на code.google.com в конце статьи я указал ссылку, а приведу лишь метод ToRpn, ибо я считаю он более важен.

    public string ToRpn(string expression)
    {   
        // очищаем стек
        _stack.Purge();
        string output = "";
          
        // обходим строку посимвольно
        foreach (char c in expression)
        {   
            // если встретили закрывающую скобку
            if (c == ')')
            {  
                // вытаскиваем операции из стека
                // пока не дойдем до открывающейся скобки 
                char op = (char)_stack.Pop(); 
                while (op != '(') 
                {
                    output += op;
                    op = (char)_stack.Pop();
                }
            } 
            // если встретили цифру
            else if (Char.IsDigit(c))
            {
                // сразу добавляем ее к выходной строке
                output += c;
            } 
            // если открывающую скобку
            else if (c == '(')
            {
                // то помещаем ее в стек
                _stack.Push(c);
            }
            // если встретили арифметическую операцию
            else if (IsArithmeticOperation(c))
            {   
                // если стек - пуст
                if (_stack.IsEmpty)
                {
                    // помещаем операцию в стек
                    _stack.Push(c);
                }
                else
                {
                     // проверяем приоритеты 
                     if (GetPriority(c) > 
                         GetPriority((char)_stack.Top))
                     {
                         _stack.Push(c);
                     }
                     else
                     {
                         
                            while (!_stack.IsEmpty &&
                                   GetPriority(c) <= 
                                   GetPriority(
                                       (char)_stack.Top))
                            {
                                output += 
                                    (char)_stack.Pop(); ;
                            }                        
                            _stack.Push(c);
                     }
                }
            }
        }

        // добавляем в выходную строку оставшиеся символы
        while (!_stack.IsEmpty)
        {
            output += (char)_stack.Pop();
        }
   
        return output;
    }

Думаю, комментарии дадут вам понять шаги алгоритма, он достаточно прост. Visual Studio проект с использованием C# можно скачать отсюда.

Используемые материалы: 

1. http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D0%BB%D1%8C%D1%81%D0%BA%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C
2. http://algolist.manual.ru/maths/misc/revpn.php
3. http://habrahabr.ru/blogs/algorithm/100869/

Используемые библиотеки: 

1. Opus6

Спасибо за внимание, вопросы и замечания принимаются в комментариях!