Problem link ও উৎস
- **Original source:** Classic stack-simulation exercise
- **Platform:** LeetCode —
- **Topic:** stack
- **Difficulty:** Medium
- **Pattern:** stack simulation
- **Basic idea inherited from:** operand-রা stack-এ অপেক্ষা করে যতক্ষণ না তাদের operator আসে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **postfix** (Reverse Polish Notation, RPN) expression দেওয়া আছে token-এর list আকারে। postfix-এ operator তার দুটো operand-এর *পরে* বসে — যেমন `2 1 +` মানে `2 + 1`। token গুলো হয় একটা সংখ্যা, নয়তো `+`, `-`, `*`, `/` operator। expression-টা evaluate করে চূড়ান্ত মান return করো। ভাগের ফল শূন্যের দিকে truncate হয় (যেমন `6 / -132 = 0`)।
### Input ও output {#8-example-input-and-output}
```text
Input : ["2","1","+","3","*"] -> Output: 9 ((2+1)*3)
Input : ["4","13","5","/","+"] -> Output: 6 (4 + 13/5 = 4 + 2)
Edge case (negative + truncation): ["3","-4","/"] -> 0 (3/-4 = -0.75 -> 0, শূন্যের দিকে)
Big case: ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] -> 22
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ক্যালকুলেটরের পুরোনো RPN ধাঁচ ভাবো (HP calculator-এর মতো): তুমি সংখ্যা টিপে টিপে জমাও, তারপর একটা operator চাপলে সে শেষ দুটো সংখ্যা নিয়ে হিসাব করে ফলটা আবার জমার জায়গায় বসিয়ে দেয়। তোমাকে bracket নিয়ে ভাবতে হয় না — শুধু "জমাও, তারপর হিসাব করো"। সেই জমার জায়গাটাই stack।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা stack-simulation পরিবারের (problem 2, 3-এর মতো)। মূল idea: **operand-রা stack-এ অপেক্ষা করে যতক্ষণ না তাদের operator আসে।** সংখ্যা দেখলে জমিয়ে রাখো; operator দেখলে শেষ দুটো operand নামিয়ে হিসাব করে ফলটা আবার জমাও।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো postfix-এর সংজ্ঞা নিজেই: একটা operator সবসময় তার ঠিক আগের দুটো (এখনো-ব্যবহার-না-হওয়া) মানের উপর কাজ করে। এই "ঠিক আগের দুটো" মানে stack-এর top দুটো। তাই evaluation = বাঁ-থেকে-ডানে scan, সংখ্যা push, operator-এ top দুটো নিয়ে reduce। এ কারণেই postfix-এ কোনো bracket লাগে না — order-টাই precedence ঠিক করে দেয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **stack** (`list`), যেখানে এখনো-হিসাব-না-হওয়া operand (এবং মাঝপথের ফলাফল) জমে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা operator-এর দরকার সবচেয়ে recent দুটো operand — ঠিক stack-এর top দুটো, `pop` দিয়ে O(1)-তে পাওয়া যায়। হিসাবের ফল আবার একটা নতুন operand, যা `append` করে রাখি — পরের operator সেটাকে top হিসেবে পাবে। এই "শেষ দুটো নাও, একটা ফেরত দাও" নাচটা stack-এর জন্য নিখুঁত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
stack ছাড়া করতে গেলে: token list-এ বারবার scan করে প্রথম operator খুঁজি, তার আগের দুটো সংখ্যা নিয়ে হিসাব করি, তারপর ওই তিনটা token (দুই সংখ্যা + operator) কে একটা ফলাফল-token দিয়ে বদলে দিই — যতক্ষণ একটা token বাকি থাকে।
```text
["2","1","+","3","*"]
-> প্রথম operator "+": 2,1 -> 3 -> ["3","3","*"]
-> প্রথম operator "*": 3,3 -> 9 -> ["9"]
-> answer 9
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার operator খুঁজতে list scan (O(n)), আর list-এর মাঝখানে replace করতে element shift (O(n))। n বার করলে → **O(n^2)**। stack approach একবার বাঁ-থেকে-ডানে হেঁটে সব সামলায় — প্রতিটা token O(1), মোট O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা operator সবসময় ঠিক তার আগের দুটো অমীমাংসিত মানের উপর কাজ করে** — এর বেশি দূর তাকাতে হয় না। "আগের দুটো অমীমাংসিত মান" = stack-এর top দুটো। তাই একবার scan-ই যথেষ্ট, কোনো back-tracking লাগে না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা stack নাও। token গুলোতে একবার হাঁটো: token operator হলে `b = pop()`, `a = pop()`, `a op b`-এর ফল push করো; নাহলে সংখ্যাটাকে `int` করে push করো। শেষে stack-এ থাকা একমাত্র মানটাই answer। `-` আর `/`-এর জন্য মনে রেখো: প্রথম pop = ডান operand।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** postfix-কে "অদ্ভুত notation" না ভেবে, এটাকে দেখো operand-দের একটা **waiting room** হিসেবে — সংখ্যা এসে অপেক্ষা করে, operator এসে শেষ দুজনকে জোড়া লাগিয়ে একজন বানিয়ে দেয়। এই দৃষ্টিভঙ্গিতে precedence/parenthesis-এর সব ঝামেলা উবে যায়; order-টাই সব বলে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`["2", "1", "+", "3", "*"]` evaluate করি:
```text
token action stack (top ডানে)
"2" সংখ্যা -> push [2]
"1" সংখ্যা -> push [2, 1]
"+" pop 1, pop 2 -> 2+1=3 -> push [3]
"3" সংখ্যা -> push [3, 3]
"*" pop 3, pop 3 -> 3*3=9 -> push [9]
end stack-এ একটাই মান -> answer = 9
```
খেয়াল রাখো: operator-এ প্রথমে যেটা pop হয় সেটা **ডান** operand (`b`), পরেরটা **বাঁ** operand (`a`) — `-` আর `/`-এ order জরুরি।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `["4", "13", "5", "/", "+"]`:
1. `"4"` → push → `[4]`
2. `"13"` → push → `[4, 13]`
3. `"5"` → push → `[4, 13, 5]`
4. `"/"` → `b=5`, `a=13` → `int(13/5)=int(2.6)=2` → push → `[4, 2]`
5. `"+"` → `b=2`, `a=4` → `4+2=6` → push → `[6]`
6. end → stack-এ একটাই মান → answer `6`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def eval_rpn(tokens):
stack = []
ops = {"+", "-", "*", "/"}
for token in tokens:
if token in ops:
b = stack.pop() # প্রথম pop = ডান operand
a = stack.pop() # দ্বিতীয় pop = বাঁ operand
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
else: # "/" শূন্যের দিকে truncate
stack.append(int(a / b))
else:
stack.append(int(token)) # সংখ্যা (negative-ও)
return stack[-1]
# ---- tests ----
assert eval_rpn(["2", "1", "+", "3", "*"]) == 9
assert eval_rpn(["4", "13", "5", "/", "+"]) == 6
assert eval_rpn(["3", "-4", "/"]) == 0 # -0.75 -> 0 (শূন্যের দিকে)
assert eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]) == 22
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `stack = []` — operand আর মাঝপথের ফলাফল এখানে জমে।
- `ops = {...}` — কোনগুলো operator, O(1)-তে চিনতে একটা set।
- `if token in ops:` — operator হলে: `b = pop()` (ডান), `a = pop()` (বাঁ) — order জরুরি।
- চারটা `if/elif` শাখা — যথাক্রমে যোগ/বিয়োগ/গুণ; `else`-এ ভাগ।
- `int(a / b)` — float ভাগ করে `int()` দিয়ে শূন্যের দিকে truncate (যেমন `int(-0.75) == 0`, `int(2.6) == 2`)।
- `else: stack.append(int(token))` — সংখ্যা হলে `int` করে push; negative হ্যান্ডল হয়।
- `return stack[-1]` — শেষে stack-এ থাকা একমাত্র মান।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`eval_rpn(["4","13","5","/","+"])` → section 14-এর মতো `13/5 -> 2`, তারপর `4+2 -> 6`। `eval_rpn(["3","-4","/"])` → `int(3 / -4) = int(-0.75) = 0`। বড় expression-টা ধাপে ধাপে reduce হয়ে `22` দেয়। সব assert pass — print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function evalRPN(tokens) {
const stack = [];
const ops = new Set(["+", "-", "*", "/"]);
for (const token of tokens) {
if (ops.has(token)) {
const b = stack.pop(); // প্রথম pop = ডান operand
const a = stack.pop(); // দ্বিতীয় pop = বাঁ operand
if (token === "+") stack.push(a + b);
else if (token === "-") stack.push(a - b);
else if (token === "*") stack.push(a * b);
else stack.push(Math.trunc(a / b)); // শূন্যের দিকে truncate
} else {
stack.push(Number(token)); // সংখ্যা (negative-ও)
}
}
return stack[stack.length - 1];
}
// ---- test cases ----
assert(evalRPN(["2", "1", "+", "3", "*"]) === 9, "(2+1)*3");
assert(evalRPN(["4", "13", "5", "/", "+"]) === 6, "4 + 13/5");
assert(evalRPN(["3", "-4", "/"]) === 0, "-0.75 -> 0"); // শূন্যের দিকে
assert(evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]) === 22, "big");
console.log("সব JS test pass!");
```
> **JS টীকা:** এখানে সবচেয়ে বড় ফাঁদ হলো ভাগ। JS-এ `/` সবসময় float ভাগ দেয়, তাই truncation নিজে করতে হয় — কিন্তু `Math.floor` নয়, `Math.trunc` (বা `(a/b)|0` ছোট সংখ্যায়)। কারণ negative-এ `Math.floor(-0.75) = -1`, অথচ চাই শূন্যের দিকে `0` = `Math.trunc(-0.75)`। সংখ্যা parse-এ `Number(token)` ব্যবহার করো — এটা `"-4"`-ও ঠিক handle করে, `parseInt`-এর মতো edge ছাড়াই।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function evalRPN(tokens: string[]): number {
const stack: number[] = [];
const ops = new Set