Всем привет! Сегодня хочу поделиться опытом написания консольного инженерного калькулятора, который может посчитать выражение вроде (log2(18)/3.14)*sqrt(0.1*10^(-3)/0.02)

Почему именно калькулятор (ну камон, их же и так тьма тьмущая)? Все потому, что в школе дали задание написать графический калькулятор на Qt; мне это показалось скучным, и я решил поэкспериментировать.

Введение

Статья разделена на 2 части:

  1. Токенизатор математических выражений

  2. Обратная польская запись (Алгоритм сортировочной станции)

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

Зачем это нужно? Обработка математического выражения в том виде, в котором оно есть, весьма неудобно - ведь операторы имеют приоритет, скобки этот приоритет меняют, а есть еще и функции, а унарное отрицание - так вообще ужас... Получается неудобно. Чтобы эту проблему решить, были придуманы Обратная польская запись (RPN) и Алгоритм сортировочной станции, позволяющий обычную запись выражения (ее также называют инфиксной) преобразовать в RPN (она является постфиксной). О них речь пойдет в следующей части.

Пока важно лишь то, что для преобразования инфиксного выражения в RPN его сначала необходимо токенизировать.

Конечный автомат

Если вы заглянете на эту статью в Википедии, то увидите, что парсеры для языков с формальной грамматикой (нам такое подходит) построены на конечных автоматах. О том, что такое конечный автомат, вы можете почитать здесь.

В первую очередь, определим набор состояний. По задумке, токенизатор умеет распознавать: числовые литералы (целые и floating-point) , операторы (лево- и правоаcсоциативные), функции от фиксированного числа аргументов, а также символ-разделитель аргументов функции (запятая).

S0

Стартовое

S1

Токенизация скобки/оператора

S2

Запись целого числа в буфер

S3

Запись floating-point числа в буфер

S4

Запись функции в буфер

S5

Токенизация записанного числа/функции из буфера:

Теперь переходы между состояниями (в виде графа и таблицы).

Легенда: Оп = Оператор (+ - ^ * /) , Бук = Буква, Циф = Цифра. Отдельные символы перечислены через пробел.

Рис 1. Переходы между состояниями
Рис 2. Переходы между состояниями (таблица)

Краткое пояснение работы автомата:

  • На вход последовательно поступают символы строки-выражения

  • Если текущий обрабатываемый символ:

    • Оператор или скобка: просто токенизируем (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

С токенизатором на этом, собственно, все. Пример работы:

Рис 3. Пример токенизации

Код целиком приведен ниже.

Код
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

А вот и вторая часть!