LeetCode 224 बेसिक कैलकुलेटर: पायथन में स्टैक समाधान एक ट्रेस के साथ

LeetCode 224, Basic Calculator, आपसे एक ऐसी स्ट्रिंग का मूल्यांकन करने के लिए कहता है जिसमें अंक, +, -, कोष्ठक और स्पेस हों, बिना eval का उपयोग किए। इसमें गुणा या भाग नहीं है, इसलिए ऑपरेटर प्राथमिकता संभालने की ज़रूरत नहीं। एकमात्र कठिनाई कोष्ठक हैं, और सहेजी गई अवस्थाओं का एक स्टैक इसे एक ही पास में साफ़-सुथरे ढंग से संभाल लेता है।

समस्या

एक स्ट्रिंग s दी गई है जो गैर-ऋणात्मक पूर्णांकों, +, -, (, ), और स्पेस वाले एक व्यंजक को दर्शाती है — इसका मान लौटाइए। ऋण चिह्न एक यूनरी ऑपरेटर भी हो सकता है, जैसे -(2 + 3) में।

उदाहरण:

मुख्य विचार

बाएँ से दाएँ स्कैन कीजिए और तीन चीज़ें बनाए रखिए: चलता हुआ परिणाम, वर्तमान चिह्न, और बनती हुई संख्या। जब आप ( पर पहुँचें, तो आप एक उप-व्यंजक शुरू करने वाले हैं। कोष्ठक के सामने वाले परिणाम और चिह्न को स्टैक पर सहेजिए, फिर परिणाम 0 और चिह्न +1 के साथ नए सिरे से शुरू कीजिए। जब आप ) पर पहुँचें, तो उप-व्यंजक पूरा कीजिए, उसे सहेजे गए चिह्न से गुणा कीजिए, और सहेजे गए परिणाम में जोड़ दीजिए।

हर अक्षर को संभालिए:

अंत में, आख़िरी sign * num जोड़ दीजिए।

def calculate(s):
    result, sign, num = 0, 1, 0
    stack = []
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-":
            result += sign * num
            num = 0
            sign = 1 if ch == "+" else -1
        elif ch == "(":
            stack.append(result)
            stack.append(sign)
            result, sign = 0, 1
        elif ch == ")":
            result += sign * num
            num = 0
            result *= stack.pop()   # the sign before the parenthesis
            result += stack.pop()   # the result before the parenthesis
    return result + sign * num

पॉप का क्रम मायने रखता है: चिह्न सबसे आख़िर में पुश हुआ था, इसलिए वह सबसे पहले पॉप होता है।

ट्रेस

व्यंजक: 1-(2+3)।

1 - (2 + 3) = -4, जो मेल खाता है।

यूनरी माइनस

शुरुआत में आने वाला माइनस बिना किसी विशेष कोड के काम करता है। शुरुआत में, num 0 है, इसलिए पहला - परिणाम में sign * 0 जोड़ता है, फिर चिह्न को -1 पर सेट कर देता है। यही बात ( के बाद भी लागू होती है: सहेजी गई अवस्था result को 0 और sign को +1 पर रीसेट कर देती है, इसलिए (-2) भी उसी तरह संभाला जाता है।

जटिलता

• समय: O(n), स्ट्रिंग पर एक पास।
• स्पेस: गहराई से नेस्टेड कोष्ठकों के लिए सबसे ख़राब स्थिति में O(n), क्योंकि स्टैक हर खुले कोष्ठक के लिए दो मान रखता है।

मैंने इस फ़ंक्शन को नेस्टेड कोष्ठकों और यूनरी माइनस चिह्नों वाले 4,000 यादृच्छिक व्यंजकों पर परखा, Python के अपने मूल्यांकन से तुलना की, और सभी मेल खाए।

विकल्प: रिकर्शन

आप एक रिकर्शिव फ़ंक्शन भी लिख सकते हैं जो एक व्यंजक को पार्स करता है और ( मिलने पर ख़ुद को कॉल करता है। यह पढ़ने में स्वाभाविक लगता है, लेकिन गहराई से नेस्टेड इनपुट पर रिकर्शन सीमा तक पहुँचने का जोखिम रहता है, इसलिए Python में स्टैक वाला संस्करण ज़्यादा सुरक्षित है।

इंटरव्यूअर जो एक्सटेंशन पूछते हैं

एज केस

आम गलतियाँ

1. हर अंक को अपनी अलग संख्या मान लेना।
2. अंत में आख़िरी sign * num जोड़ना भूल जाना।
3. ग़लत क्रम में पॉप करना।
4. ऑपरेटर के बाद num को रीसेट न करना।
5. शुरुआती माइनस को ग़लत संभालना।

इंटरव्यू में इसे कैसे समझाएँ

1. अनुमत अक्षरों को स्पष्ट कीजिए, और यह कि यूनरी माइनस आता है या नहीं।
2. कहिए कि प्राथमिकता की कोई समस्या नहीं है, इसलिए कोष्ठक ही एकमात्र चुनौती हैं।
3. तीन वेरिएबल और स्टैक क्या सहेजता है, इसका वर्णन कीजिए।
4. व्हाइटबोर्ड पर 1-(2+3) को चरण-दर-चरण समझाइए।
5. जटिलता बताइए, फिर Calculator II एक्सटेंशन का ज़िक्र कीजिए।

संबंधित अभ्यास

जटिलता की शब्दावली के लिए हमारी Big O चीट शीट देखिए, AI LeetCode ट्यूटर गाइड, और कोडिंग इंटरव्यू सहायक गाइड। Valid Parentheses और Decode String भी वही स्टैक विचार इस्तेमाल करते हैं।

अभ्यास करते समय अपना ट्रेस ज़ोर से बोलिए। एक मॉक इंटरव्यू ट्रांसक्रिप्ट दिखाता है कि आपने स्टैक का उद्देश्य समझाया या नहीं। किसी भी लाइव असेसमेंट में AI टूल्स पर नियोक्ता के नियमों का पालन कीजिए।