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

Дадзены алгарытм прызначаны для пераўтварэння выразаў з інфікснай натацыі ў постфіксную. У дадзеным артыкуле не будзе прыводзіцца поўны доказ працы дадзенага алгарытму, а толькі дадзены частковыя тлумачэнні, каб зрабіць рэалізацыю больш інтуітыўна зразумелай.

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

• Пакуль выраз мае токены бярэм чарговы токен:

  • Калі токен з’яўляецца аперандам, то запісваем яго ў выніковую паслядоўнасць;

  • Калі токен з’яўляецца аператарам, то захоўваем яго ў асобным сховішчы;

• Дастаем захаваны токен са сховішча і дадаем яго ў выніковы выраз.

Усё гэта працуе цудоўна да таго моманту, пакуль мы не захочам ўскладніць зыходны выраз і дадаць яшчэ адзін аператар 2 + 3 - 4. У дадзеным выпадку аналагічным постфіксным выразам будзе 2 3 + 4 -. Заўважым, што папярэдні алгарытм не можа захоўваць больш за адзін аператар ў часовым сховішчы, такім чынам мы страцім адзін аператар у працэсе вылічэння і ў выніку атрымаем 2 3 4 -. Гэта не можа не засмучаць, таму паспрабуем унесці паляпшэнне ў наш алгарытм пераўтварэння.

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

Прыгажосць! Але што ж рабіць, калі аператары маюць розны прыярытэт? 2 + 3 * 4 выраз павінны быць пераўтвораны ў выраз 2 3 4 * +, але ж ніяк не ў выраз 2 3 + 4 *. Для далейшага паляпшэння алгарытму разгледзім таксама выраз 2 * 3 + 4 і яго аналаг 2 3 * 4 +. Адсюль мы можам зрабіць выснову, што наш алгарытм не працуе толькі для выпадкаў, калі наступны аператар мае больш высокі прыярытэт, чым папярэдні. Прычым у выпадку, калі наступны аператар мае больш высокі прыярытэт, аператары павінны як бы памяняцца месцамі ў выніковым выразе. Адсюль напрошваецца выснова, што неабходна для сховішча аператараў выкарыстоўваць стэк, таму ўнясем чарговае змяненне ў наш алгарытм:

• Пакуль выраз мае токены бярэм чарговы токен:

  • Калі токен з’яўляецца аперандам, то запісваем яго ў выніковую паслядоўнасць;

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

  • Калі токен з’яўляецца аператарам, то:

    • Пакуль стэк аператараў не пусты, і ў вяршыні стэку ляжыць аператар з не меншым (> =) прыярытэтам, дастаем яго са стэку і запісваем у выніковую паслядоўнасць;

    • Захоўваем токен ў стэк аператараў

• Дастаем захаваны токен са сховішча і дадаем яго ў захаваныя аператары са стэку аператараў і дадаем іх у выніковы выраз.

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

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

• Пакуль выраз мае токены бярэм чарговы токен:

  • Калі токен з’яўляецца аперандам, то запісваем яго ў выніковую паслядоўнасць;

  • Калі токен з’яўляецца аператарам (не дужкай), то:

    • Пакуль стэк аператараў не пусты, і ў вяршыні стэку ляжыць аператар з не меншым (> =) прыярытэтам, дастаем яго са стэку і запісваем у выніковую паслядоўнасць;
    • Захоўваем токен ў стэк аператараў.

  • Калі токен з’яўляецца адкрывальнай дужкай, то захоўваем аператар у стэк аператараў;

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

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

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