008 — Evaluate Reverse Polish Notation

Source

• Original source: Classic stack-simulation exercise
• Platform: LeetCode — https://leetcode.com/problems/evaluate-reverse-polish-notation/
• Topic: stack
• Difficulty: Medium
• Pattern: stack simulation
• Basic idea inherited from: operand-রা stack-এ অপেক্ষা করে যতক্ষণ না তাদের operator আসে

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)।

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-এর জন্য নিখুঁত।

6. Real-life analogy

ক্যালকুলেটরের পুরোনো RPN ধাঁচ ভাবো (HP calculator-এর মতো): তুমি সংখ্যা টিপে টিপে জমাও, তারপর একটা operator চাপলে সে শেষ দুটো সংখ্যা নিয়ে হিসাব করে ফলটা আবার জমার জায়গায় বসিয়ে দেয়। তোমাকে bracket নিয়ে ভাবতে হয় না — শুধু "জমাও, তারপর হিসাব করো"। সেই জমার জায়গাটাই stack।

7. Visual explanation

["2", "1", "+", "3", "*"] evaluate করি:

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 জরুরি।

8. Example input and output

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

9. Brute force thinking

stack ছাড়া করতে গেলে: token list-এ বারবার scan করে প্রথম operator খুঁজি, তার আগের দুটো সংখ্যা নিয়ে হিসাব করি, তারপর ওই তিনটা token (দুই সংখ্যা + operator) কে একটা ফলাফল-token দিয়ে বদলে দিই — যতক্ষণ একটা token বাকি থাকে।

["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-টাই সব বলে দেয়।

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

15. Python solution

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-এ থাকা একমাত্র মান।

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!।

18. Time complexity

O(n) — প্রতিটা token ঠিক একবার process হয়; প্রতিটা push/pop O(1)।

19. Space complexity

O(n) — সবচেয়ে খারাপ ক্ষেত্রে (শুরুতে অনেকগুলো সংখ্যা) stack-এ O(n) operand জমতে পারে।

20. Common mistakes

• - আর /-এ operand-এর order উল্টে ফেলা — প্রথম pop হলো ডান operand (b), দ্বিতীয়টা বাঁ (a); a - b, a / b লিখতে হবে, b - a নয়।
• ভাগে // (floor division) ব্যবহার — negative-এ // শূন্যের দিকে নয়, নিচের দিকে truncate করে (-7 // 2 == -4), অথচ এখানে শূন্যের দিকে চাই; তাই int(a / b)।
• negative সংখ্যা parse-এ ভুল — op.isdigit() দিয়ে check করলে "-4" বাদ পড়ে; operator কিনা আগে দেখে, নাহলে int()।

21. Which basic problem this inherits from

ভিত্তি: stack simulation (problem 2 — Baseball Game)-এর "শেষ কয়েকটা মানের উপর কাজ করা" idea; chapter-এর ../patterns.md-এর Pattern 1 ছাতার নিচে (matching/nesting-এর সঙ্গী stack simulation)। ../concept.md-এর "কখন stack ব্যবহার করবে" তালিকায় "postfix/infix expression evaluate" সরাসরি বলা আছে।

22. Similar harder problems

• Basic Calculator (+, -, parentheses সহ infix) — https://leetcode.com/problems/basic-calculator/ (এই tracker-এর #22)
• Basic Calculator II (precedence সহ * /) — https://leetcode.com/problems/basic-calculator-ii/
• Decode String (nested context, stack) — https://leetcode.com/problems/decode-string/ (#10)

23. Pattern learned

Stack-based expression evaluation: postfix-এ সংখ্যা push করো, operator-এ top দুটো নিয়ে reduce করো — bracket/precedence ছাড়াই একবার scan-এ O(n) evaluation।

24. Final summary

ভবিষ্যতের আমাকে: "postfix = operand-দের waiting room; operator এসে শেষ দুজনকে এক করে দেয়।" -//-এ pop-order মনে রাখবে (প্রথম pop = ডান), আর truncation চাইলে int(a / b), কখনো // নয়। expression evaluate দেখলেই stack।

25. JavaScript solution (with test cases)

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 ছাড়াই।

26. TypeScript solution (with test cases)

function evalRPN(tokens: string[]): number {
  const stack: number[] = [];
  const ops = new Set<string>(["+", "-", "*", "/"]);
  for (const token of tokens) {
    if (ops.has(token)) {
      const b = stack.pop()!;             // ডান operand
      const a = stack.pop()!;             // বাঁ operand
      switch (token) {
        case "+": stack.push(a + b); break;
        case "-": stack.push(a - b); break;
        case "*": stack.push(a * b); break;
        default:  stack.push(Math.trunc(a / b));   // "/"
      }
    } else {
      stack.push(Number(token));
    }
  }
  return stack[stack.length - 1];
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
expect(evalRPN(["2", "1", "+", "3", "*"]), 9, "ex1");
expect(evalRPN(["4", "13", "5", "/", "+"]), 6, "ex2");
expect(evalRPN(["3", "-4", "/"]), 0, "trunc");
expect(evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]), 22, "big");
console.log("সব TS test pass!");

TS টীকা: input string[] কিন্তু stack number[] — এই দুই type আলাদা রাখায় কম্পাইলার মনে করিয়ে দেয় যে token-কে আগে Number() দিয়ে রূপান্তর করতে হবে, নাহলে number array-তে string push হবে না। switch ব্যবহার করায় প্রতিটা operator-শাখা স্পষ্ট, আর default ভাগ ধরায় কোনো operator বাদ পড়ার সুযোগ থাকে না।

27. কোথায় কাজে লাগে (real-world use)

• Calculator engines: RPN/postfix evaluation পুরোনো HP calculator আর আধুনিক spreadsheet formula engine-এর core।
• Compiler/interpreter: infix expression-কে postfix-এ রূপান্তর করে stack দিয়ে evaluate করা — code generation-এর ধাপ।
• Query/rule engines: database query optimizer ও business-rule engine অনেক সময় expression tree-কে stack-evaluation দিয়ে চালায়।
• Virtual machines: JVM, CPython-এর মতো stack-based VM bytecode-কে ঠিক এই push-operand/apply-operator ধাঁচে execute করে।
• Scientific/graphing tools: user-typed formula parse করে নিরাপদে মান বের করতে এই pattern ব্যবহৃত হয়।

এক কথায়, যেকোনো expression evaluation — যেখানে operator তার operand-দের উপর ক্রমে কাজ করে — stack-ই সবচেয়ে স্বাভাবিক ও bracket-মুক্ত হাতিয়ার।

---

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