Teskari polyak yozuvi (RPN)

Odatda matematik ifodani 2 + 3 yoki (5 + 1) * 4 ko'rinishida yozamiz. Bu yozuv infix deyiladi — operator ikki operand o'rtasida turadi. Lekin bu yozuvning kompyuter uchun qulay bo'lmagan bir xususiyati bor: ifodaning qaysi qismini avval hisoblash kerakligini bilish uchun qavslarni yoki ustuvorlik qoidalarini tushunish shart.

Teskari polyak yozuvi (Reverse Polish Notation, RPN) yoki postfix yozuvi operatorni ikkala operanddan keyin joylashtiradi. Masalan, 2 + 3 postfix shaklida 2 3 +, (2 + 3) * 4 esa 2 3 + 4 * bo'ladi.

Infix:    2 + 3
Postfix:  2 3 +

Infix:    (2 + 3) * 4
Postfix:  2 3 + 4 *

Infix:    5 - (1 + 2) * 4
Postfix:  5 1 2 + 4 * -

Postfix yozuvda qavslar yo'q. Hisoblash tartibi yozuvning o'zidan kelib chiqadi: operand-operand-operator — demak bu ikki operandga shu operator qo'llanadi.

Nima sababdan bunday yozuv kerak?

1950-yillarda elektron kalkulyatorlar va kompilyator dizayni uchun ifodalarni samarali hisoblash usuli kerak edi. Jan Lukasevich 1920-yillarda operator-operand tartibini o'zgartiruvchi yozuv taklif qildi. Keyinchalik Charlz Hembl va Fridrix Bauer teskari (postfix) variantni kalkulyatorlar uchun moslashtirdi. Bu yozuv Dysktra's shunting-yard algoritmi bilan infix ifodalarni postfixga aylantirish uchun ham asosga aylandi.

Postfix yozuvning asosiy afzalligi: u hech qanday qavs yoki ustuvorlik qoidasi talab qilmasdan chapdan o'ngga bir marta o'qib, stack yordamida hisoblab bo'ladi. Shu sababli ba'zi kalkulyatorlar va virtual mashinalar postfix yozuvni ichki ko'rinish sifatida ishlatadi.

Stack bilan hisoblash mantig'i

Postfix ifodani chapdan o'ngga o'qiymiz:

Raqam uchraganida — uni stackka PUSH qilamiz.
Operator uchraganida — stackdan ikkita operandni POP qilamiz, amalni bajaramiz, natijani stackka PUSH qilamiz.

Ifoda to'g'ri yozilgan bo'lsa, barcha tokenlar qayta ishlangach stackda aynan bitta qiymat qoladi — bu yakuniy natija.

FUNCTION EVALUATE_RPN(tokens)
    stack = bo'sh stack

    FOR har bir token ichida
        IF token raqam bo'lsa
            stack.PUSH(token)
        ELSE
            right = stack.POP()
            left  = stack.POP()

            IF token = '+'  THEN  stack.PUSH(left + right)
            IF token = '-'  THEN  stack.PUSH(left - right)
            IF token = '*'  THEN  stack.PUSH(left * right)
            IF token = '/'  THEN  stack.PUSH(left / right)

    RETURN stack.POP()

Bosqichma-bosqich dry run

"2 3 + 4 *" — bu (2 + 3) * 4 = 20 ga teng:

Token: 2    → raqam → PUSH    Stack: [2]
Token: 3    → raqam → PUSH    Stack: [2, 3]
Token: +    → operator
                right = POP → 3
                left  = POP → 2
                2 + 3 = 5
                PUSH(5)          Stack: [5]
Token: 4    → raqam → PUSH    Stack: [5, 4]
Token: *    → operator
                right = POP → 4
                left  = POP → 5
                5 * 4 = 20
                PUSH(20)         Stack: [20]

Yakuniy POP → 20

"5 1 2 + 4 * -" — bu 5 - (1 + 2) * 4 = -7 ga teng:

Token: 5    → PUSH    Stack: [5]
Token: 1    → PUSH    Stack: [5, 1]
Token: 2    → PUSH    Stack: [5, 1, 2]
Token: +    → right=2, left=1,  1+2=3, PUSH(3)    Stack: [5, 3]
Token: 4    → PUSH    Stack: [5, 3, 4]
Token: *    → right=4, left=3,  3*4=12, PUSH(12)   Stack: [5, 12]
Token: -    → right=12, left=5, 5-12=-7, PUSH(-7)  Stack: [-7]

Yakuniy POP → -7

Operand tartibiga e'tibor

Qo'shish va ko'paytirish uchun operandlar tartibi muhim emas: a + b = b + a. Lekin ayirish va bo'lish uchun tartib muhim.

Stackdan birinchi POP qilingan qiymat o'ng operand, ikkinchisi esa chap operand bo'ladi. Chunki stackka kechroq qo'shilgan (ya'ni, o'ngda joylashgan) qiymat yuqorida turadi.

"10 3 -"  →  10 - 3 = 7

Token: 10 → PUSH    Stack: [10]
Token: 3  → PUSH    Stack: [10, 3]
Token: -
    right = POP → 3
    left  = POP → 10
    left - right = 10 - 3 = 7 ✓

Agar left va right aralashtirilsa:
    right - left = 3 - 10 = -7 ✗

Warning

Ayirish va bo'lishda left hamisha ikkinchi POP, right hamisha birinchi POP. Bu tartibni teskari yozish ko'paytirish va qo'shishda sezilmaydi, lekin ayirish va bo'lishda noto'g'ri natija beradi.

Butun sonni bo'lish

Bo'lish operatsiyasida nolga bo'lish holati ko'rib chiqilishi kerak. Bundan tashqari, bo'lish natijasi butun sonmi yoki kasr sonmi — bu dasturlash tiliga va masala talabiga bog'liq.

Ko'pchilik RPN masalalarida integer division — ya'ni, natija kasr bo'lsa nolga yaxlitlash talab qilinadi:

"6 -132 /"

right = POP → -132
left  = POP → 6
6 / -132 = -0.0454...

Nolga yaxlitlash: 0
(Bir qismi -1 tomoniga emas, 0 tomoniga yaxlitlanadi)

Musbat va manfiy sonlarni bo'lganda yaxlitlash yo'nalishi dasturlash tilida boshqacha ishlashi mumkin. Masala shartnomasi buni aniq ko'rsatishi kerak.

Vaqt va xotira murakkabligi

n ta token uchun har biri bir marta ko'riladi. Har tokenga PUSH yoki ikki marta POP + PUSH — doimiy miqdordagi ish. Vaqt murakkabligi O(n).

Stack eng ko'pi bilan barcha tokenlar raqam bo'lganida n ta element saqlaydi. Yordamchi xotira O(n).

Amal	Vaqt	Yordamchi xotira
Bir token uchun	`O(1)`	`O(1)`
Butun ifoda	`O(n)`	`O(n)`

Edge case'lar

Bitta raqam. "42" — stack [42] bo'ladi, yakuniy POP → 42. To'g'ri.

Ketma-ket operatorlar. "2 3 4 + *" — stack oldin [2, 3, 4], so'ng [2, 7], so'ng [14]. Bu 2 * (3 + 4) ga teng. To'g'ri yozuv, to'g'ri natija.

Manfiy raqamlar. Tokenlar odatda bo'shliq bilan ajratilgani uchun - belgisi yopishib kelgan raqam bilan operator ekanini kontekstdan aniqlash kerak. "-3 2 +" da -3 son, "3 2 -" da - operator.

Stack kamdan kam to'lishi. Agar ifoda noto'g'ri bo'lsa (masalan, "+ 3"), operator uchraganda stackda ikki operand bo'lmaydi. POP underflowga olib keladi. To'g'ri tuzilgan postfix ifodada bu holat sodir bo'lmaydi.

Yakunida bir nechta element. Agar ifoda noto'g'ri bo'lsa (masalan, "2 3"), oxirida stackda bir nechta element qoladi. Faqat bitta qolish kerak.

RPN va infix o'rtasidagi bog'liq

Infix ifodani postfixga aylantirish uchun Dysktra'ning shunting-yard algoritmi ishlatiladi. U ham stackdan foydalanadi, lekin bu safar operatorlar va qavslar stack orqali qayta tartiblangan holda chiqariladi.

Kompilyatorlar va interpreterlari ko'pincha infix ifodani avval abstract syntax tree (AST) ga, keyin postfix yoki boshqa oraliq ko'rinishga aylantiradi. RPN — bu zanjirning oddiy, lekin muhim bo'g'ini.

Xulosa

Teskari polyak yozuvida ifodani hisoblash stackning operandlar bilan ishlashining to'g'ridan-to'g'ri namunasi. Raqam uchraganda stackka qo'yiladi, operator uchraganda esa kerakli operandlar stack tepasidan olinadi. Ayirish va bo'lishda operandlar tartibini teskari olish eng keng tarqalgan xato.

Stack bu masalada nafaqat vosita, balki postfix yozuvning mantiqiy asosi: postfix ifoda aynan stackga mos tartibda yozilgan.