Leetcode 150 Evaluate Reverse Polish Notation

Soru

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are ‘+’, ‘-’, ‘*’, and ‘/’. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be any division by zero. The input represents a valid arithmetic expression in a reverse polish notation. The answer and all the intermediate calculations can be represented in a 32-bit integer.

Örnek 1

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Örnek 2

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Örnek 3

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Çözüm

• Ters Polonyalı gösterimde (veya post-fix notasyonunda) verilen bir dizi operatör ve operandın değerini hesaplamanızı ister. Bu gösterimde, operatörler operandların hemen arkasından gelir, bu da hesaplamayı parantez kullanmadan ve işlem önceliğini dikkate almadan yapmanıza olanak tanır.
• Girdi: Bir string dizisi olarak verilen operatörler (+, -, *, /) ve operandlar.
• Bu problem genellikle bir yığın (stack) kullanılarak çözülür. Operandlar yığına eklenir; bir operatör geldiğinde, yığından iki operand çıkarılır, operatör bu iki operand üzerinde uygulanır ve sonuç tekrar yığına eklenir. Bu süreç, ifadenin sonuna kadar devam eder.
• Çalışma Mekanizması:
• Yığın İnitialize Edilmesi: Bir yığın oluşturulur.
• İterasyon: Girdi olarak verilen tokenlar üzerinde döngü yapılır.
• Operatör Kontrolü: Token bir operatörse, yığından iki eleman çıkarılır ve ilgili aritmetik işlem yapılır. İşlem sonucu yığına geri eklenir.
• Operand Kontrolü: Eğer token bir sayıysa, doğrudan yığına eklenir.
• Sonuç: İşlemler tamamlandığında, yığındaki son eleman çıkarılır ve bu değer ifadenin sonucu olarak döndürülür.

Code

class Solution:
    def evalRPN(self, tokens):
        stack = []
        
        for token in tokens:
            if token in "+-*/":
                b, a = stack.pop(), stack.pop()  # İkinci çıkan, işlemde ilk operand olmalı
                if token == '+':
                    stack.append(a + b)
                elif token == '-':
                    stack.append(a - b)
                elif token == '*':
                    stack.append(a * b)
                elif token == '/':
                    # Python'da tam sayı bölmesi yuvarlama işlemini yukarıya değil, sıfıra doğru yapar
                    stack.append(int(a / b))
            else:
                stack.append(int(token))  # Operand yığına eklenir
        
        return stack.pop()  # Son eleman sonuçtur

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n token dizisinin uzunluğudur. Her token için sabit zaman harcanır.
• Space complexity (Alan Karmaşıklığı) : O(n), en kötü durumda tüm tokenlar sayı olabilir ve bunlar yığına eklenir.