Всем привет! Сегодня хочу поделиться опытом написания консольного инженерного калькулятора, который может посчитать выражение вроде (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;
}Заключение
Надеюсь, было интересно. В следующей статье, как было обещанно, будет моя реализация Алгоритма сортировочной станции, и калькулятор (мы же все здесь за этим собрались?) будет доделан до конца.
Megobari
Круто)
Некоторые фирмы начинали с калькуляторов!
https://education.ti.com/en/products?category=graphing-calculators#!product%3Dgraphing-calculators
UmarNur Автор
Интересно, спасибо! Не знал, что Texas Inst. начинал именно с калькуляторов