Evaluate Reverse Polish Notation
Bir dizi belirteç olarak ters Polonya gösteriminde bir aritmetik ifade alırsın. Her operatör iki işleneninden hemen sonra gelir; bu nedenle 3 4 +, 3 + 4 anlamına gelir ve 3 4 + 2 *, parantez olmadan (3 + 4) * 2 anlamına gelir. Her belirteç bir tam sayı ya da +, -, * ve / operatörlerinden biridir.
İfadenin değerini döndür. Bölme sıfıra doğru yuvarlanır: 7 / 2, 3 eder ve -7 / 2, -3 eder.
Fonksiyon
- tokensstring-array
- ifadenin sayıları ve operatörleri, sırasıyla
- Döndürürinteger
- ifadenin değeri
Kısıtlar
1 ≤ tokens.length ≤ 104- Her belirteç
+,-,*,/ya da negatifse başında eksi işareti bulunan ve ondalık biçimde yazılmış -200 ile 200 arasında bir tamsayıdır. tokens, ters Lehçe gösteriminde geçerli bir ifadedir.- Sıfıra bölme gerçekleşmez ve her ara değer ile son değer
-231değerinden büyük,231değerinden küçüktür.
Örnekler
- Girdi
- tokens = ["8", "3", "-", "4", "*"]
- Çıktı
- 20
- Açıklama
-önce 8'e, sonra 3'e uygulanır; bu nedenle -5 değil, 5 sonucunu verir. Ardından*, bu 5'i 4 ile çarpar ve 20 sonucunu verir.
- Girdi
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- Çıktı
- -6
- Açıklama
/en son iki değeri kullanır: 9 bölü 3, 3 eder. Ardından-, 2 eksi 3 işlemini yapar; sonuç -1 olur ve*, 6 ile -1'i çarpar.
- Girdi
- tokens = ["10", "-7", "2", "/", "+"]
- Çıktı
- 7
- Açıklama
-7bir sayıdır, operatör değildir. -7 bölü 2, -3.5 eder; sıfıra doğru kesildiğinde -4 değil, -3 olur ve 10 artı -3, 7 eder.
Ek soru
İfadeyi, yalnızca anlamı değiştirdikleri yerlere parantez ekleyerek, (3 + 4) * 2 gibi alışılmış gösterimle yeniden oluşturabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Belirteçleri soldan sağa oku. Bir işleçle karşılaştığında, hangi iki değere uygulanır? Bu değerlerin üretilme sırasına bak.
Bir operatör her zaman henüz hiçbir operatörün kullanmadığı en son iki değere uygulanır ve sonucu, ardından gelen operatörler için yeni bir değer olur. “Henüz kullanılmamış en son değer” tam olarak bir yığının sana sağladığı şeydir.
Her sayıyı yığına ekle. Bir operatörle karşılaştığında önce sağ işleneni, sonra sol işleneni yığından çıkar; bunları bu sırayla birleştir ve sonucu yığına ekle. Belirteçler tükendiğinde yığında tek bir değer kalır: cevap. Bölme işleminin sıfıra doğru yuvarlandığından emin ol.
Çözüm
Her operatör, hemen önündeki iki değere uygulanır ve bunlardan biri önceki bir operatörün sonucu olabilir. Böylece bir değer yığını, ifadeyi tek geçişte değerlendirir. Dikkat edilmesi gereken noktalar, - ve / için işlenenlerin sırası, - operatörünü -7 sayısından ayırt etmek ve bölme sonucunu kesmektir.
İlk operatörü birleştir, tekrarla
Doğru, ama en büyük testlerde bitmiyor
Sezgi
En soldaki operatörü bulun. Ondan önce hiçbir operatör gelmediğinden, önündeki iki belirteç sayıdır; bunlar operatörün işlenenleridir. Bu üç belirteci sonuçlarıyla değiştirin. Sonraki operatörler, parçanın bulunduğu yerde bu değeri görür; böylece ifade anlamını korur. Geriye tek bir sayı kalana kadar tekrarlayın.
Her turda arama yeniden baştan başlar. 5,000 sayı ve ardından 4,999 operatör olduğunda, ilk operatör her turda yolun yaklaşık yarısında yer alır; bu nedenle yalnızca aramalar yaklaşık 1.25 × 10^7 belirteci okur.
Algoritma
- Belirteçleri değiştirebileceğin bir listeye kopyala.
- Baştan başlayarak
kkonumundaki ilk işleci bulana kadar tara. - İşleci,
k-2(sol) vek-1(sağ) konumlarındaki sayılara uygula. k-2,k-1vekkonumlarındaki üç belirteci sonuçla değiştir.- Bir belirteç kalana kadar tekrarla ve onu sayı olarak döndür.
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])Değerlerden oluşan bir yığınla tek geçiş
Sezgi
Operatörün solundaki değerleri yeniden okumak yerine bir yığında tutun. Bir sayı yığına eklenir. Bir operatör iki değeri çıkarır, bunları birleştirir ve sonucu yığına ekler; sonuç, diğer tüm değerler gibi sıradaki operatörü bekler. Yığın, şimdiye kadar okunan tamamlanmış parçaların değerlerini sırasıyla tutar; bu nedenle bir operatör her zaman en üstteki iki değere uygulanır. En üstteki değer sağ işlenendir, çünkü en son o üretilmiştir.
6 2 9 3 / - * işleminde /, önce 3'ü sonra 9'u çıkarır ve 3'ü ekler; -, önce 3'ü sonra 2'yi çıkarır ve -1'i ekler; * ise 6 × -1 = -6 sonucunu ekler. Her belirteç bir kez işlenir: O(n) zaman ve O(n) alan.
Algoritma
- Boş bir yığınla başlayın.
- Sayı olan her belirteç için değerini yığına itin.
- Her operatör için önce sağ işleneni, ardından sol işleneni yığından çıkarın.
left op rightişlemini hesaplayın;/için sonucu sıfıra doğru yuvarlayın ve sonucu yığına itin.- Son belirteçten sonra yığındaki tek değeri döndürün.
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
Tuzaklar ve uç durumlar
- İşlenenleri yer değiştirmek. İlk pop sağ işlenendir:
["3", "5", "-"]-2 eder ve["2", "9", "/"]4 değil, 0 eder. - Operatörleri ilk karakterlerine göre belirlemek.
-7eksi işaretiyle başlar ama bir sayıdır; bu yüzden belirtecin tamamını karşılaştırın. - Kesmek yerine aşağı yuvarlamak. Python'daki
//, Ruby'deki/, R'deki%/%ve Lua'dakimath.floor,-7 / 2ifadesini -4'e ve-1 / 3ifadesini -1'e dönüştürür. -0yazdırmak. JavaScript ve Lua'da0 * -5veMath.trunc(-1 / 3)negatif sıfır verir. Son değere 0 ekleyin.
Sıkça sorulan sorular4
Evaluate Reverse Polish Notation'ın zaman karmaşıklığı nedir?
Yığın çözümü n token için O(n) zamanda çalışır: her sayı bir kez yığına eklenir ve her operatör iki kez çıkarma, bir kez ekleme işlemi yapar. Yığın yaklaşık n/2 değere kadar tutar, bu nedenle alan karmaşıklığı O(n) olur.
Ters Lehçe gösterimi neden parantez gerektirmez?
Alışılmış gösterimde, 3 + 4 * 2 ifadesinde hangi işlemin önce yapılacağını belirtmek için işlem önceliği kuralı veya parantez gerekir. Ters Lehçe gösterimde bir operatör her zaman hemen önündeki iki değere uygulanır; bu nedenle belirteçlerin sırası sonucu belirler: 3 4 2 * + 11 eder ve 3 4 + 2 * 14 eder.
Python'da sıfıra doğru keserek nasıl bölme yaparsınız?
int(a / b) kullanın. // operatörü aşağı yuvarlar; bu nedenle -7 // 2 sonucu -4 iken int(-7 / 2) sonucu -3 olur. Kayan noktalı bölme, 32 bitlik değerler için yeterince kesindir. Daha büyük tam sayılar için mutlak değerleri // ile bölün ve işareti geri ekleyin.
T sıradan bir ifadeyi ters Polonya gösterimine nasıl dönüştürürsünüz?
Shunting-yard algoritması, operatörlerden oluşan bir yığınla bunu tek geçişte yapar. Sayılar doğrudan çıktıya gider. Bir operatörü yığına eklemeden önce, yığındaki önceliği daha yüksek veya eşit olan tüm operatörleri çıktıya taşı. Kapanış parantezi, açılış parantezi eşine ulaşana kadar operatörleri dışarı taşır. Sonunda geri kalanlar çıktıya gider.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def evalRPN(tokens):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
tokens = ["8", "3", "-", "4", "*"]
Beklenen Çıktı
20