Yığınla ifade işlemleri: parantez, infix → postfix, postfix hesaplama

Hesap makinesine 2 + 3 * 4 yazınca 14 alırsın, 20 değil. Makine öncelik kurallarını nasıl uygular? Cevap: iki yığın algoritması. Önce ifadeyi parantezsiz bir biçime (postfix) çevirir, sonra o biçimi soldan sağa tek geçişte hesaplar. Aynı yığın fikri editörlerin parantez eşleştirmesinde de kullanılır. Sınavda üç soru tipi var: dengeli mi, postfix’e çevir (çoğu zaman yığın tablosuyla), postfix’i hesapla.

Altın kurallar:

1. Açılan son parantez ilk kapanmalı. Yığın tam bunu kontrol eder.
2. Postfix’te işlenenlerin (operand) sırası değişmez. Sadece operatörler yer değiştirir.
3. Yüksek öncelikli operatör yığından önce çıkar.
4. Postfix hesaplarken ilk çekilen sağ işlenendir.

Parantez dengesi (balanced parentheses)

Algoritma: soldan sağa oku. Açılış parantezini it. Kapanış gelince yığın boşsa ya da tepedeki açılış aynı türde değilse dengesiz. Sonda yığın boş değilse dengesiz.

static boolean isBalanced(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (st.isEmpty()) return false;
            char open = st.pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{'))
                return false;
        }
    }
    return st.isEmpty();
}

{[()()]} -> true
([)] -> false
(() -> false
())( -> false
{[]}() -> true
a*(b+c] -> false

Her karakterden sonra yığının hali (soldan sağa: dip → tepe):

input: ( [ ] { } )
(  stack(bottom->top): (
[  stack(bottom->top): ([
]  stack(bottom->top): (
{  stack(bottom->top): ({
}  stack(bottom->top): (
)  stack(bottom->top): (empty)
end: empty -> balanced

TUZAK · Sayı tutmak yetmez. “Açılış sayısı = kapanış sayısı” kontrolü ([)] için evet der ama ifade yanlış. )( için de sayı eşit ama sıra yanlış. Tür ve sıra için yığın şart.

Üç gösterim: infix, postfix, prefix

Postfix’e Reverse Polish Notation (RPN) da denir. Avantajı: öncelik bilgisi sıranın içine gömülüdür, makine soldan sağa okuyup tek yığınla hesaplar.

Elle çevirmenin hızlı yolu: ifadeyi tamamen parantezle, sonra her operatörü kendi kapanış parantezinin yerine taşı. A + B * C → (A + (B * C)) → A B C * +.

İnfix → postfix algoritması

Bir çıktı dizgisi ve bir operatör yığını kullanılır.

Her token için:
  işlenen (harf/sayı)  → çıktıya yaz
  (                    → yığına it
  )                    → ( gelene kadar pop edip çıktıya yaz; ( 'ı at
  operatör op          → yığın boş değil, tepe ( değil VE
                         [ prec(tepe) > prec(op)  ya da  prec(tepe) == prec(op) ve op sola bağlı ]
                         olduğu sürece pop edip çıktıya yaz; sonra op'u it
Sonda: yığında kalanları pop edip çıktıya yaz

Java kodu (tek harfli işlenenler için):

static int prec(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': case '%': return 2;
        case '^': return 3;
    }
    return 0;
}

static String toPostfix(String infix) {
    StringBuilder out = new StringBuilder();
    Deque<Character> st = new ArrayDeque<>();
    for (char c : infix.toCharArray()) {
        if (c == ' ') continue;
        if (Character.isLetterOrDigit(c)) out.append(c);
        else if (c == '(') st.push(c);
        else if (c == ')') {
            while (st.peek() != '(') out.append(st.pop());
            st.pop();                        // ( at
        } else {
            while (!st.isEmpty() && st.peek() != '(' &&
                   (prec(st.peek()) > prec(c) || (prec(st.peek()) == prec(c) && c != '^')))
                out.append(st.pop());
            st.push(c);
        }
    }
    while (!st.isEmpty()) out.append(st.pop());
    return out.toString();
}

Çözümlü iz: A + B * C - D / E

token  stack      output
A      (empty)    A
+      +          A
B      +          AB
*      +*         AB
C      +*         ABC
-      -          ABC*+
D      -          ABC*+D
/      -/         ABC*+D
E      -/         ABC*+DE
end    (empty)    ABC*+DE/-

Kritik an - token’ı: tepede * (öncelik 2 > 1) var, çıkar. Sonra tepede + (eşit öncelik, soldan sağa) var, o da çıkar. Ancak ondan sonra - itilir. / geldiğinde tepedeki - daha düşük öncelikli olduğu için kalır.

Program bir dizi ifadeyi çevirdi:

A+B*C -> ABC*+  maxStack=2
(A+B)*C-D -> AB+C*D-  maxStack=2
A*(B+C)/D-E -> ABC+*D/E-  maxStack=3
A-B-C -> AB-C-  maxStack=1
A^B^C -> ABC^^  maxStack=2
(A+B)*(C-D) -> AB+CD-*  maxStack=3
A+B*(C^D-E)^(F+G*H)-I -> ABCD^E-FGH*+^*+I-  maxStack=6

maxStack, çevirme sırasında yığının ulaştığı en büyük boyuttur; sınavda bazen sorulur.

TUZAK · Sağa bağlı ^. $A^{B^C}$ matematikte $A^{(B^C)}$ demektir. Eşit öncelikte ^ geldiğinde tepedeki ^’ı çıkarırsan AB^C^ yazarsın, bu $(A^B)^C$ olur. Doğrusu ABC^^.

Postfix ifadeyi hesaplama

Bu sefer yığında sayılar var.

Her token için:
  sayı      → it
  operatör  → right = pop(), left = pop(), it(left op right)
Sonda yığında tek sayı kalır: sonuç

static int evalPostfix(String expr) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String tok : expr.trim().split("\\s+")) {
        if (tok.matches("-?\\d+")) st.push(Integer.parseInt(tok));
        else {
            int right = st.pop();
            int left = st.pop();
            switch (tok) {
                case "+": st.push(left + right); break;
                case "-": st.push(left - right); break;
                case "*": st.push(left * right); break;
                case "/": st.push(left / right); break;
            }
        }
    }
    return st.pop();
}

Çözümlü iz: 4 7 2 - * 3 +

Her token sonrası yığın (dip → tepe):

4    4
7    4 7
2    4 7 2
-    4 5
*    20
3    20 3
+    23
23

Kontrol: postfix’i infix’e geri çevir. 7 2 - = (7 − 2), 4 (7−2) * = 4 · 5, 20 3 + = 23. Doğru.

İPUCU · Operand sırası. 9 5 - 2 - için doğru sonuç (9 − 5) − 2 = 2. pop sırasını ters alırsan önce 5 − 9 = −4, sonra 2 − (−4) = 6 bulursun. “İlk çıkan sağa gider” cümlesini ezberle.

Hatalı ifade tespiti: bir operatör geldiğinde yığında iki sayı yoksa ya da sonda birden fazla sayı kalıyorsa ifade bozuktur (3 + gibi).

Sık yapılan hatalar

6    6
2    6 2
3    6 2 3
+    6 5
-    1        (6 - 5)
3    1 3
8    1 3 8
2    1 3 8 2
/    1 3 4    (8 / 2)
+    1 7
*    7

static boolean isBalanced(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.isEmpty()) return false;          // fazladan kapanış
            char open = st.pop();
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{')) return false;   // tür uyumsuz
        }
    }
    return st.isEmpty();                             // açık kalan var mı
}

static int evalPostfix(String expr) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String tok : expr.trim().split("\\s+")) {
        if (tok.matches("-?\\d+")) {
            st.push(Integer.parseInt(tok));
        } else {
            int right = st.pop();    // önce SAĞ
            int left = st.pop();
            switch (tok) {
                case "+": st.push(left + right); break;
                case "-": st.push(left - right); break;
                case "*": st.push(left * right); break;
                case "/": st.push(left / right); break;
            }
        }
    }
    return st.pop();
}

token  stack      output
A      (empty)    A
*      *          A
(      *(         A
B      *(         AB
-      *(-        AB
C      *(-        ABC
)      *          ABC-
+      +          ABC-*
D      +          ABC-*D
end    (empty)    ABC-*D+