Реалізація токенізатора математичних виразів у JS.
Привіт, чудові люди в інтернеті.
Токенізатори — це основа багатьох застосунків: вони розбивають рядок тексту на менші, керовані частини, які називаються "токенами".
У мовах програмування або математичних виразах токенізація означає розбиття коду чи рівнянь на впізнавані елементи, такі як ключові слова, оператори, змінні або значення.
Уявіть, що у вас є вираз, наприклад, "10.5 + 20.75 * 30". Ваше завдання:
- Ідентифікувати числа (
10.5,20.75,30). - Ідентифікувати оператори (
+,*). - Обробити спеціальні випадки, як негативні числа (
-10) або дужки.
Цей токенізатор допоможе розібрати ці вирази на значущі частини для подальшої обробки, наприклад, для оцінки або перевірки синтаксису.
Код, пояснений
Ось код токенізатора:
const tokenizer = (expression) => {
// перевірка, чи є рядок
if(typeof(expression) !== 'string' || expression instanceof String){
return "Expression must be string";
}
const exprLength = expression.length;
// повернути, якщо вираз порожній
if(exprLength === 0)
return null;
// список операндів, які можна використовувати у виразі
const operands = ['+', '-', '*', '/', '(', ')', '^'];
let currentChar = 0;
const result = [];
/**
* у випадку з -10, звичайна реалізація розділить '-' і 10
* але це неправильно, оскільки -10 має розглядатися як один оператор
* для цього ми перевіряємо, чи є останнім токеном '-' і чи йдуть за ним
* числа без пробілів.
*/
let lastToken = null;
const parseOperators = (buffer = '') => {
// Парсинг цілих чисел і десяткових дробів
while(
currentChar < exprLength &&
(
(
expression[currentChar] >= '0' &&
expression[currentChar] <= '9'
) || expression[currentChar] === "." // для врахування дробів
)
){
// додаємо числа до буфера
buffer += expression[currentChar];
currentChar++;
}
if(buffer.length !== 0 && !Number.isNaN(buffer)){
result.push({
type: 'operator',
value: buffer
})
lastToken = result[result.length - 1];
}
}
while(currentChar < exprLength){
// пропускаємо всі пробіли
while(currentChar < exprLength && /\s/.test(expression[currentChar])){
currentChar++;
}
// Обробка операндів
if (currentChar < exprLength && operands.includes(expression[currentChar])) {
// Обробка унарного мінуса (негативні числа)
if (
expression[currentChar] === "-" &&
(
lastToken === null ||
lastToken.type === "operand" ||
lastToken.type === "paren_open"
)) {
currentChar++; // Пропускаємо знак '-' і трактуємо його як частину числа
parseOperators('-'); // парсимо число з '-'
lastToken = result[result.length - 1];
continue;
} else {
// Звичайний операнд
result.push({
type: "operand",
value: expression[currentChar],
});
lastToken = result[result.length - 1];
if (expression[currentChar] === "(") {
lastToken.type = "paren_open"; // маркуємо '(' як особливий тип операнда
}
currentChar++;
continue;
}
}
// Обробка операторів
parseOperators();
}
return result.length !== 0 ? result : null;
}
Як це працює
Перевірка вводу:
- Спочатку токенізатор перевіряє, чи є ввід рядком. Якщо це не так, функція повідомляє, що вираз має бути рядком.
Порожній ввід:
- Якщо ввід є порожнім рядком, токенізатор просто зупиняється і нічого не повертає.
Розпізнавання операторів:
- Токенізатор має список символів, які він розпізнає як спеціальні знаки (наприклад,
+,-,*,/,(,), і^). Це називаються "оператори" або "операнди".
Запуск процесу:
- Токенізатор починає аналізувати вираз по символах.
Токенізатор відстежує своє місце в рядку і зберігає знайдені частини (які називаються "токенами").
Обробка чисел:
- Токенізатор шукає числа, які можуть бути цілими або десятковими (наприклад,
10.5або20.75). Він збирає всі цифри (і десяткову крапку, якщо вона є), щоб сформувати повне число.
Пропуск пробілів:
- Якщо токенізатор натрапляє на пробіли, він їх ігнорує, оскільки пробіли не потрібні для токенізації виразу.
Обробка спеціальних випадків:
- Найскладніша частина — це те, як токенізатор обробляє знак мінус (
-): - Негативні числа: Іноді знак мінус означає, що число негативне (наприклад,
-10). Якщо знак мінус стоїть на початку виразу або відразу після оператора або дужок, токенізатор розуміє, що це частина числа, а не окремий оператор. Він трактує-10як єдиний токен числа. - Віднімання: Якщо знак мінус стоїть між двома числами (наприклад,
10 - 5), токенізатор трактує його як оператор віднімання.
Обробка кожного символа:
- Токенізатор проходить через вираз, символ за символом:
- Якщо він бачить число, він збирає всі цифри та десяткову крапку в один токен.
- Якщо він бачить оператор (наприклад,
+,-,*тощо), він додає його як токен. - Якщо він бачить дужки (
(або)), він трактує їх як спеціальні токени, що позначають початок і кінець групи.
Фінальні токени:
- Після того, як токенізатор пройде через увесь вираз, він повертає масив "токенів". Це частини початкового виразу, тепер акуратно розділені та готові до подальшої обробки (наприклад, для обчислення результату).
Спеціальна обробка знака мінус (-)
- Знак мінус (
-) може бути складним, оскільки він може означати дві речі:
- Негативне число: Якщо він стоїть на початку виразу або після оператора чи дужок, це означає, що число негативне (наприклад,
-10). - Оператор віднімання: Якщо він стоїть між двома числами, це означає віднімання (наприклад,
10 - 5).
- Для правильної обробки токенізатор звертає увагу на контекст знака мінус:
- Якщо після знака мінус йде число, він трактує мінус як частину числа (наприклад,
-10трактуватиметься як один токен:-10). - Якщо знак мінус стоїть між двома числами, він трактує його як оператор віднімання.
Приклад:
console.log(tokenizer("10.5 + 20.75 * 30"));
// Вивід:
// [
// { type: 'operator', value: '10.5' },
// { type: 'operand', value: '+' },
// { type: 'operator', value: '20.75' },
// { type: 'operand', value: '*' },
// { type: 'operator', value: '30' }
// ]
console.log(tokenizer("-10 + (-20.8) - 30"));
// Вивід:
// [
// { type: 'operator', value: '-10' },
// { type: 'operand', value: '+' },
// { type: 'paren_open', value: '(' },
// { type: 'operator', value: '-20.8' },
// { type: 'operand', value: ')' },
// { type: 'operand', value: '-' },
// { type: 'operator', value: '30' }
// ]
console.log(tokenizer("10 ++ 20 ** 30"));
// Вивід:
// [
// { type: 'operator', value: '10' },
// { type: 'operand', value: '+' },
// { type: 'operand', value: '+' },
// { type: 'operator', value: '20' },
// { type: 'operand', value: '*' },
// { type: 'operand', value: '*' },
// { type: 'operator', value: '30' }
// ]
Я завжди прагну до вдосконалення і буду радий почути ваші думки! Якщо у вас є пропозиції, відгуки чи теми, які ви хотіли б, щоб я розглянув, будь ласка, поділіться ними в коментарях нижче. Ваші думки дуже важливі! 🙂
Перекладено з: Tokenizer in JavaScript