Всем маткульт-привет! В этой статье мы продолжаем и заканчиваем написание консольного инженерного калькулятора. Для понимания происходящего настоятельно рекомендую сначала ознакомиться с первой частью.

Введение

В прошлой части мы научились разбивать исходное математическое выражение формата (log2(18)/3.14)*sqrt(0.11^(-3)/0.02)на токены. На выходе мы получаем массив токенов, каждый их которых содержит информацию о типе (оператор, скобка, число, ...) и об ассоциативности, если он таковую имеет.

Теперь мы хотим привести выражение к виду обратной польской записи (RPN), чтобы затем удобно его посчитать. Это нам позволяет сделать изобретенный Эдсгером Дейкстрой алгоритм сортировочной станции.

Алгоритм сортировочной станции

Описание

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

Сложность , что очень и очень радует.

Приступим к реализации. Напомню, что токенизатор и класс Token - в первой части.

Реализация

Фунция shuntingYard принимает на вход вектор токенов; на выходе выдает тоже вектор токенов, так называемую очередь вывода, но уже в RPN,

void shuntingYard(const std::vector<Token> &expr, std::vector<Token> &outQueue)
{ // ...

Основа работы алгоритма - стек, в который помещаются операторы, функции, скобки и разделители, а затем переносятся в очередь вывода. Эта операция выполняется часто, поэтому для удобства используем лямбду, которая перемещает токен с вершины стека в очередь вывода.

// ...
std::stack<Token> stack;
auto fromStackToQueue = [&]() { outQueue.push_back(stack.top()); stack.pop(); };
// ...

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

// ...
for(const auto& token : expr)
    {
        switch(token.getType())
        {
        case Token::INT_LITERAL:
        case Token::FLOAT_LITERAL:
            outQueue.push_back(token);
            break;
        case Token::L_PARANTHESIS:
        case Token::FUNCTION:
            stack.push(token);
            break;
        // ...

Если токен - оператор:

// ...
case Token::OPERATOR:
    if(!stack.empty())
    {
        /* Пока на вершине стека присутствует правоассоциативный оператор с приоритетом выше,
           или левоассоциативный с равным приоритетом, перекладываем его в очередь вывода   */
        while(stack.top().getType() == Token::OPERATOR && ((stack.top().getPrecendance() > token.getPrecendance())
                || (stack.top().getPrecendance() == token.getPrecendance() && token.getAsc() == Token::LEFT)))
        {
            fromStackToQueue();
            if(stack.empty()) 
                break;
        }
    }
    // Перекладываем текущий токен на вершину стека
    stack.push(token);
    break;
// ...

Если токен - закрывающая скобка:

// ...
case Token::R_PARANTHESIS:
    // Если стек уже пуст, даже не начинаем цикл
    if(stack.empty())
        throw Error("Non-balanced on paranthesis expression!", Error::Syntax);

    // Пока не встретили открывающую скобку, перекладываем токен с вершины стека в очередь вывода
    while (stack.top().getType() != Token::L_PARANTHESIS)
    {
        fromStackToQueue();
        // Если стек кончился, а открывающую скобку не встретили - в исходном выражении не хватает скобок
        if (stack.empty())
            throw Error("Non-balanced on paranthesis expression!", Error::Syntax);
    }

    // Удаляем открывающую скобку со стека, не перенося её в очередь вывода
    stack.pop();

    // Если на вершине оказалась функция, перекладываем её а стек
    if(!stack.empty() && stack.top().getType() == Token::FUNCTION)
        fromStackToQueue();
    break;
    // ...

Если токен - разделитель аргументов функции (он же запятая):

// ...
case Token::SEPARATOR:
    // Если стек уже пуст, даже не начинаем цикл
    if(stack.empty())
        throw Error("Paranthesis or separator missed!", Error::Syntax);

    // Пока не наткнулись на открывающую скобку, перекладываем токены со стека в очередь вывода
    while(stack.top().getType() != Token::L_PARANTHESIS)
    {
        fromStackToQueue();
        // Если так и не встретили закрывающую скобку - в исходном выражении не хватает скобки или разделителя
        if(stack.empty())
            throw Error("Paranthesis or separator missed!", Error::Syntax);
    }
    break;
} // конец цикла
// ...

Теперь перекладываем опереторы, оставшиеся на стеке, в очередь вывода:

// ...
while(!stack.empty())
{
    if(stack.top().getType() == Token::L_PARANTHESIS)
        throw Error("Paranthesis-unbalanced expression!", Error::Syntax);
    else
        fromStackToQueue();
} // конец функции shuntingYard

Отлично, мы преобразовали выражение.

Например, из(log2(18)/3.14)*sqrt(0.11^(-3)/0.02) мы получим последовательность23 log2 2 - 3.14 / 0.1 10 3 - ^ * 0.02 / sqrt * +

Обсчет RPN

Теперь то, зачем мы все здесь собрались - посчитать. Как подробно описано здесь, весь смысл RPN в заключается в том, что нам больше не надо заботиться о приоритете операций - все операнды и операторы уже расположены в нужном порядке. Так что нам лишь остается последовательно пройтись по операторам, записывая промежуточные вычисления на стек.

Реализация

Фукнция countRPN будем принимать на вход вектор токенов в RPN (да ладно!) и возвращать результат вычисления.

double countRPN(const std::vector<Token> &expr)
{ // ...

Теперь нам понадобится стек, куда мы будем класть операнды и результаты промежуточных вычислений:

// ...
std::stack<double> stack;
// ...

Для удобства введем лямбды, которые будут брать один или два аргумента со стека:

// ...
auto getOneToken = [&]() 
{
    if(stack.empty()) throw Error("Not enough arguments in function!", Error::Syntax);
    double x = stack.top(); 
    stack.pop(); 
    return x; 
};

auto getTwoTokens = [&]()
    { double x = getOneToken(), y = getOneToken(); return std::tuple{y,x}; };
// ...

Теперь, собственно, посчитайка:

// ...
double res;
for (auto &token : expr)
{
    const std::string &str = token.getStr();
    switch(token.getType())
    {
    // Если токен - числовой литерал, он же операнд, кладем на стек
    case Token::INT_LITERAL:
        stack.push(std::stof(str));
        break;
    case Token::FLOAT_LITERAL:
        stack.push(std::stof(str));
        break;
// ...

Теперь операторы:

// ...
case Token::OPERATOR:
    switch(token.getAsc())
    {
    // Левоассоциативные операторы
    case Token::LEFT:
    {
        auto [a,b] = getTwoTokens(); 
        if      (str == "+") res = a + b;
        else if (str == "-") res = a - b;
        else if (str == "*") res = a * b;
        else if (str == "/") res = checkedDivision(a, b);
        else if (str == "^") res = std::pow(a,b);
        else    throw Error("Unknown operator!", Error::Syntax);
        break;
    }
    // Правоассоциативные операторы
    case Token::RIGHT:
    {
        auto a = getOneToken();
        if   (str == "-") res = -a;
        else throw Error("Unknown operator!", Error::Syntax);
        break;
    }
    }
    stack.push(res);
    break;
// ...

И функции:

// ...
    case Token::FUNCTION:
        if(str == "log") 
        {
            auto [a,b] = getTwoTokens();
            if(a <= 0.f || a == 1.0f) throw Error(std::format("log(a,x): not defined for a = {}", a), Error::Math);
            if(b <= 0.f) throw Error("log(a,x): out of function's domain", Error::Math);
            res = std::log(b) / std::log(a);
        }
        else if 
        // сколько хотите, столько и добавляйте
        else
            throw Error("Unknown function!", Error::Syntax);
        stack.push(res);
        break;
    }
} // конец цикла
// ...

Результатом будет единственный оставшийся элемент на стеке:

// ...
  return stack.top();
} // конец функции countRPN

Заключение

Весь код проекта лежит на github. Надеюсь, что было интересно.

UPD

Как было замечено в комментарии к первой части, существует куда более простой способ сделать то, что было описано в статье - генератор синтаксических анализаторов GNU Bison, разработанный аж в 1985 году. В официальной документации есть пример создания RPN-калькулятора.