Прывітанне, паважаны чытач!

Хто ж, як не мы, прапаленыя жыццём і маніторам распрацоўнікі, ведае які супярэчлівы, цяжкі і несправядлівы гэты свет тэхнічных сумоўяў! Хай твае рашэнні запускаюць касмічныя караблі, або твой сэрвіс утрымлівае мільёны запытаў, дасведчаны інтэрв’юер заўсёды выведзе цябе на чыстую ваду. Не можаш з ходу ўзгадаць розніцу паміж сартаваннем зліццём і ўстаўкамі, не ведаеш на памяць усе SOLID прынцыпы? О, сябар мой, у адрозненне ад цябе інтэрв’юер падрыхтаваўся сур’ёзней і яшчэ з раніцы паўтарыў гэтыя важныя тэмы. Твая некампетэнтнасць відавочна. Пераздача!

Вядома ў наступны раз гэтыя пытанні не заспеюць цябе знянацку, ты сам зараз дзівішся, як чалавек не можа адразу рэалізаваць сартаванне кучай, або на памяць не ведае ўсе правілы балансавання чырвона-чорных дрэў. Цябе зноў клічуць на сумоўе, і якое дзіўнае супадзенне: зноў трапляецца той жа інтэрв’юер. Вось ён момант ісціны, цяпер ты ведаеш пра сартаванні ўсё, ты ўжо гатовы ўдарыць па клавішах, як нечакана чытаеш пастаноўку пытання: “Рэалізаваць парсер матэматычных выразаў”.

Нечакана? Так і ёсць! І таму, каб у гэты раз усё атрымалася, прапаную прама тут і цяпер разабрацца з гэтым пытаннем. Такім чынам, прыступім!

Пастаноўка задачы: рэалізаваць парсер матэматычных выразаў.

Вядома з такой фармулёўкай працаваць складана, таму пажадана на тэхнічных сумоўях прытрымлівацца правіла: спачатку абмеркаваць абмежаванні, потым прыступаць да рэалізацыі. Калі ёсць жаданне ўвесці інтэрв’юера ў стан экстазу, то варта прапанаваць зафіксаваць абмежаванні ў выглядзе набору тэстаў.

Увядзем наступны набор абмежаванняў:

• Выраз не можа ўтрымліваць пераменных або найменных канстант, складаецца толькі з лікаў, арыфметычных знакаў і дужак;
• Даступны наступныя арыфметычныя знакі: +, -, *, /;
• Даступны толькі круглыя дужкі;
• Калі ў выразе ёсць сінтаксічная або вылічальная памылка, то неабходна замест выніку вярнуць паведамленне пра памылку;

Складанасць разбору матэматычных выразаў заключаецца ў тым, што матэматычныя аперацыі маюць розны прыярытэт, які таксама можа змяняцца з дапамогай дужак. Гучыць складана? Насамрэч досыць пераўтварыць выраз з інфік снай натацыі ў постфіксную з дапамогай алгарытму сартавальнай станцыі, выканаць разлік і ўсё! Здаецца, можна на гэтым завяршаць пост, але хутчэй за ўсё злосны інтэрв’юер захоча паглыбіцца ў дэталі, а яшчэ, чаго добрага, запатрабуе рэалізацыі. Таму працягнем.

Інфіксная натацыя - форма запісу матэматычных выразаў, у якой аператары (у нашым выпадку арыфметычныя знакі) запісаны паміж аперандамі (у нашым выпадку лікамі), на якія яны прымяняюцца. Парадак вылічэнняў вызначаецца прыярытэтам аператараў, але можа рэгулявацца дужкамі. Такім чынам, інфіксная натацыя - гэта стандартная форма запісу выразаў, якой нас вывучалі яшчэ ў школе, напрыклад: 1 + (2 - 3) * 4.

Постфіксная натацыя - форма запісу матэматычных выразаў, у якой аператары запісаны пасля аперандаў, на якія яны прымяняюцца. У дадзенай натацыі адсутнічае прыярытэт аперацый, а таму адсутнічаюць дужкі. Напрыклад, выразу вышэй будзе адпавядаць наступны выраз у постфікснай натацыі: 2 3 - 4 * 1 + або 4 2 3 - * 1 +.

Поўную рэалізацыю на C# можна знайсці на GitHub праекта coding-interview, а пакуль разбяром алгарытм вылічэння выразу, які запісаны ў постфікснай натацыі. Створым клас, які на ўваход будзе прымаць паслядоўнае мноства токенаў (аператараў і аперандаў), а на выхадзе будзе вяртаць вынік у выглядзе вылічанага аперанда.

Калі токен з’яўляецца аперандам, то дадаем аперанд у стэк аперандаў.

Калі ж токен з’яўляецца аператарам, то дастаем неабходную колькасць аперандаў са стэку, вырабляем вылічэнне і дадаем вынік вылічэння ў стэк аперандаў. Калі ж у стэку няма неабходнага ліку элементаў для вылічэнні аператара, то сігналізуем пра памылку.

Засталося толькі дадаць рэалізацыю вяртання выніку - адзінага элемента ў стэку. Калі пасля апрацоўкі ўсіх токенаў ў стэку знаходзіцца больш за адзін элемент, то гэта будзе сігналізаваць аб неадпаведнасці паміж аператарамі і аперандамі. Калі ж у стэку няма элементаў, то гэта значыць, што на ўваход была пададзена пустая паслядоўнасць.

На гэтым мне трэба развітвацца, а ўжо ў наступным пасце разбяром рэалізацыю алгарытму сартавальнай станцыі.