Алгоритм сортувальної станції

Алгоритм сортувальної станції — метод синтаксичного розбору математичних виразів наданих в інфіксній нотації. Його можна використовувати для отримання інверсного польського запису (ПОЛІЗ) або абстрактного синтаксичного дерева. Алгоритм було винайдено Дейкстрою і названо алгоритм «сортувальної станції», бо ця операція нагадує дію залізничної сортувальної станції.

Як обчислювач ПОЛІЗ, алгоритм сортувальної станції — це стековий алгоритм. Інфіксні форму виразів використовує більшість людей, наприклад 3+4 або 3+4*(2−1). Для перетворення використовуються дві текстові змінні (рядки), вхідний і вихідний. Також задіюється стек, що містить оператори ще не додані в вихідну чергу. Для перетворення програма посимвольно читає початкові дані й виконує дії виходячи з прочитаного символу.

Просте перетворення

Зображення алгоритму, що використовує тригілкове залізничний вузол. Початкові дані опрацьовуються по одному символу за раз, якщо отримана змінна або номер вона копіюється прямо на вихід b), d), f), h). Якщо ж це оператор, він заштовхується в стек операторів c), e), однак, якщо старшинство менше ніж у оператора на верхівці стека або вони мають однакове старшинство й оператор лівоасоціативний, тоді той оператор виштовхується зі стека й записується на вихід g). Насамкінець оператор, що залишились у стеці, виштовхуються і додаються до виходу.

Початкові дані: 3+4

1. Додаємо 3 до черги на виході (щоразу як читається число, воно записується на вихід)
2. Заштовхується + (або його ID) у стек операторів
3. Додаємо 4 до черги на виході
4. По прочитанню виразу виштовхуємо оператор зі стеку та додаємо його до вихідної черги.
5. Наразі він лиш один, «+».
6. Вихід 3 4 +

Тут ми вже побачили пару правил:

• Всі числа додаються до виходу одразу по прочитанню.
• Наприкінці всього виразу, виштовхуємо всі оператори зі стеку й додаємо їх до черги на виході.

Подробиці алгоритму

• Допоки на вході ще є позначки:

• Прочитати позначку.
• Якщо це число, додати до черги на виході.
• Якщо це позначка функції, тоді заштовхнути його у стек.
• Якщо позначка — це відокремлювач аргументів функції (наприклад, кома):

• Доки позначка на верхівці стеку це не ліва дужка, виштовхувати зі стеку оператори до черги на виході. Якщо ліва дужка так і не зустрілась, тоді або відокремлювач не на своєму місці, або пропущені дужки.

• Якщо позначка — це оператор, o₁, тоді:

• доки на верхівці стеку оператор, o₂, і

або o₁ ліво-асоціативний і його першість менша ніж чи дорівнює першості o₂,

або o₁ право-асоціативний і першість менша ніж у o₂,

виштовхнути o₂ зі стеку до черги на виході;

• заштовхнути o₁ на стек.

• Якщо позначка це ліва дужка, заштовхнути на стек.
• Якщо права дужка:

• Допоки не зустрінеться ліва дужка, виштовхувати оператори зі стека до черги на виході.
• Виштовхнути ліву дужку зі стеку, але не до черги на виході.
• Якщо позначка на верхівці стеку — це позначка функції, виштовхнути її до черги на виході.
• Якщо стек завершився, а ліва дужка не зустрілась, тоді вона була пропущена.

• Коли вже немає позначок на вході:

• Доки ще є оператори в стеці:

• Якщо оператор на верхівці стеку — це дужка, значить була пропущена дужка.
• Виштовхнути оператори до черги на виході.

• Вихід.

Для розбору складності цього алгоритму за часом виконання, можна спостерегти, що кожна позначка буде прочитана один раз, кожне число, функція чи оператор буде надрукована один раз і кожна функція, оператор або дужка буде заштовхнута на стек і виштовхнута звідти один раз — отже, не більше сталої кількості операцій буде виконано з кожною позначкою, звідси час виконання O(n) — лінійний щодо розміру вхідних даних.

Алгоритм сортувальної станції також можна застосовувати для отримання префіксного запису (також відомого як польська нотація). Для цього необхідно почати з даного рядка в зворотному напрямку, і тоді розвернути чергу на виході(внаслідок чого перетворивши чергу на виході на стек на виході).

Приклад реалізації на C++

//алгоритм сортувальної станції
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 == '^');
}

Посилання

• Оригінальний опис алгоритму Дейкстрою
• Реалізація на C на сайті Literate Programs