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

Hardstack-parsing

Basic Calculator

Problem (yeniden ifade)

+, -, parantez, negatif olmayan tamsayılar ve boşluklarla ifadeyi değerlendir. * veya / yok.

Sezgi

Soldan sağa tara, res ve mevcut sayıyı biriktir. (’de res ve işareti push et, sıfırla; )’de kaydedilmiş işareti uygula ve dış res’i ekle.

Yaklaşımlar

Parantezler için işaret yığını

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. Unary bağlamı işaretli terimler olarak işle. Parantezler iç içe biriktirici açar.

Yürüyüş. “(1+(4+5+2)-3)+(6+8)” → 23.

Trade-off. Çok basamaklı sayılar running num gerektirir; boşluklar no-op.

Çözüm

export function calculate(s: string): number {
  let res = 0;
  let num = 0;
  let sign = 1;
  const stack: number[] = [];
  for (let i = 0; i < s.length; i++) {
    const ch = s[i]!;
    if (ch >= "0" && ch <= "9") {
      num = num * 10 + (ch.charCodeAt(0) - 48);
    } else if (ch === "+" || ch === "-") {
      res += sign * num;
      num = 0;
      sign = ch === "+" ? 1 : -1;
    } else if (ch === "(") {
      stack.push(res);
      stack.push(sign);
      res = 0;
      sign = 1;
    } else if (ch === ")") {
      res += sign * num;
      num = 0;
      res *= stack.pop()!;
      res += stack.pop()!;
    }
  }
  return res + sign * num;
}

export function calculate(s: string): number {
  let res = 0;
  let num = 0;
  let sign = 1;
  const stack: number[] = [];
  for (let i = 0; i < s.length; i++) {
    const ch = s[i]!;
    if (ch >= "0" && ch <= "9") {
      num = num * 10 + (ch.charCodeAt(0) - 48);
    } else if (ch === "+" || ch === "-") {
      res += sign * num;
      num = 0;
      sign = ch === "+" ? 1 : -1;
    } else if (ch === "(") {
      stack.push(res);
      stack.push(sign);
      res = 0;
      sign = 1;
    } else if (ch === ")") {
      res += sign * num;
      num = 0;
      res *= stack.pop()!;
      res += stack.pop()!;
    }
  }
  return res + sign * num;
}

Şablon bağlantısı

İç içe ifadelerin yığın ile parse edilmesi.

Yansıma

Parantez içinin işareti dışarıdakiyle çarpılır. -(a+b) için yığına −1 itilir.
Rakam birikir; operatör veya ) görünce uygulanır. Sondaki sayıyı da ekle.
1-(2-(3)) ve baştaki +. Boşluk yok sayılır.