Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumstack-parsing

Evaluate Reverse Polish Notation

Problem (yeniden ifade)

Reverse Polish notation’daki bir aritmetik ifadeyi değerlendir. Token’lar tamsayı veya +, -, *, / (sıfıra doğru kes).

Sezgi

Postfix: sayıları push et; operatörde iki tane pop et, uygula, sonucu push et.

Yaklaşımlar

Yığın ile değerlendirme

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. değer yığını; op(a,b) sırası b sonra a.

Yürüyüş. [“2”,“1”,“+”,“3”,“*”] → ((2+1)*3)=9.

Trade-off. Öncelik ayrıştırması gerekmez, RPN zaten sıralı.

Çözüm

export function evalRPN(tokens: string[]): number {
  const st: number[] = [];
  for (const t of tokens) {
    if (t === "+" || t === "-" || t === "*" || t === "/") {
      const b = st.pop()!, a = st.pop()!;
      if (t === "+") st.push(a + b);
      else if (t === "-") st.push(a - b);
      else if (t === "*") st.push(a * b);
      else st.push(Math.trunc(a / b));
    } else st.push(Number(t));
  }
  return st[0]!;
}

export function evalRPN(tokens: string[]): number {
  const st: number[] = [];
  for (const t of tokens) {
    if (t === "+" || t === "-" || t === "*" || t === "/") {
      const b = st.pop()!, a = st.pop()!;
      if (t === "+") st.push(a + b);
      else if (t === "-") st.push(a - b);
      else if (t === "*") st.push(a * b);
      else st.push(Math.trunc(a / b));
    } else st.push(Number(t));
  }
  return st[0]!;
}

Şablon bağlantısı

Stack-parsing ifade değerlendirmesi.

Yansıma

- ve / sıra ister. a b - = a−b. İkinci pop edilen soldur.
Bölme sıfıra doğru keser. Python // negatifte TS/C# trunc ile aynı değil.
İfade geçerliyse yığında tek sayı kalır. Eksik operand yığını boşaltır.