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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Як обчилювач ПОЛІЗ, алгоритм сортувальної станції це стековий алгоритм. Інфіксні форму виразів використовує більшість людей, наприклад 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 +

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

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

Подробиці алгоритму[ред.ред. код]

  • Прочитати позначку.
  • Якщо це число, додати до черги на виході.
  • Якщо це позначка функції, тоді заштовхнути його у стек.
  • Якщо позначка — це відокремлювач аргументів функції (наприклад, кома):
  • Доки позначка на верхівці стеку це не ліва дужка, виштовхувати зі стеку оператори до черги на виході. Якщо ліва дужка так і не зустрілась, тоді або відокремлювач не на своєму місці, або пропущені дужки.
  • Якщо позначка — це оператор, o1, тоді:
  • доки на верхівці теку оператор, o2, і
або o1 ліво-асоціативний і його першість менша ніж чи дорівнює першості o2,
або o1 право-асоціативний і першість менша ніж у o2,
виштовхнути o2 зі стеку до черги на виході;
  • заштовхнути o1 на стек.
  • Якщо позначка це ліва дужка, заштовхнути на стек.
  • Якщо права дужка:
  • Допоки не зустрінеться ліва дужка, виштовхувати оператори зі стека до черги на виході.
  • Виштовхнути ліву дужку зі стеку, але не до черги на виході.
  • Якщо позначка на верхівці стеку — це позначка функції, виштовхнути її до черги на виході.
  • Якщо стек завершився, а ліва дужка не зустрілась, тоді вона була пропущена.
  • Коли вже немає позначок на вході:
  • Доки ще є оператори в стеці:
  • Якщо оператор на верхівці стеку — це дужка, значить була пропущена дужка.
  • Виштовхнути оператори до черги на виході.
  • Вихід.

Для розбору складності цього алгоритму за часом виконання, можна спостерігти, що кожна позначка буде прочитана один раз, кожне число, функція чи оператор буде надрукована один раз і кожна функція, оператор або дужка буде заштовхнута на стек і виштовхнута звідти один раз — отже, не більше сталої кількості операцій буде виконано з кожною позначкою, звідси час виконання 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 == '^');
}

Посилання[ред.ред. код]