Arifmetik ifodani hisoblash. Dijkstra’ning ikki stack algoritmi

Stack

Avvalgi maqolada Stack haqida ma’lumot berib, uning qo’llanishiga misollar keltirgan edik. Nederland matematigi Edsger Dijkstra (o’qilishi – Daykstra)  arifmetik ifodani hisoblash uchun ikki stack algoritmini (Dijkstra’s two stack algorithm) taklif qilgan.

Misol: ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

Dijkstraga ko’ra sonlar birinchi – qiymat stackga, operatorlar ikkinchi – operator stackga yig’iladi. Ochilgan qavs hisobga olinmaydi, qavs yopilganda birinchi stackdan ikki son va ikkinchi stackdan operator olinib ular o’rtasida hisoblash bajariladi. Shu tariqa ifoda ohiridagi qavsgacha amallar bajariladi.

Ish jarayoni:

Daykstraning ikki stack algoritmi ishlashi
Dijkstraning ikki stack algoritmi ishlash jarayoni

Algoritm complexity – O(n), sababi barcha amallar bitta sikl ichida bajariladi.

Kod:

Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/tree/master/algorithms/dijkstra-two-stack-algorithm

E’tiborga molik:

Hisoblash operator ikki sondan keyin yozilganda ham ishlaydi. Masalan:
( 1 ( ( 2 3 + ) ( 4 5 * ) * ) + )

Biz yuqoridagi kodni biroz o’zgartirib, qavslarni tashlab ketishimiz mumkin.
1 2 3 + 4 5 * * +
Bunday ifoda Reverse polish notation, polish postfix notation yoki shunchaki postfix notation deyiladi. Baxtimizga Dijkstra’ning ikki stack algoritmi kerak bo’ladigan postfix notation masalalar Leetcode’da bor:
https://leetcode.com/problems/evaluate-reverse-polish-notation/

Oddiy matematik ifodaning nomi esa infix notation. Infix notation’ni postfix notationga o’zgartirish uchun Shunting yard algoritmi mos keladi.

Algoritm realizatsiyasining kamchiliklari:

  • ifoda qavs ichida bo’lishi kerak, aks holda hisoblash ohirigacha bajarilmay qoladi.
  • sonlar va amallar probel bilan ajratilishi kerak
  • amallarni qavsga ajratish kerak. Masalan ( 1 + 2 * 3 ) ifodada bitta «( )» bo’lgani uchun ifodaning faqat 2 * 3 qismini hisoblaydi. To’g’ri ifoda (1 + ( 2 * 3 ) ) bo’lishi kerak.

Algoritmni yana qanday masalalar uchun qo’llash mumkin?

Valid parenthesis string  – berilgan matnda ochilgan va yopilgan qavslarning sonini tekshirish uchun. Leetcode’dagi masala: https://leetcode.com/problems/valid-parenthesis-string/

Leetcode’da o’zingizni sinab ko’ring!

* * *

Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.