Алгоритм сортувальної станції
Алгоритм сортувальної станції — метод синтаксичного розбору математичних виразів наданих в інфіксній нотації. Його можна використовувати для отримання інверсного польського запису (ПОЛІЗ) або абстрактного синтаксичного дерева. Алгоритм було винайдено Дейкстрою і названо алгоритм «сортувальної станції», бо ця операція нагадує дію залізничної сортувальної станції.
Як обчислювач ПОЛІЗ, алгоритм сортувальної станції — це стековий алгоритм. Інфіксні форму виразів використовує більшість людей, наприклад 3+4 або 3+4*(2−1). Для перетворення використовуються дві текстові змінні (рядки), вхідний і вихідний. Також задіюється стек, що містить оператори ще не додані в вихідну чергу. Для перетворення програма посимвольно читає початкові дані й виконує дії виходячи з прочитаного символу.
- Початкові дані: 3+4
- Додаємо 3 до черги на виході (щоразу як читається число, воно записується на вихід)
- Заштовхується + (або його ID) у стек операторів
- Додаємо 4 до черги на виході
- По прочитанню виразу виштовхуємо оператор зі стеку та додаємо його до вихідної черги.
- Наразі він лиш один, «+».
- Вихід 3 4 +
Тут ми вже побачили пару правил:
- Всі числа додаються до виходу одразу по прочитанню.
- Наприкінці всього виразу, виштовхуємо всі оператори зі стеку й додаємо їх до черги на виході.
- Допоки на вході ще є позначки:
- Прочитати позначку.
- Якщо це число, додати до черги на виході.
- Якщо це позначка функції, тоді заштовхнути його у стек.
- Якщо позначка — це відокремлювач аргументів функції (наприклад, кома):
- Доки позначка на верхівці стеку це не ліва дужка, виштовхувати зі стеку оператори до черги на виході. Якщо ліва дужка так і не зустрілась, тоді або відокремлювач не на своєму місці, або пропущені дужки.
- Якщо позначка — це оператор, o1, тоді:
- доки на верхівці стеку оператор, o2, і
- або o1 ліво-асоціативний і його першість менша ніж чи дорівнює першості o2,
- або o1 право-асоціативний і першість менша ніж у o2,
- виштовхнути o2 зі стеку до черги на виході;
- заштовхнути o1 на стек.
- Якщо позначка це ліва дужка, заштовхнути на стек.
- Якщо права дужка:
- Допоки не зустрінеться ліва дужка, виштовхувати оператори зі стека до черги на виході.
- Виштовхнути ліву дужку зі стеку, але не до черги на виході.
- Якщо позначка на верхівці стеку — це позначка функції, виштовхнути її до черги на виході.
- Якщо стек завершився, а ліва дужка не зустрілась, тоді вона була пропущена.
- Коли вже немає позначок на вході:
- Доки ще є оператори в стеці:
- Якщо оператор на верхівці стеку — це дужка, значить була пропущена дужка.
- Виштовхнути оператори до черги на виході.
- Вихід.
Для розбору складності цього алгоритму за часом виконання, можна спостерегти, що кожна позначка буде прочитана один раз, кожне число, функція чи оператор буде надрукована один раз і кожна функція, оператор або дужка буде заштовхнута на стек і виштовхнута звідти один раз — отже, не більше сталої кількості операцій буде виконано з кожною позначкою, звідси час виконання O(n) — лінійний щодо розміру вхідних даних.
Алгоритм сортувальної станції також можна застосовувати для отримання префіксного запису (також відомого як польська нотація). Для цього необхідно почати з даного рядка в зворотному напрямку, і тоді розвернути чергу на виході(внаслідок чого перетворивши чергу на виході на стек на виході).
//алгоритм сортувальної станції
string shuntingYard(const string& input)
{
Stack<char> stack;
string output("");
unsigned length = input.length();
for (unsigned i = 0; i < length; ++i)
{
//перевірка чи вхідний символ є частиною числа(врахування унарного '-')
if (isNumber(input[i]) || (input[i] == '-' && i == 0) || (i > 0 && input[i-1] == '(' && input[i] == '-'))
{
//перевірка це останній символ числа,щоб поставити після нього пробіл
if(i + 1 == length || isOperator(input[i+1]) || input[i+1] == '(' || input[i+1] == ')')
{
output = output + input[i] + ' ';
}
else
{
output = output + input[i];
}
}
else if (input[i] == '(')
{
stack.push('(');
}
else if (input[i] == ')')
{
while (stack.top() != '(')
{
output = output + stack.pop()+ ' ';
}
stack.pop();
}
else if (isOperator(input[i]))
{
while (!stack.isEmpty() && (opPreced(stack.top()) >= opPreced(input[i])))
{
output = output + stack.pop() + ' ';
}
stack.push(input[i]);
}
else
{
//помилка вхідних даних
throw "Помилка вхідних даних";
}
}
//виводимо символи що залишились у стеку
unsigned stackSize = stack.size();
if (stackSize > 0)
{
for (unsigned i = 0; i < stackSize - 1; ++i)
{
output = output + stack.pop() + ' ';
}
output = output + stack.pop();
}
return output;
}
// Функція для визначення пріоритету операцій
unsigned opPreced(const char ch)
{
switch(ch)
{
case '^':
return 3;
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
}
// для випадку вхідного символу '('
return 0;
}
bool isNumber(char ch)
{
return (('0' <= ch) && (ch <= '9')) || (ch == '.');
}
bool isOperator(char ch)
{
return (ch == '+' || ch == '-' || ch == '/' || ch == '*' || ch == '^');
}