Всем маткульт-привет! В этой статье мы продолжаем и заканчиваем написание консольного инженерного калькулятора. Для понимания происходящего настоятельно рекомендую сначала ознакомиться с первой частью.
Введение
В прошлой части мы научились разбивать исходное математическое выражение формата (log2(18)/3.14)*sqrt(0.11^(-3)/0.02)на токены. На выходе мы получаем массив токенов, каждый их которых содержит информацию о типе (оператор, скобка, число, …) и об ассоциативности, если он таковую имеет.
Теперь мы хотим привести выражение к виду обратной польской записи (RPN), чтобы затем удобно его посчитать. Это нам позволяет сделать изобретенный Эдсгером Дейкстрой алгоритм сортировочной станции.
Алгоритм сортировочной станции
Описание
Не мудрствуя лукаво и не изобретая велосипед, скажу, что подробное описание работы алгоритма на русском и на английском есть на Википедии. В англиской версии также наглядно показано, почему алгоритм так называется — его работа напоминает работу железнодорожной сортировочной станции.
Сложность 
, что очень и очень радует.
Алгоритм
-
Пока не все токены обработаны:
-
Прочитать токен.
-
Если токен — число, то добавить его в очередь вывода.
-
Если токен — функция, то поместить его в стек.
-
Если токен — разделитель аргументов функции (запятая):
-
Пока токен на вершине стека не открывающая скобка:
-
Переложить оператор из стека в очередь вывода.
-
Если стек закончился до того, как был встречен токен открывающая скобка, то в выражении пропущен разделитель аргументов функции (запятая), либо пропущена открывающая скобка.
-
-
-
Если токен — оператор op1, то:
-
Пока присутствует на вершине стека токен оператор op2, чей приоритет выше или равен приоритету op1, и при равенстве приоритетов op1 является левоассоциативным:
-
Переложить op2 из стека в очередь вывода;
-
-
Положить op1 в стек.
-
-
Если токен — открывающая скобка, то положить его в стек.
-
Если токен — закрывающая скобка:
-
Пока токен на вершине стека не открывающая скобка:
-
Переложить оператор из стека в очередь вывода.
-
Если стек закончился до того, как был встречен токен открывающая скобка, то в выражении пропущена скобка.
-
-
Выкинуть открывающую скобку из стека, но не добавлять в очередь вывода.
-
-
Если токен на вершине стека — функция, переложить её в очередь вывода.
-
-
-
Если больше не осталось токенов на входе:
-
Пока есть токены операторы в стеке:
-
Если токен оператор на вершине стека — открывающая скобка, то в выражении пропущена скобка.
-
Переложить оператор из стека в очередь вывода.
-
-
-
Конец.
Приступим к реализации. Напомню, что токенизатор и класс 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 в заключается в том, что нам больше не надо заботиться о приоритете операций — все операнды и операторы уже расположены в нужном порядке. Так что нам лишь остается последовательно пройтись по операторам, записывая промежуточные вычисления на стек.
Алгоритм
-
Обработка входного символа
-
Если на вход подан операнд, он помещается на вершину стека.
-
Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
-
-
Если входной набор символов обработан не полностью, перейти к шагу 1.
-
После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.
Реализация
Фукнция 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-калькулятора.
ссылка на оригинал статьи https://habr.com/ru/articles/777368/
Добавить комментарий