Postfix token'larını değerlendir
Görev tanımı
Problem
Bir cep hesap makinesi formülleri, her operatörün iki işleneninden sonra geldiği postfix sırasında saklıyor; yani "3 4 +" 3 + 4 demek ve hiç paranteze gerek kalmıyor. Formül, her biri bir tam sayı ya da +, -, * ve / sembollerinden biri olan token'lardan oluşan bir liste olarak verildiğinde değerini döndür. Bölme sıfıra doğru keser, yani 7 / -2, -3'tür. Formül her zaman geçerli, 1 ile 10.000 arasında token içeriyor, asla sıfıra bölmüyor ve her ara değer işaretli 32 bitlik bir tam sayıya sığıyor.
Örnekler
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Neden: (2 + 1) * 3
Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Neden: 4 + (13 / 5), 13 / 5 de 2'ye kesilir
Input: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Neden: -11 gibi negatif sayılar operatör değil, işlenendir
İpuçları
0 / 3
Bir operatör geldiğinde işlenenleri henüz kullanılmamış en son iki değerdir.
Sayıları bir stack'e push et. Bir operatörde önce sağ işleneni, sonra sol olanı pop et, operatörü uygula ve sonucu geri push et.
- ve / için sıra önemli. Python'un // operatörü eksi sonsuza doğru yuvarlar; bu yüzden sıfıra doğru kesmek için mutlak değerleri böl ve işareti kendin geri koy.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- 1 ≤ tokens.length ≤ 10⁴
- the formula is valid and never divides by zero
- values fit in a 32-bit signed integer
- division truncates toward zero
Çözüm
Postfix sırasında bir operatör her zaman kullanılmamış en son iki değere uygulanır; bir stack'in tepesinin tuttuğu da tam olarak bu. Sayılar push edilir; bir operatör sağ işleneni, sonra sol olanı pop eder ve birleşik değeri push eder; böylece sonda kalan tek değer cevaptır. Tek tuzak bölme: Python'un taban bölmesi -7 // 2'yi -4'e aşağı yuvarlar; bu yüzden bölüm mutlak değerler üzerinden alınır ve işareti geri getirilir, bu da sıfıra doğru keser. Bir token yalnız tam olarak dört sembolden biriyse operatördür, bu yüzden "-11" bir sayı olarak okunur. Zaman ve alan O(n).
def eval_postfix(tokens):
stack = []
for tok in tokens:
if tok not in ("+", "-", "*", "/"):
stack.append(int(tok))
continue
right, left = stack.pop(), stack.pop() # right operand is on top
if tok == "+":
stack.append(left + right)
elif tok == "-":
stack.append(left - right)
elif tok == "*":
stack.append(left * right)
else:
q = abs(left) // abs(right) # truncate toward zero
stack.append(q if (left < 0) == (right < 0) else -q)
return stack[0]
print(eval_postfix(["2", "1", "+", "3", "*"])) # -> 9
print(eval_postfix(["4", "13", "5", "/", "+"])) # -> 6
print(eval_postfix(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) # -> 22Kodda değil de fikirde mi takıldın? Stack temelleri bunu anlatıyor.