022 — Basic Calculator

Source

• Original source: Classic stack-of-contexts exercise
• Platform: LeetCode — https://leetcode.com/problems/basic-calculator/
• Topic: stack (nesting / context)
• Difficulty: Hard
• Pattern: nesting (stack of contexts)
• Basic idea inherited from: Problem 10-এর save-context-on-( restore-on-) চাল — ( এলে এ পর্যন্তের ফলাফল আর sign জমিয়ে রাখো, ) এলে ফিরিয়ে আনো

1. Problem in simple words

তোমাকে একটা গাণিতিক expression string দেওয়া আছে যাতে আছে: অঋণাত্মক পূর্ণসংখ্যা, +, -, খোলা-বন্ধ বন্ধনী ( ), আর কিছু space। (এখানে গুণ-ভাগ নেই — শুধু যোগ, বিয়োগ আর বন্ধনী।) string-টা evaluate করে তার মান বের করো।

"1 + 1"                 -> 2
" 2-1 + 2 "             -> 3
"(1+(4+5+2)-3)+(6+8)"   -> 23
"2-(5-6)"               -> 3   (= 2 - (-1))

2. Which basic idea does this inherit from?

এটা Problem 10 (decode string)-এর জ্ঞাতি — দুটোতেই বন্ধনী একটা nested context তৈরি করে, আর stack সেই context save/restore করে। decode-এ [ এলে এখনকার string আর repeat-সংখ্যা জমিয়ে রাখতে; এখানে ( এলে এ পর্যন্তের যোগফল আর বন্ধনীর-আগের sign জমিয়ে রাখি। ) এলে ভেতরের হিসাব শেষ করে জমানো context ফিরিয়ে এনে মিলিয়ে দিই।

3. What is the hidden math or logic?

লুকানো logic: আমরা বাঁ-থেকে-ডান হেঁটে একটা চলমান result রাখি, আর পরের সংখ্যাটা যোগ হবে না বিয়োগ হবে তা ঠিক করে একটা sign (+1 বা -1)। একটা সংখ্যা শেষ হলেই (পরের operator বা বন্ধনী বা string-শেষে) তাকে result += sign * num দিয়ে মিশিয়ে দিই।

বন্ধনী এই সরল প্রবাহে nesting আনে। (-তে আমরা বাইরের result আর বাইরের sign stack-এ জমিয়ে একটা নতুন পরিষ্কার context (result=0, sign=+1) দিয়ে ভেতরটা শুরু করি। )-তে ভেতরের চূড়ান্ত result বের হয়; তাকে জমানো বাইরের sign দিয়ে গুণ করে জমানো বাইরের result-এ যোগ করি — মানে পুরো বন্ধনীটা যেন একটা একক সংখ্যা হয়ে বাইরের হিসাবে ঢুকে যায়।

4. Which data structure is needed?

একটা stack (Python-এ list) যেখানে প্রতিটা (-তে দুটো জিনিস push করি: বাইরের result, আর বাইরের sign। সাথে তিনটে চলক — চলমান result, চলমান num (এখন যে সংখ্যাটা বানাচ্ছি), আর sign।

5. Why this data structure fits

বন্ধনী মানেই "সবচেয়ে ভেতরের বন্ধনী আগে শেষ হয়" — এটাই LIFO, তাই stack। প্রতিটা ( একটা নতুন স্তর খোলে, প্রতিটা ) সবচেয়ে recent খোলা স্তর বন্ধ করে — ঠিক stack-এর push/pop। বাইরের context (result, sign) stack-এ অপেক্ষায় থাকে যতক্ষণ ভেতরের হিসাব চলে, তারপর হুবহু ফিরে আসে — অন্য কোনো structure-এ এই "শেষ-খোলা আগে-বন্ধ" এত সস্তায় হয় না।

6. Real-life analogy

ভাবো তুমি একটা হিসাব কষছ, হঠাৎ এক বন্ধনী এসে বলল "দাঁড়াও, আগে এই ছোট হিসাবটা আলাদা করে করি"। তুমি এখনকার খাতার যোগফল আর "এই অংশটা যোগ হবে না বিয়োগ" তথ্যটা একটা sticky-note-এ লিখে পাশে রাখলে (push), নতুন একটা পরিষ্কার পাতায় ভেতরের হিসাব শুরু করলে। ভেতরের হিসাব শেষ ()) হলে sticky-note তুলে এনে (pop) ভেতরের ফলটা ঠিক চিহ্ন দিয়ে মূল হিসাবে বসিয়ে দিলে। একাধিক বন্ধনী নেস্ট করলে sticky-note-ও গাদা হয়ে জমে — শেষেরটা আগে তোলো।

7. Visual explanation

(1+(4+5+2)-3)+(6+8) evaluate করার সময় stack (top ডানে) আর চলক:

char  action                                       stack(result,sign)  result  sign
(     push(0,+1); নতুন context                     [0,+1]              0       +1
1     num=1
+     result+=(+1)*1 -> 1; sign=+1                                     1       +1
(     push(1,+1); নতুন context                     [0,+1, 1,+1]        0       +1
4+5+2 ভেতরে যোগ                                                       11      +1
)     result+=2 ->11; *pop sign(+1)=11; +pop res(1)=12  [0,+1]        12      +1
-     result(12); sign=-1                                             12      -1
3     num=3
)     result+=(-1)*3 ->9; *pop sign(+1)=9; +pop res(0)=9  []          9       -1
+     result+=(-1)*0 ->9; sign=+1                                     9       +1
(6+8) push(9,+1); ভেতরে 14; ) -> 14*(+1)+9 = 23     []                23
শেষ   result + sign*num = 23 + (+1)*0 = 23

8. Example input and output

Input : "1 + 1"               -> 2
Input : " 2-1 + 2 "           -> 3
Input : "(1+(4+5+2)-3)+(6+8)" -> 23

Edge case 1 (leading unary -) : "-1 + 2"  -> 1
Edge case 2 (নেস্টেড negative): "2-(5-6)" -> 3   (= 2-(-1))
Edge case 3 (একটাই সংখ্যা)    : "100"     -> 100

9. Brute force thinking

সরল চিন্তা: বারবার সবচেয়ে ভেতরের বন্ধনী খুঁজে বের করে আলাদাভাবে evaluate করি, ফলটা দিয়ে বন্ধনীসহ অংশটা প্রতিস্থাপন করি — যতক্ষণ আর বন্ধনী না থাকে; তারপর বন্ধনীহীন +/- চেইন বাঁ-থেকে-ডান হিসাব করি।

যতক্ষণ '(' আছে:
    সবচেয়ে ভেতরের "(...)" খুঁজে তার ভেতরটা evaluate করো
    string-এ "(...)"-কে ওই মান দিয়ে বদলাও
শেষে বন্ধনীহীন expression বাঁ->ডান যোগ/বিয়োগ

10. Why brute force is slow

প্রতিবার একটা বন্ধনী খুঁজে string নতুন করে বানালে আর আবার scan করলে — গভীর নেস্টিং (((((...))))) থাকলে বহুবার পুরো string scan, সবচেয়ে খারাপে O(n^2) বা তারও বেশি, আর substring বানানো ব্যয়বহুল। stack দিয়ে একবার বাঁ-থেকে-ডান হেঁটেই O(n)-তে পুরো কাজ হয়, string নতুন করে গড়তে হয় না।

11. Key observation

মূল observation: একটা সংখ্যাকে শুধু তার ঠিক-আগের একটা চিহ্ন (+/-) ঠিক করে — আগের পুরো ইতিহাস লাগে না, কারণ +/- বাঁ-থেকে-ডান একই অগ্রাধিকারে চলে। আর বন্ধনী শুধু একটা "ভেতরের ফল = একটা সংখ্যা" বানায়, যেটা বাইরের sign দিয়ে বাইরের যোগফলে ঢোকে। তাই stack-এ শুধু (বাইরের result, বাইরের sign) জমালেই পুরো nesting সামলানো যায়।

12. Optimized intuition

string-এ একবার হাঁটো। result=0, num=0, sign=+1 দিয়ে শুরু। digit পেলে num = num*10 + digit। + পেলে result += sign*num, তারপর num=0, sign=+1। - পেলে একই, কিন্তু sign=-1। ( পেলে result আর sign push করে result=0, sign=+1 দিয়ে নতুন context শুরু। ) পেলে result += sign*num; num=0, তারপর result *= pop() (বাইরের sign) আর result += pop() (বাইরের result)। শেষে অবশিষ্ট সংখ্যা মেশাতে return result + sign*num।

13. Thinking tweak

মোচড়: পুরো expression-কে একসাথে parse করার বদলে ভাবো — "আমি এই মুহূর্তে কোন context-এর ভেতরে যোগ করছি, আর পরের সংখ্যার চিহ্ন কী?" বন্ধনী মানে শুধু "এখনকার context-টা একটু পাশে রেখে নতুন একটা শুরু করো, পরে ফিরে এসে মিলিয়ে দাও"। তখন সব বন্ধনী এক-একটা সাব-হিসাব হয়ে সরল চেইনে গলে যায়।

14. Step-by-step dry run

Input "2-(5-6)":

1. শুরু: result=0, num=0, sign=+1, stack=[]
2. '2' → num=2
3. '-' → result += (+1)*2 = 2; num=0, sign=-1
4. '(' → push result=2, push sign=-1; result=0, sign=+1 → stack=[2, -1]
5. '5' → num=5
6. '-' → result += (+1)*5 = 5; num=0, sign=-1
7. '6' → num=6
8. ')' → result += (-1)*6 = -1; num=0; result *= pop()=-1 → 1; result += pop()=2 → 3; stack=[]
9. string শেষ → return result + sign*num = 3 + (-1)*0 = 3

15. Python solution

def calculate(s):
    result = 0
    num = 0
    sign = 1                       # পরের সংখ্যার চিহ্ন: +1 বা -1
    stack = []                     # '(' এ (বাইরের result, বাইরের sign) জমে
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)        # multi-digit সংখ্যা গড়ো
        elif ch == '+':
            result += sign * num
            num = 0
            sign = 1
        elif ch == '-':
            result += sign * num
            num = 0
            sign = -1
        elif ch == '(':
            stack.append(result)            # বাইরের যোগফল জমাও
            stack.append(sign)              # '(' এর আগের sign জমাও
            result = 0                      # ভেতরের জন্য নতুন context
            sign = 1
        elif ch == ')':
            result += sign * num            # ভেতরের শেষ সংখ্যা মেশাও
            num = 0
            result *= stack.pop()           # বাইরের sign দিয়ে গুণ
            result += stack.pop()           # বাইরের যোগফল ফিরিয়ে আনো
        # space বা অন্য কিছু -> কিছুই না
    return result + sign * num              # অবশিষ্ট সংখ্যা মেশাও

# ---- tests ----
assert calculate("1 + 1") == 2
assert calculate(" 2-1 + 2 ") == 3
assert calculate("(1+(4+5+2)-3)+(6+8)") == 23
assert calculate("-1 + 2") == 1            # leading unary minus
assert calculate("2-(5-6)") == 3           # নেস্টেড, দুই negative
assert calculate("100") == 100             # multi-digit, কোনো operator নেই
print("সব test pass!")

16. Line-by-line code explanation

• result, num, sign = 0, 0, 1 — চলমান যোগফল, এখন-বানানো সংখ্যা, পরের সংখ্যার চিহ্ন।
• if ch.isdigit(): num = num*10 + int(ch) — পরপর digit জুড়ে multi-digit সংখ্যা।
• elif ch == '+': — একটা সংখ্যা শেষ; result += sign*num দিয়ে মিশিয়ে num রিসেট, পরের চিহ্ন +1।
• elif ch == '-': — একই, তবে পরের চিহ্ন -1। (string --দিয়ে শুরু হলে num=0 মেশে, তাই leading unary minus এমনিতেই ঠিক হয়।)
• elif ch == '(': — বাইরের result আর sign দুটো push, তারপর ভেতরের জন্য result=0, sign=1।
• elif ch == ')': — ভেতরের শেষ সংখ্যা মেশাও; তারপর result *= pop() (বাইরের sign, যা পুরো বন্ধনীর চিহ্ন) আর result += pop() (বাইরের জমানো যোগফল) — বন্ধনীটা যেন একটা সংখ্যা হয়ে বাইরে ঢুকল।
• space ইত্যাদি কোনো branch-এ পড়ে না, তাই উপেক্ষিত।
• return result + sign * num — loop শেষে যে সংখ্যাটা এখনো মেশানো হয়নি, তাকে মিশিয়ে চূড়ান্ত ফল।

17. Output walkthrough

calculate("(1+(4+5+2)-3)+(6+8)") → section 7-এর trace মতো ভেতরের বন্ধনী (4+5+2)=11, তারপর বাইরের (1+11-3)=9, শেষে +(6+8)=14 মিলে 23। calculate("-1 + 2") → শুরুতেই - এসে num=0 মেশায় (ক্ষতি নেই) আর sign=-1 করে, তাই -1+2 = 1। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity

O(n) — string-এর প্রতিটা character ঠিক একবার দেখা হয়; প্রতিটা push/pop O(1)।

19. Space complexity

O(n) — সবচেয়ে খারাপ ক্ষেত্রে (গভীর নেস্টিং, যেমন ((((...))))) প্রতিটা ( দুটো করে value push করে, stack গভীরতা বন্ধনী-গভীরতার সমান।

20. Common mistakes

• (-তে শুধু result push করা, sign ভুলে যাওয়া — তাহলে 2-(...)-এর মতো ক্ষেত্রে বন্ধনীর চিহ্ন হারিয়ে ভুল উত্তর।
• pop-এর ক্রম উল্টে দেওয়া — push করেছি result আগে, sign পরে; তাই pop-এ আগে sign (গুণ), পরে result (যোগ)। ক্রম ভুল হলে গণ্ডগোল।
• loop শেষে শেষ সংখ্যা না মেশানো — "100"-এর মতো operator-হীন বা শেষ সংখ্যাওয়ালা ক্ষেত্রে return result লিখলে শেষ num বাদ পড়ে; result + sign*num লাগবে।
• multi-digit ভুলে এক-digit ধরা — num*10 + digit না করলে 100 ভুল হবে।

21. Which basic problem this inherits from

ভিত্তি: Problem 10 (decode string)-এর save-context-on-open, restore-on-close চাল; chapter-এর ../patterns.md Pattern 1 (Matching / Nesting)। এখানে context হলো (result, sign) জোড়া, আর )-তে ভেতরের ফল বাইরের sign দিয়ে মিশে যায়।

22. Similar harder problems

• Basic Calculator II (*, / সহ, precedence) — https://leetcode.com/problems/basic-calculator-ii/
• Basic Calculator III (বন্ধনী + চার operator) — https://leetcode.com/problems/basic-calculator-iii/
• Decode String (nested context) — https://leetcode.com/problems/decode-string/ (এই tracker-এর #10)

23. Pattern learned

Stack of contexts: "বন্ধনী সহ expression evaluate", "nested context" দেখলে চলমান result আর sign রাখো; (-তে দুটোই push করে নতুন context শুরু, )-তে ভেতরের ফল বাইরের sign দিয়ে গুণ করে বাইরের result-এ যোগ। loop শেষে শেষ সংখ্যা মেশাতে ভুলো না।

24. Final summary

ভবিষ্যতের আমাকে: basic calculator = চলমান result + sign, বন্ধনীতে context push/pop। ( → push(result), push(sign), রিসেট; ) → শেষ num মেশাও, *= pop() (sign), += pop() (result)। শেষে result + sign*num। leading - এমনিতেই ঠিক হয় (num=0)। "parentheses সহ evaluate / nested context" দেখলেই এই pattern।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।