Evaluate Reverse Polish Notation

Q: Ters Lehçe Gösterimini Değerlendirme işleminin zaman karmaşıklığı nedir?

Yığın çözümü n belirteç için O(n) zamanda çalışır: her sayı bir kez yığına eklenir ve her operatör iki öğeyi çıkarıp bir öğe ekler. Yığın yaklaşık n/2 değer tutabilir, dolayısıyla alan karmaşıklığı O(n) 'dir. İlk operatörü tekrar tekrar birleştirmek O(n²) zaman alır; çünkü her turda arama yeniden baştan yapılır.

Q: 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 öncelik kuralı veya parantezler gerekir. Ters Lehçe gösteriminde bir işlemci, her zaman hemen önündeki iki değere uygulanır; dolayısıyla belirteçlerin sırası her şeyi anlatır: 3 4 2 * + 11, 3 4 + 2 * ise 14 eder. Bu nedenle tek bir yığın, hiç ileriye bakmadan ifadeyi değerlendirebilir.

Q: Sıfıra doğru kesme yaparak Python'da nasıl bölme işlemi 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. Değerler 32 bite sığdığı için burada kayan noktalı bölme yeterince kesindir. İstediğiniz büyüklükteki tam sayılar için mutlak değerleri // ile bölün ve ardından işareti geri koyun.

OrtaYığın

+10

Bir dizi belirteç olarak, ters Lehçe gösteriminde bir aritmetik ifade alırsınız. Bu gösterimde her işleç iki işleneninden hemen sonra gelir; bu nedenle 3 4 +, 3 + 4 anlamına gelir ve 3 4 + 2 *, parantez gerektirmeden (3 + 4) * 2 anlamına gelir. Her belirteç bir tam sayı ya da +, -, * ve / işleçlerinden biridir.

İfadeyi değerlendirip değerini döndürün. Bölme yalnızca tam sayı kısmını alır ve sıfıra doğru keser: 7 / 2, 3 eder ve -7 / 2, -3 eder.

Fonksiyon

evalRPN(tokens: string-array) → integer

tokensstring-array: ifadenin sayıları ve operatörleri, sırasıyla
Döndürürinteger: ifadenin değeri

Kısıtlar

1 ≤ tokens.length ≤ 10⁴
Her belirteç +, -, *, / ya da -200 ile 200 arasında, ondalık biçimde yazılmış ve negatifse başında eksi işareti bulunan bir tam sayıdır.
tokens, ters Lehçe gösteriminde geçerli bir ifadedir.
Sıfıra bölme gerçekleşmez ve tüm ara değerler ile son değer -2³¹ değerinden büyük, 2³¹ değerinden küçüktür.

Örnekler

Girdi: tokens = ["8", "3", "-", "4", "*"]
Çıktı: 20
Açıklama: -, sıralarına göre kendisinden önce gelen iki sayıya, yani önce 8'e sonra 3'e uygulanır; bu nedenle -5 değil, 5 verir. Ardından *, bu 5'i 4 ile çarpar ve 20 verir.

Girdi: tokens = ["6", "2", "9", "3", "/", "-", "*"]
Çıktı: -6
Açıklama: İlk işleç olan /, en son iki değeri kullanır: 9 bölü 3, 3 eder. Ardından -, 2’den bu 3’ü çıkarır; sonuç -1 olur ve *, 6’yı -1 ile çarpar.

Girdi: tokens = ["10", "-7", "2", "/", "+"]
Çıktı: 7
Açıklama: -7 belirteci bir sayıdır, işleç değildir. -7 bölü 2, -3,5 eder; bu değer aşağı yuvarlanarak -4 olmaz, sıfıra doğru kesilerek -3 olur ve 10 artı -3, 7 eder.

Gönderirken +18 gizli test

Ek soru

İfadeyi, yalnızca anlamı değiştirdikleri yerlerde parantez ekleyerek (3 + 4) * 2 gibi sıradan gösterimle yeniden oluşturabilir misin?

Çözüm

Ters Lehçe gösterimi, parantez gerektirmez; çünkü belirteçlerin sırası işlemlerin sırasını zaten belirler: her operatör, hemen önündeki iki değere uygulanır ve bu değerlerden biri önceki bir operatörün sonucu olabilir. Bir değer yığını, ifadenin tamamını soldan sağa tek geçişte değerlendirir. Dikkat edilmesi gereken ayrıntılar şunlardır: - ve / için işlenenlerin sırası, - operatörünü -7 sayısından ayırt etmek ve sıfıra doğru kesen bölme.

İlk operatörü daralt, tekrarla

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Bunu kâğıt üzerinde şöyle hesaplardın. En soldaki işleç operatörünü bul. Ondan önce hiçbir işleç yoktur; bu yüzden hemen önündeki iki belirteç düz sayılardır ve onun işlenenleridir. Sonucu hesapla ve bu üç belirteci tek bir sayıyla değiştir. İfade artık daha kısadır ve hâlâ aynı anlama gelir. Tek bir sayı kalana kadar tekrarla.

["6", "2", "9", "3", "/", "-", "*"] ifadesini ele alalım. İlk operatör / olduğundan, 9 3 / ifadesi 3 olur: ["6", "2", "3", "-", "*"]. Ardından 2 3 - ifadesi -1 olur: ["6", "-1", "*"]. Sonra 6 -1 * ifadesi -6 olur; cevap budur.

Bu yöntem doğrudur; çünkü her turda a b op biçimindeki eksiksiz bir parça değeriyle değiştirilir ve sonraki operatörler bu değeri, parçanın bulunduğu yerde görür. Yavaştır; çünkü her turda arama yeniden baştan başlar ve ardından dizinin ortasındaki bir boşluk kapatılır. Sonunda 4.999 operatör bulunan 5.000 sayı olduğunda, ilk operatör 4.999 turun tamamında yaklaşık olarak dizinin ortasında yer alır; bu yüzden yalnızca aramalar yaklaşık 1.25 × 10^7 belirteci kontrol eder. Operatörün solundaki sayılar bir turdan diğerine neredeyse hiç değişmez, ancak her turda yeniden okunurlar.

Algoritma

Belirteçleri değiştirebileceğin bir listeye kopyala.
Baştan başlayarak k konumundaki ilk işleci bulana kadar tara.
İşleci, k-2 (sol) ve k-1 (sağ) konumlarındaki sayılara uygula.
k-2, k-1 ve k konumlarındaki üç belirteci sonuçla değiştir.
Tek 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

Yığma yaklaşımı, operatörün solundaki sayıları tekrar tekrar okumayı gerektirir. Bunun yerine sayıları bir yığında tut. Belirteçleri soldan sağa, bir kez oku. Bir sayı yığına eklenir. Bir operatör, yığının en üstündeki iki değeri alır, bunları birleştirir ve sonucu yığına geri koyar; burada, diğer tüm değerler gibi bir sonraki operatörü bekler.

["6", "2", "9", "3", "/", "-", "*"] dizisini adım adım inceleyelim. Dört sayı yığına eklenir: [6, 2, 9, 3]. /, önce 3'ü, ardından 9'u çıkarır ve 9 / 3 = 3 sonucunu ekler: [6, 2, 3]. -, önce 3'ü, ardından 2'yi çıkarır ve 2 - 3 = -1 sonucunu ekler: [6, -1]. *, önce -1'i, ardından 6'yı çıkarır ve 6 * -1 = -6 sonucunu ekler. Geriye tek bir değer kalır ve cevap budur.

İşe yaramasının nedeni: yığın, her an, şimdiye kadar okunan eksiksiz parçaların değerlerini sıralarıyla birlikte tutar ve bir operatör her zaman bunların son ikisine uygulanır. Yığının en üstündeki değer sağ operanddır, çünkü en son o üretilmiştir; bu yüzden önce onu çıkar. Bu sırayı yanlış belirlemek yalnızca - ve / işlemlerinde sorun yaratır; bu işlemlerde 8 3 - sonucu -5 değil, 5 olmalıdır.

Bazı dillerde bölme konusunda dikkatli olmak gerekir. İfade sıfıra doğru keser; ancak Python'daki //, Ruby'deki / ve R'deki %/% aşağı yuvarlar; bu da -3.5'i -4'e dönüştürür. Her sayı bir kez eklenir ve her operatör iki değeri çıkarıp bir değer ekler; bu nedenle tek geçiş O(n) zaman alır ve yığın hiçbir zaman n değerinden fazlasını tutmaz.

Algoritma

Boş bir yığınla başla.
Sayı olan her belirteç için değerini yığına ekle.
Her işleç için önce sağ işleneni, ardından sol işleneni yığından çıkar.
left op right işlemini hesapla; / için sıfıra doğru yuvarla ve sonucu yığına ekle.
Son belirteçten sonra yığındaki tek değeri döndür.

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

Yığın döngüsü kısadır; yanlış yanıtların çoğu, işlenenlerin sırasından ve bir dilde bölme işleminin nasıl yapıldığından kaynaklanır.

İşlenenlerin sırasını değiştirmek. İlk çıkarılan değer sağ işlenendir: ["3", "5", "-"] sonucu -2, ["2", "9", "/"] sonucu ise 4 değil, 0'dır.
İşleçleri ilk karakterlerine göre belirlemek. -7 eksi işaretiyle başlar ama bir sayıdır. Token'ın tamamını karşılaştırın veya tek karakter uzunluğunda olup olmadığını kontrol edin.
Kesmek yerine aşağı yuvarlamak. -7 / 2 sonucu -3, -1 / 3 sonucu ise 0 olmalıdır. Python'daki //, Ruby'deki /, R'deki %/% ve Lua'daki math.floor -4 ve -1 sonuçlarını verir.
-0 yazdırmak. JavaScript ve Lua'da her sayı bir kayan noktalı sayıdır; bu nedenle 0 * -5 ve Math.trunc(-1 / 3) negatif sıfır üretir ve bu değer -0 olarak yazdırılır. Son değere 0 ekleyerek bunu 0'a dönüştürün.
Bir sayıyı her seferinde tek basamak okuyarak ayrıştırmak. 13 ve -200 gibi token'lar birden fazla karakterden oluşur; token'ın tamamını ayrıştırın.
Son token'ın bir işleç olduğunu varsaymak. ["7"] gibi tek bir sayı, değeri 7 olan geçerli bir ifadedir.

Sıkça sorulan sorular4

Ters Lehçe Gösterimini Değerlendirme işleminin zaman karmaşıklığı nedir?

Yığın çözümü n belirteç için O(n) zamanda çalışır: her sayı bir kez yığına eklenir ve her operatör iki öğeyi çıkarıp bir öğe ekler. Yığın yaklaşık n/2 değer tutabilir, dolayısıyla alan karmaşıklığı O(n)'dir. İlk operatörü tekrar tekrar birleştirmek O(n²) zaman alır; çünkü her turda arama yeniden baştan yapılır.

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 öncelik kuralı veya parantezler gerekir. Ters Lehçe gösteriminde bir işlemci, her zaman hemen önündeki iki değere uygulanır; dolayısıyla belirteçlerin sırası her şeyi anlatır: 3 4 2 * + 11, 3 4 + 2 * ise 14 eder. Bu nedenle tek bir yığın, hiç ileriye bakmadan ifadeyi değerlendirebilir.

Sıfıra doğru kesme yaparak Python'da nasıl bölme işlemi 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. Değerler 32 bite sığdığı için burada kayan noktalı bölme yeterince kesindir. İstediğiniz büyüklükteki tam sayılar için mutlak değerleri // ile bölün ve ardından işareti geri koyun.

T sıradan bir ifadeyi ters Polonya gösterimine nasıl dönüştürürsünüz?

Shunting-yard algoritması bunu, işleçlerden oluşan bir yığınla tek geçişte yapar. Sayılar doğrudan çıktıya gider. Bir işleç yığına eklenmeden önce, yığında bulunan ve önceliği daha yüksek ya da eşit olan tüm işleçler çıktıya taşınır; açılış parantezi yığına eklenir, kapanış parantezi ise eş paranteziyle karşılaşana kadar işleçleri çıktıya taşır. Sonunda, kalan işleçler çıktıya gider.

Python

def evalRPN(tokens):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

tokens = ["8", "3", "-", "4", "*"]

Beklenen