Всем привет! Сегодня хочу поделиться опытом написания консольного инженерного калькулятора, который может посчитать выражение вроде (log2(18)/3.14)*sqrt(0.1*10^(-3)/0.02)
Почему именно калькулятор (ну камон, их же и так тьма тьмущая)? Все потому, что в школе дали задание написать графический калькулятор на Qt; мне это показалось скучным, и я решил поэкспериментировать.
Введение
Статья разделена на 2 части:
Токенизатор математических выражений
Обратная польская запись (Алгоритм сортировочной станции)
В этой части мы рассмотрим создание простейшего парсера (токенизатора) на базе конечного автомата, который будет разделять исходное выражение на части: числовые литералы, операторы, функции и т.п.
Зачем это нужно? Обработка математического выражения в том виде, в котором оно есть, весьма неудобно - ведь операторы имеют приоритет, скобки этот приоритет меняют, а есть еще и функции, а унарное отрицание - так вообще ужас... Получается неудобно. Чтобы эту проблему решить, были придуманы Обратная польская запись (RPN) и Алгоритм сортировочной станции, позволяющий обычную запись выражения (ее также называют инфиксной) преобразовать в RPN (она является постфиксной). О них речь пойдет в следующей части.
Пока важно лишь то, что для преобразования инфиксного выражения в RPN его сначала необходимо токенизировать.
Конечный автомат
Если вы заглянете на эту статью в Википедии, то увидите, что парсеры для языков с формальной грамматикой (нам такое подходит) построены на конечных автоматах. О том, что такое конечный автомат, вы можете почитать здесь.
В первую очередь, определим набор состояний. По задумке, токенизатор умеет распознавать: числовые литералы (целые и floating-point) , операторы (лево- и правоаcсоциативные), функции от фиксированного числа аргументов, а также символ-разделитель аргументов функции (запятая).
S0 | Стартовое |
S1 | Токенизация скобки/оператора |
S2 | Запись целого числа в буфер |
S3 | Запись floating-point числа в буфер |
S4 | Запись функции в буфер |
S5 | Токенизация записанного числа/функции из буфера: |
Теперь переходы между сост��яниями (в виде графа и таблицы).
Легенда: Оп = Оператор (+ - ^ * /) , Бук = Буква, Циф = Цифра. Отдельные символы перечислены через пробел.
Краткое пояснение работы автомата:
На вход последовательно поступают символы строки-выражения
Если текущий обрабатываемый символ:
Оператор или скобка: просто токенизируем (S1)
Цифра или буква: записываем в буфер, т.к. все число или называние функции может состоять из нескольких символов (S2, S3, S4). Обратите внимание: название функций может также содержать в себе цифры, например
log2(x)
Запись в буфер прерывается, как только на вход поступает оператор, скобка или разделитель (S5). Тогда мы сохраняем содержимое буфера в один токен, а оператор/скобку/разделитель - в другой
Если обрабатываемый символ не соответствует текущему состоянию (например, в исходном выражении встречается
).), значит выражение содержит синтаксическую ошибку. Таким образом мы можем поймать часть синтаксических ошибок еще на этапе токенизации; остальные будем ловить в Алгоритме сортировочной станции, но уже в следующ��й части
Но это все слова. Давайте воплотим это в код.
Класс токена
Мы хотим, чтобы класс токена хранил информацию о типе токена и его ассоциативности, а также сам токен в виде строки:
class Token { public: // Тип enum Type { OPERATOR, // унарный/бинарный оператор L_PARANTHESIS, // открывающая скобка R_PARANTHESIS, // закрывающая скобка INT_LITERAL, // целое число FLOAT_LITERAL, // число с плавающей точкой FUNCTION, // функция SEPARATOR // разделитель аргументов функции }; // Ассоциативность enum OperatorAssociativity { NONE, // токен - не оператор RIGHT, // правоассоциативный LEFT // левоассоциативный }; Token(std::string token, Type type, OperatorAssociativity asc = NONE); // Приоритет int getPrecendance() const; // Геттеры ( ну у нас же ООП :D ) const Type& getType() const { return type; } const OperatorAssociativity& getAsc() const { return opAsc; } const std::string& getStr() const { return str; } private: Type type; OperatorAssociativity opAsc; std::string str; };
Конструктор:
Token::Token(std::string token, Type type, OperatorAssociativity asc) : type{type} , str{token} { // если токен - оператор, но ассоциативность не задана - ошибка (алгоритма) if(type == OPERATOR && asc == NONE) throw std::logic_error("Associativity required!"); // если токен - НЕ оператор, но ассоциативность задана - ошибка else if(type != OPERATOR && asc != NONE) throw std::logic_error("Non-operator token can't have an associativity!"); opAsc = asc; }
Функция getPrecedance() вовращает приоритет оператора в виде целого числа. Приоритет тем меньше, чем меньше число. Если токен - не оператор, генерирует исключение.
int Token::getPrecendance() const { static std::map<std::string, int> op_leftassociative = { {"+", 2}, {"-", 2}, {"/", 3}, {"*", 3}, {"^", 5} }; static std::map<std::string, int> op_rightassociative = { {"-", 4} // унарное отрицание }; // В зависимости от ассоциативности один и тот же символ означает разные операторы switch(opAsc) { case LEFT: // Если str явлеяется ключом map-а, значит мы знаем такой оператор if(op_leftassociative.contains(str)) return op_leftassociative[str]; else throw Error("Unknown Operator!", Error::Syntax); break; case RIGHT: if(op_rightassociative.contains(str)) return op_rightassociative[str]; else throw Error("Unknown Operator!", Error::Syntax); break; case NONE: throw std::logic_error( std::format("Token \"{}\" is not an operatator, impossible.", str) ); break; } }
Отмечу, что для сигнализации об ошибках я использую собственный класс Error для обозначения синтаксических и (в дальнейшем) математических ошибок в исходном инфиксном выражении, и std::logic_error для обозначения программных багов.
Токенизатор-автомат
Во первых, состояния:
enum State { S0, // Стартовое S1, // Токенизация скобки/оператора S2, // Запись целого числа в буфер S3, // Запись floating-point числа в буфер S4, // Запись функции в буфер S5 // Токенизация записанного числа/функции из буфера };
Теперь конечный автомат. Реализуем его функцией, принимающей на вход сроку-выражение, а на выходе дающую вектор токенов.
void tokenize(const std::string &expr, std::vector<Token> &tokens) { // ...
Объявим необходимые переменные:
// ... State state = S0; // Устанавливаем состояние в начальное std::string validOperators = "+-*^/"; // Допустимые операторы // каким типом является текущий символ? bool isDigit, isLetter, isOp, isParanth, isPoint, isSep, isLParanth, isRParanth; std::string buffer; // Буфер Token::Type bufferTokenType = Token::INT_LITERAL; // Тип токена, записаного в буфере // ...
Цикл:
// ... for(auto& s : expr) { // Определяем тип символа isDigit = std::isdigit(s); isLetter = std::isalpha(s); isLParanth = s == '('; isRParanth = s == ')'; isParanth = isLParanth || isRParanth; isPoint = s == '.'; isSep = s == ','; isOp = validOperators.find(s) != validOperators.npos; // Если тип символа неопределен, значит ошибка в синтаксисе if(!(isDigit || isLetter || isParanth || isPoint || isSep || isOp)) throw SyntaxError(std::format("Unknown symbol: {}", s)); // Смена состояния switch(state) { case S0: if (isOp || isParanth) state = S1; else if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw SyntaxError(std::format("Unexpected symbol: {}", s)); break; case S1: if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw SyntaxError(std::format("Unexpected symbol: {}", s)); break; case S2: bufferTokenType = Token::INT_LITERAL; if (isPoint) state = S3; else if (isParanth || isOp || isSep) state = S5; else if (isLetter) throw SyntaxError(std::format("Unexpected symbol: {}", s)); break; // и так далее для состояний S3, S4, S5. Остальной код можно посмотреть в конце статьи default: break; } // ...
Далее - соответствующее действия на каждое из состояний:
// ... // Токенизирует оператор/скобку/разделитель auto tokenize_Op_Paranth_Sep = [&]() { /* ... */ }; // Действия switch(state) { case S1: tokenize_Op_Paranth_Sep(); break; case S2: case S3: case S4: // Записываем цифру/букву в буфер buffer.push_back(s); break; case S5: // Токенизируем содержимое буфера tokens.push_back({buffer, bufferTokenType}); // Освобождаем буфер buffer.clear(); // Токенизируем текущий символ tokenize_Op_Paranth_Sep(); break; } } // конец цикла // ...
Если после обработки всех символов в буфере в��е еще что-то осталось, токенизируем:
// ... if(!buffer.empty()) tokens.push_back({buffer, bufferTokenType}); } // конец функции tokenize
С токенизатором на этом, собственно, все. Пример работы:
Код целиком приведен ниже.
Код
Error.hpp
#pragma once #include <string> class Error { public: enum Type { Syntax, Math } type; Error(std::string message, Type errorType) : type{errorType} { switch(errorType) { case Syntax: msg = "Syntax Error: " + message; break; case Math: msg = "Math Error: " + message; break; } } std::string what() { return msg; } private: std::string msg; };
Token.hpp
#pragma once #include <string> class Token { public: // Тип enum Type { OPERATOR, // унарный/бинарный оператор L_PARANTHESIS, // открывающая скобка R_PARANTHESIS, // закрывающая скобка INT_LITERAL, // целое число FLOAT_LITERAL, // число с плавающей точкой FUNCTION, // функция SEPARATOR // разделитель аргументов функции }; // Ассоциативность enum OperatorAssociativity { NONE, // токен - не оператор RIGHT, // правоассоциативный LEFT // левоассоциативный }; Token(std::string token, Type type, OperatorAssociativity asc = NONE); // Приоритет int getPrecendance() const; const Type& getType() const { return type; } const OperatorAssociativity& getAsc() const { return opAsc; } const std::string& getStr() const { return str; } private: Type type; OperatorAssociativity opAsc; std::string str; };
Token.cpp
#include <map> #include <stdexcept> #include <format> #include "Token.hpp" #include "Error.hpp" Token::Token(std::string token, Type type, OperatorAssociativity asc) : type{type} , str{token} { // если токен - оператор, но ассоциативность не задана - ошибка if(type == OPERATOR && asc == NONE) throw std::logic_error("Associativity required!"); // если токен - НЕ оператор, но ассоциативность задана - ошибка else if(type != OPERATOR && asc != NONE) throw std::logic_error("Non-operator token can't have an associativity!"); opAsc = asc; } int Token::getPrecendance() const { static std::map<std::string, int> op_leftassociative = { {"+", 2}, {"-", 2}, {"/", 3}, {"*", 3}, {"^", 5} }; static std::map<std::string, int> op_rightassociative = { {"-", 4} // унарное отрицание }; switch(opAsc) { case LEFT: if(op_leftassociative.contains(str)) return op_leftassociative[str]; else throw Error("Unknown Operator!", Error::Syntax); break; case RIGHT: if(op_rightassociative.contains(str)) return op_rightassociative[str]; else throw Error("Unknown Operator!", Error::Syntax); break; case NONE: throw std::logic_error( std::format("Token \"{}\" is not an operatator, impossible.", str) ); break; } }
Tokenizer.hpp
#pragma once #include <vector> #include "Token.hpp" enum State { S0, // Стартовое S1, // Токенизация скобки/оператора S2, // Запись целого числа в буфер S3, // Запись floating-point числа в буфер S4, // Запись функции в буфер S5 // Токенизация записанного числа/функции из буфера }; void tokenize(const std::string &expr, std::vector<Token> &tokens);
Tokenizer.cpp
#include "Tokenizer.hpp" #include <iostream> #include <format> #include <map> #include <string> #include "Error.hpp" void tokenize(const std::string &expr, std::vector<Token> &tokens) { State state = S0; std::string validOperators = "+-*^/"; bool isDigit, isLetter, isOp, isParanth, isPoint, isSep, isLParanth, isRParanth; std::string buffer; Token::Type bufferTokenType = Token::INT_LITERAL; for(auto& s : expr) { // Определяем тип символа isDigit = std::isdigit(s); isLetter = std::isalpha(s); isLParanth = s == '('; isRParanth = s == ')'; isParanth = isLParanth || isRParanth; isPoint = s == '.'; isSep = s == ','; isOp = validOperators.find(s) != validOperators.npos; // Если тип символа неопределен, значит ошибка в синтаксисе if(!(isDigit || isLetter || isParanth || isPoint || isSep || isOp)) throw Error(std::format("Unknown symbol: {}", s), Error::Syntax); // Смена состояния switch(state) { case S0: if (isOp || isParanth) state = S1; else if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw Error(std::format("Unexpected symbol: \"{}\"", s), Error::Syntax); break; case S1: if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw Error(std::format("Unexpected symbol: \"{}\"", s), Error::Syntax); break; case S2: bufferTokenType = Token::INT_LITERAL; if (isPoint) state = S3; else if (isParanth || isOp || isSep) state = S5; else if (isLetter) throw Error(std::format("Unexpected symbol: \"{}\"", s), Error::Syntax); break; case S3: bufferTokenType = Token::FLOAT_LITERAL; if (isParanth || isOp || isSep) state = S5; else if (isPoint) throw Error(std::format("Unexpected symbol: \"{}\"", s), Error::Syntax); break; case S4: bufferTokenType = Token::FUNCTION; if(isLParanth) state = S5; else if(isOp || isRParanth || isSep) throw Error(std::format("Unexpected symbol \"{}\"", s), Error::Syntax); break; case S5: if (isParanth || isOp) state = S1; else if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw Error(std::format("Unexpected symbol: \"{}\"", s), Error::Syntax); break; default: break; } auto tokenize_Op_Paranth_Sep = [&]() { if(isOp) { // обработка unary negation if(tokens.size() == 0 || tokens[tokens.size()-1].getType() == Token::L_PARANTHESIS) tokens.push_back({std::string{s}, Token::OPERATOR, Token::RIGHT}); else tokens.push_back({std::string{s}, Token::OPERATOR, Token::LEFT}); } else if(isParanth) { tokens.push_back({std::string{s}, isRParanth ? Token::R_PARANTHESIS : Token::L_PARANTHESIS}); } else if(isSep) { tokens.push_back({std::string{s}, Token::SEPARATOR}); } }; // Действия switch(state) { case S1: tokenize_Op_Paranth_Sep(); break; case S2: case S3: case S4: buffer.push_back(s); break; case S5: tokens.push_back({buffer, bufferTokenType}); buffer.clear(); tokenize_Op_Paranth_Sep(); break; } } if(!buffer.empty()) tokens.push_back({buffer, bufferTokenType}); }
main.cpp
#include <iostream> #include "Tokenizer.hpp" int main() { std::vector<Token> tokensInfix; std::string expr = "log2(23)+(2/(3.14))*(sqrt(0.1*10^(-3)/0.02))"; std::cout << "Expression: " << expr << std::endl; try { tokenize(expr, tokensInfix); // Красиво печатаем токены в консоль for(auto& i : tokensInfix) { std::string type, asc; switch(i.getType()) { case Token::OPERATOR: type = "OPERATOR"; break; case Token::L_PARANTHESIS: type = "L_PARANTHESIS"; break; case Token::R_PARANTHESIS: type = "R_PARANTHESIS"; break; case Token::INT_LITERAL: type = "INT_LITERAL"; break; case Token::FLOAT_LITERAL: type = "FLOAT_LITERAL"; break; case Token::FUNCTION: type = "FUNCTION"; break; case Token::SEPARATOR: type = "OPERATOR"; break; } switch(i.getAsc()) { case Token::NONE: asc = "NONE"; break; case Token::RIGHT: asc = "RIGHT"; break; case Token::LEFT: asc = "LEFT"; break; } std::cout << i.getStr() << "\t\t" << type << "\t\t" << asc << "\n"; } } catch(Error &e) { std::cerr << e.what() << "\n"; exit(-1); } catch(const std::exception& e) { std::cerr << e.what() << '\n'; exit(-1); } return 0; }
Заключение
Надеюсь, было интересно. В следующей статье, как было обещанно, будет реализация Алгоритма сортировочной станции, и калькулятор (мы же все здесь за этим собрались?) будет доведен до конца.
UPD
А вот и вторая часть!
