Навука пастаянна развіваецца, тэхналогіі імкліва ўрываюцца ў наша жыццё, з’яўляюцца новыя інструменты і магчымасці, нязменна толькі адно - пануры выраз твару твайго інтэрв’юера. І калі з чытаннем эмоцый інтэрв’юера мы разабраліся, то з чытаннем выразаў у нас усё яшчэ ёсць праблемы. Таму ў дадзеным пасце разбяром самую простую тэму ў кантэксце дадзенай задачы - разбіццё зыходнага радка на асобныя токены.
Як згадвалася ў папярэдніх пастах пра постфіксную натацыю і алгарытм сартавальнай станцыі, мы маем наступныя віды токенаў:
- Знакі арыфметычных аперацый
+, -, *, /; - Круглыя дужкі
(, ); - Рэчаісныя лікі. Для прастаты абмяжуемся толькі лікамі з дзесятковым раздзяляльнікамі і цэлымі лікамі;
- У якасці раздзяляльнікаў токенаў можа выступаць толькі сімвал прабелу.
Створым цела асноўнага метаду на C#. Будзем чытаць выраз сімвал за сімвалам і адразу апрацоўваць. Для нашага выпадку гэтага дастаткова, у іншых выпадках лексічныя аналізатары могуць патрабаваць больш складаных падыходаў. Дадзеная тэма дастаткова добра разгледжана ў той самай кнізе.
Спачатку рэалізуем самы просты варыянт: уваходны радок змяшчае толькі адзін лік, прабелы і аператары адсутнічаюць.
- Пакуль ёсць сімвалы, дадаем сімвалы ў асобнае сховішча, на аснове якіх будзем фарміраваць выніковы лік;
- Калі ў сховішчы ёсць сімвалы, то канвертуем сімвалы ў лік і дадаем у спіс выніковых токенаў.
Ускладнім трохі задачу: дазволім выкарыстанне некалькіх лікаў, якія раздзяляюцца прабеламі. Тады разбіццё на токены можна прадставіць у наступным выглядзе:
Пакуль ёсць сімвалы, аналізуем чарговы сімвал:
Калі сімвал з’яўляецца раздзяляльнікам (прабелам), то канвертуем захаваныя ў сховішчы сімвалы ў лік і дадаем у спіс выніковых токенаў;
Інакш выкарыстоўваем сімвал для фарміравання ліку ў асобным сховішчы;
Калі ў сховішчы засталіся сімвалы, то канвертуем сімвалы ў лік і дадаем у спіс выніковых токенаў.
Дададзім цяпер падтрымку апрацоўкі аператараў. Бо ў нашай пастаноўцы задачы ўсе аператары выражаюцца роўна адным сімвалам, то пры сустрэчы сімвала аператара будзем адразу захоўваць аператар у выніковую паслядоўнасць. Пры гэтым калі ў сховішчы ўтрымліваюцца сімвалы для фарміравання ліку, то канвертуем іх у лік. Тады фінальны алгарытм будзе выглядаць наступным чынам:
- Пакуль ёсць сімвалы, аналізуем чарговы сімвал:
- Калі сімвал з’яўляецца раздзяляльнікам (прабелам), то канвертуем захаваныя ў сховішчы сімвалы ў лік і дадаем у спіс выніковых токенаў;
- Калі сімвал з’яўляецца аператарам, то канвертуем захаваныя ў сховішчы сімвалы ў лік і дадаем у спіс выніковых токенаў, пасля чаго дадаем токен аператара ў выніковы спіс;
- Інакш захоўваем сімвал для фарміравання ліку ў асобным сховішчы;
- Калі ў сховішчы засталіся сімвалы, то канвертуем сімвалы ў лік і дадаем у спіс выніковых токенаў.
Як заўсёды поўную рэалізацыю можна паглядзець на GitHub праекта coding-interview, а гэтым пастом будзем завяршаць тэму разбору матэматычных выразаў. Спадзяюся, што ўсё было пазнавальна і цікава. Да сустрэчы!