Инженерный калькулятор на C++. Часть 1: Токенизатор математических выражений25.10.2023 12:45

Всем привет! Сегодня хочу поделиться опытом написания консольного инженерного калькулятора, который может посчитать что-то вроде (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. Переходы между состояниями

Рис 1. Переходы между состояниями

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

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

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

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

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

    • Оператор или скобка: просто токенизируем (S1)

    • Цифра или буква: записываем в буфер, т.к. все число или называние функции может состоять из нескольких символов (S2, S3, S4).

  • Запись в буфер прерывается, как только на вход поступает оператор, скобка или разделитель (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 SyntaxError("Associativity required!");

    // если токен - НЕ оператор, но ассоциативность задана - ошибка
    else if(type != OPERATOR && asc != NONE)
        throw SyntaxError("Non-operator token can't have an associativity!");

    opAsc = asc;
}

Функция getPrecedance() вовращает приоритет оператора в виде целого числа. Приоритет тем меньше, чем меньше число. Если токен — не оператор, генерирует исключение. 

int Token::getPrecendance() const
{
    static std::map op_leftassociative = 
    {
        {"+", 2},
        {"-", 2},
        {"/", 3},
        {"*", 3},
        {"^", 5}
    };


    static std::map op_rightassociative = 
    {
        {"-", 4} // унарное отрицание
    };
    
    switch(opAsc)
    {
    case LEFT:
        if(op_leftassociative.contains(str)) return op_leftassociative[str];
        else throw SyntaxError("Unknown Operator!");
        break;
    case RIGHT:
        if(op_rightassociative.contains(str)) return op_rightassociative[str];
        else throw SyntaxError("Unknown Operator!");
        break;
    case NONE:
        throw SyntaxError("Token is not an operator, impossible!");
        break;
    }
}

Токенизатор-автомат

Во первых, состояния: 

enum State
{
    S0, // Стартовое
    S1, // Токенизация скобки/оператора
    S2, // Запись целого числа в буфер
    S3, // Запись floating-point числа в буфер
    S4, // Запись функции в буфер
    S5  // Токенизация записанного числа/функции из буфера
};

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

void tokenize(const std::string &expr, std::vector &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

С токенизатором на этом, собственно, все. Код целиком приведен ниже.

Код

SyntaxError.hpp
#pragma once
#include 

class SyntaxError
{
public:
    SyntaxError(std::string msg)
    {
        _msg = "Syntax Error: " + msg;
    }
    std::string what() { return _msg; }

private:
    std::string _msg;
};
Token.hpp
#pragma once
#include 

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;
};
Tokenizer.hpp
#pragma once
#include 
#include "Token.hpp"

enum State
{
    S0, // Стартовое
    S1, // Токенизация скобки/оператора
    S2, // Запись целого числа в буфер
    S3, // Запись floating-point числа в буфер
    S4, // Запись функции в буфер
    S5  // Токенизация записанного числа/функции из буфера
};


void tokenize(const std::string &expr, std::vector &tokens);
Tokenizer.cpp
#include "Tokenizer.hpp"
#include 
#include 
#include 
#include 
#include "SyntaxError.hpp"

void tokenize(const std::string &expr, std::vector &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;
        case S3:
            bufferTokenType = Token::FLOAT_LITERAL;
            if (isParanth || isOp || isSep)
                state = S5;
            else if (isPoint)
                throw SyntaxError(std::format("Unexpected symbol: {}", s));
            break;
        case S4:
            bufferTokenType = Token::FUNCTION;
            if(isLParanth)
                state = S5;
            else if(isDigit || isOp || isRParanth || isSep)
                throw SyntaxError(std::format("Unexpected symbol: {}", s));
            break;
        case S5:
            if (isParanth || isOp)
                state = S1;
            else if (isDigit)
                state = S2;
            else if (isLetter)
                state = S4;
            else if (isPoint || isSep)
                throw SyntaxError(std::format("Unexpected symbol: {}", s));
            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 "Tokenizer.hpp"
#include 

int main()
{
    std::vector tokensInfix, tokensRPN;

    std::string expr = "(log2(18)/3.14)*sqrt(0.1*10^(-3)/0.02)";
    std::cout << "Expression: " << expr << std::endl;

    try
    {
        tokenize(expr, tokensInfix);
        for(auto& i : tokensInfix) 
          std::cout << i.getStr() << ", type = " << i.getType() << 
          ", associative = " << i.getAsc() << "\n";
    }
    catch(SyntaxError &e)
    {
        std::cerr << e.what() << "\n";
        exit(-1);
    }
    catch(const std::exception& e)
    {
        std::cerr << e.what() << '\n';
        exit(-1);
    }

    return 0;
}

Заключение

Надеюсь, было интересно. В следующей статье, как было обещанно, будет моя реализация Алгоритма сортировочной станции, и калькулятор (мы же все здесь за этим собрались?) будет доделан до конца.

© Habrahabr.ru