Problem link ও উৎস
- **Original source:** Classic stack-simulation exercise
- **Platform:** LeetCode —
- **Topic:** stack
- **Difficulty:** Easy
- **Pattern:** stack simulation
- **Basic idea inherited from:** push/pop as undo — প্রতিটা operation stack-এর top-কে দেখে কাজ করে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে কতগুলো operation-এর একটা list দেওয়া আছে (সবগুলো string আকারে)। তুমি একটা score record রাখবে আর প্রতিটা operation এক এক করে চালাবে:
- একটা সংখ্যা `x` — নতুন একটা score হিসেবে `x` যোগ করো।
- `"+"` — শেষ দুটো score-এর যোগফল নতুন একটা score হিসেবে যোগ করো।
- `"D"` — শেষ score-এর দ্বিগুণ নতুন একটা score হিসেবে যোগ করো।
- `"C"` — শেষ score-টা বাতিল করে দাও (record থেকে মুছে ফেলো)।
সব operation শেষে record-এ থাকা সব score-এর যোগফল return করো।
### Input ও output {#8-example-input-and-output}
```text
Input : ["5", "2", "C", "D", "+"] -> Output: 30
Input : ["5", "-2", "4", "C", "D", "9", "+", "+"] -> Output: 27
Edge case (সব বাতিল): ["1", "C"] -> Output: 0 (record খালি -> যোগফল 0)
```
দ্বিতীয় example-এ negative সংখ্যাও আছে (`"-2"`), তাই `int()` parse করা জরুরি — শুধু digit check করলে হবে না।
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা পেন্সিল দিয়ে কাগজে score লেখা ভাবো, একটার নিচে একটা। নতুন score এলে নিচে আরেকটা লাইন লেখো। কেউ ভুল হয়েছে বললে (`"C"`) — শেষ লাইনটা মুছে দাও। কোনো লাইন যোগ করতে আগের লাইন(গুলো) দেখা লাগলে, তুমি সবসময় সবচেয়ে নিচের, মানে সবচেয়ে নতুন লাইনটাই দেখো। এই "নিচ থেকে যোগ করা আর নিচ থেকে মোছা"-ই stack।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **push/pop-কে undo হিসেবে ব্যবহার** করার সরাসরি প্রয়োগ। `"C"` মানে আক্ষরিক অর্থে "শেষ কাজটা undo করো" → একটা `pop`। `x`, `"+"`, `"D"` — সবই নতুন কিছু *push* করে, আর তারা সবসময় সবচেয়ে recent এক-দুটো score-এর উপর নির্ভর করে, যেগুলো stack-এর top-এ বসে আছে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **temporal locality**: প্রতিটা operation শুধু সবচেয়ে recent এক বা দুটো score-কে ছোঁয়, তার আগের history-কে নয়। তাই একটা LIFO structure যথেষ্ট — যা দরকার তা সবসময় উপরে থাকে। final answer হলো record-এ টিকে থাকা সব valid score-এর simple যোগফল।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **stack** (Python `list`)। আমরা শেষ প্রান্তেই push (`append`), pop, আর peek (`[-1]`, `[-2]`) করি — ঠিক stack-এর সস্তা প্রান্ত।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা operation-এর জন্য যে তথ্য দরকার তা হলো সবচেয়ে recent score গুলো — মানে stack-এর top। `"C"` চায় শেষ-যোগ-করা score মুছতে → `pop`, O(1)। `"D"` চায় শেষ score → `[-1]`, O(1)। `"+"` চায় শেষ দুটো → `[-1]` আর `[-2]`, O(1)। কোনো মাঝখানে খোঁজাখুঁজি নেই, তাই stack নিখুঁতভাবে খাপ খায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
stack ছাড়া করতে গেলে একটা সাধারণ list রাখতাম, আর প্রতিটা operation-এ index hisaব করে শেষ element খুঁজতে হতো:
```text
record = []
"+" হলে: last = len(record)-1; record.append(record[last] + record[last-1])
"C" হলে: record-এর শেষ element del করো (del record[-1])
```
আসলে এটাও কাজ করে — কারণ Python list-এর শেষ প্রান্ত নিজেই একটা stack।
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই problem-এ আসল "brute force vs optimal" tension নেই — naive approach আর optimal approach একই, কারণ list-এর শেষ প্রান্ত (`append`/`pop`) এমনিতেই O(1)। **ভুল** approach হতো record-এর *সামনে* insert/delete করা (`insert(0, ...)` / `pop(0)`), যা প্রতিবার O(n) shift ঘটায় → পুরোটা O(n^2)। আসল শিক্ষা: সবসময় সস্তা (শেষ) প্রান্তেই কাজ করো।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা operation শুধু record-এর শেষ এক-দুটো entry-কে ছোঁয়।** কখনো গভীরে যেতে হয় না। তাই "শেষ প্রান্ত" cheap রাখলেই পুরো simulation cheap — মানে stack যথেষ্ট।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা stack নাও। operation list-এ একবার হাঁটো। `"+"` হলে top দুটোর যোগফল push করো; `"D"` হলে top-এর দ্বিগুণ push করো; `"C"` হলে top pop করো; নাহলে সংখ্যাটাকে `int` করে push করো। শেষে stack-এর সব element-এর `sum` return করো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** problem-টা একগাদা নিয়মের জটিল হিসাব মনে হলেও, প্রতিটা নিয়মই আসলে "top দেখো, একটা নতুন value push করো বা top pop করো"। জটিলতাটা চারটে ছোট, top-নির্ভর operation-এ ভেঙে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`["5", "2", "C", "D", "+"]` চালাই, stack বদলাতে দেখি:
```text
op action stack (top ডানে)
"5" integer -> push 5 [5]
"2" integer -> push 2 [5, 2]
"C" cancel -> pop শেষ (2) [5]
"D" double -> push 2*top = 2*5 = 10 [5, 10]
"+" sum -> push top + প্রাক্-top = 15 [5, 10, 15]
end sum = 5 + 10 + 15 = 30
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `["5", "-2", "4", "C", "D", "9", "+", "+"]`:
1. `"5"` → push 5 → `[5]`
2. `"-2"` → push -2 → `[5, -2]`
3. `"4"` → push 4 → `[5, -2, 4]`
4. `"C"` → pop 4 → `[5, -2]`
5. `"D"` → push 2*(-2) = -4 → `[5, -2, -4]`
6. `"9"` → push 9 → `[5, -2, -4, 9]`
7. `"+"` → push 9 + (-4) = 5 → `[5, -2, -4, 9, 5]`
8. `"+"` → push 5 + 9 = 14 → `[5, -2, -4, 9, 5, 14]`
9. sum = 5 + (-2) + (-4) + 9 + 5 + 14 = 27 → return `27`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def cal_points(operations):
stack = []
for op in operations:
if op == "+":
stack.append(stack[-1] + stack[-2]) # শেষ দুটোর যোগ
elif op == "D":
stack.append(2 * stack[-1]) # শেষটার দ্বিগুণ
elif op == "C":
stack.pop() # শেষটা বাতিল
else:
stack.append(int(op)) # সংখ্যা (negative-ও) push
return sum(stack)
# ---- tests ----
assert cal_points(["5", "2", "C", "D", "+"]) == 30
assert cal_points(["5", "-2", "4", "C", "D", "9", "+", "+"]) == 27
assert cal_points(["1", "C"]) == 0 # সব বাতিল -> খালি record
assert cal_points(["1", "2", "3"]) == 6 # শুধু সংখ্যা
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `stack = []` — valid score গুলো এখানে জমবে।
- `if op == "+":` — শেষ দুটো score (`stack[-1]`, `stack[-2]`) যোগ করে নতুন একটা push।
- `elif op == "D":` — শেষ score-এর `2 *` গুণ push।
- `elif op == "C":` — শেষ score `pop` করে বাতিল।
- `else: stack.append(int(op))` — string-টা সংখ্যা; `int()` দিয়ে parse করে push (negative হ্যান্ডল হয়)।
- `return sum(stack)` — record-এ টিকে থাকা সব score-এর যোগফল।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cal_points(["5", "2", "C", "D", "+"])` → section 7-এর মতো stack হয় `[5, 10, 15]`, `sum` = 30। `cal_points(["1", "C"])` → 1 push, তারপর pop → stack খালি → `sum([])` = 0। সব assert pass হয়ে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — n-টা operation, প্রতিটা O(1) (push/pop/peek)। শেষের `sum` আরও O(n), মোট তাও O(n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — সবচেয়ে খারাপ ক্ষেত্রে (সব operation সংখ্যা) stack-এ n-টা score জমতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- negative সংখ্যা ভুলে যাওয়া — শুধু `op.isdigit()` দিয়ে check করলে `"-2"` ধরা পড়ে না; `int()` দিয়ে parse করা নিরাপদ।
- `"+"`-এ ভুল দুটো element নেওয়া (যেমন `stack[0]` আর `stack[1]`); সবসময় *শেষ* দুটো (`[-1]`, `[-2]`)।
- record-এর সামনে insert/delete করা (`pop(0)`) — অকারণে O(n) করে দেয়; শেষ প্রান্তেই কাজ করো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: stack-এর push/pop-as-undo discipline, যা problem 1 (Valid Parentheses)-এও দেখা — সেখানে `"C"`-এর মতো "শেষ খোলাটা বন্ধ করা" ছিল। chapter-এর [../patterns.md](../patterns.md)-এর Pattern 1 (Matching / Nesting / Undo) এর ছাতার নিচে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Evaluate Reverse Polish Notation (postfix expression) —