Problem link ও উৎস
- **Original source:** Classic stack-of-contexts exercise
- **Platform:** LeetCode —
- **Topic:** stack (nesting / context)
- **Difficulty:** Hard
- **Pattern:** nesting (stack of contexts)
- **Basic idea inherited from:** Problem 10-এর save-context-on-`(` restore-on-`)` চাল — `(` এলে এ পর্যন্তের ফলাফল আর sign জমিয়ে রাখো, `)` এলে ফিরিয়ে আনো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা গাণিতিক expression string দেওয়া আছে যাতে আছে: অঋণাত্মক পূর্ণসংখ্যা, `+`, `-`, খোলা-বন্ধ বন্ধনী `(` `)`, আর কিছু space। (এখানে গুণ-ভাগ নেই — শুধু যোগ, বিয়োগ আর বন্ধনী।) string-টা evaluate করে তার মান বের করো।
```text
"1 + 1" -> 2
" 2-1 + 2 " -> 3
"(1+(4+5+2)-3)+(6+8)" -> 23
"2-(5-6)" -> 3 (= 2 - (-1))
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা হিসাব কষছ, হঠাৎ এক বন্ধনী এসে বলল "দাঁড়াও, আগে এই ছোট হিসাবটা আলাদা করে করি"। তুমি এখনকার খাতার যোগফল আর "এই অংশটা যোগ হবে না বিয়োগ" তথ্যটা একটা sticky-note-এ লিখে পাশে রাখলে (push), নতুন একটা পরিষ্কার পাতায় ভেতরের হিসাব শুরু করলে। ভেতরের হিসাব শেষ (`)`) হলে sticky-note তুলে এনে (pop) ভেতরের ফলটা ঠিক চিহ্ন দিয়ে মূল হিসাবে বসিয়ে দিলে। একাধিক বন্ধনী নেস্ট করলে sticky-note-ও গাদা হয়ে জমে — শেষেরটা আগে তোলো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ এই "শেষ-খোলা আগে-বন্ধ" এত সস্তায় হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: বারবার সবচেয়ে ভেতরের বন্ধনী খুঁজে বের করে আলাদাভাবে evaluate করি, ফলটা দিয়ে বন্ধনীসহ অংশটা প্রতিস্থাপন করি — যতক্ষণ আর বন্ধনী না থাকে; তারপর বন্ধনীহীন `+`/`-` চেইন বাঁ-থেকে-ডান হিসাব করি।
```text
যতক্ষণ '(' আছে:
সবচেয়ে ভেতরের "(...)" খুঁজে তার ভেতরটা 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-টা একটু পাশে রেখে নতুন একটা শুরু করো, পরে ফিরে এসে মিলিয়ে দাও"। তখন সব বন্ধনী এক-একটা সাব-হিসাব হয়ে সরল চেইনে গলে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`(1+(4+5+2)-3)+(6+8)` evaluate করার সময় stack (top ডানে) আর চলক:
```text
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
```
### ছোট input-এ ধাপে ধাপে {#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`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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 শেষে যে সংখ্যাটা এখনো মেশানো হয়নি, তাকে মিশিয়ে চূড়ান্ত ফল।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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` ভুল হবে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Problem 10 (decode string)-এর save-context-on-open, restore-on-close চাল; chapter-এর [../patterns.md](../patterns.md) Pattern 1 (Matching / Nesting)। এখানে context হলো `(result, sign)` জোড়া, আর `)`-তে ভেতরের ফল বাইরের sign দিয়ে মিশে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Basic Calculator II (`*`, `/` সহ, precedence) —