PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Postfix Expression Evaluation using Stack (पोस्टफिक्स एक्सप्रेशन मूल्यांकन: स्टैक ऑपरेशन्स और परिणाम) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Postfix Expression Evaluation scans tokens left-to-right using an operand Stack, pushing numbers directly and popping two operands when an operator appears. Because the first popped value is the right operand (op2) and the second is the left operand (op1), computing op1 <op> op2 prevents fatal errors on subtraction, division, and exponentiation.
अध्याय सार: पोस्टफिक्स एक्सप्रेशन मूल्यांकन में बाएं से दाएं स्कैन करते हुए ऑपरेंड स्टैक का उपयोग होता है, जहाँ संख्याएं पुश होती हैं और ऑपरेटर आने पर दो मान पॉप किए जाते हैं। पहला पॉप किया गया मान दायाँ ऑपरेंड (op2) और दूसरा बायाँ ऑपरेंड (op1) होता है, इसलिए गणना हमेशा op1 <op> op2 क्रम में होती है।
Postfix Expression Evaluation using Stack: Detailed Notes & Architecture (पोस्टफिक्स एक्सप्रेशन मूल्यांकन: स्टैक ऑपरेशन्स और परिणाम)
1. Operand Stack Mechanics vs Infix-to-Postfix Stack (ऑपरेंड स्टैक की कार्यप्रणाली (रूपांतरण स्टैक से अंतर))
[EN] A classic exam contrast: Infix-to-Postfix pushes OPERATORS onto the stack, whereas Postfix Evaluation pushes OPERANDS (numeric values) onto the stack and NEVER pushes operators. Scanning left to right in O(n) time, every numeric token is pushed onto the operand stack, while each binary operator reduces stack size by 1 (pops 2 operands, pushes 1 result).
[HI] महत्वपूर्ण अंतर: रूपांतरण में स्टैक पर ऑपरेटर रखे जाते हैं, जबकि पोस्टफिक्स मूल्यांकन में स्टैक पर ऑपरेंड (संख्याएं) पुश किए जाते हैं और ऑपरेटर कभी पुश नहीं होते। बाएं से दाएं स्कैन में प्रत्येक संख्या पुश होती है और प्रत्येक बाइनरी ऑपरेटर 2 मान पॉप करके 1 परिणाम वापस पुश करता है।
2. Critical Pop Order: op2 First, op1 Second (महत्वपूर्ण पॉप क्रम: पहले op2, फिर op1)
[EN] When encountering binary operator 'op', the first item popped is the RIGHT operand (op2 = pop()) and the second item popped is the LEFT operand (op1 = pop()); you then compute (op1 op op2) and push it back. For commutative operators (+, *), swapping order hides the bug, but for non-commutative '-', '/', '%', and '^', computing op2 - op1 instead of op1 - op2 flips signs and ruins division (e.g., '8 2 /' is 8 / 2 = 4, NOT 2 / 8)!
[HI] ऑपरेटर आने पर पहली बार पॉप होने वाला मान हमेशा दायाँ ऑपरेंड (op2) और दूसरी बार पॉप होने वाला मान बायाँ ऑपरेंड (op1) होता है; अतः गणना (op1 op op2) से होती है। '+' और '*' में क्रम बदलने से अंतर नहीं दिखता, पर '-', '/', '%' और '^' में क्रम गलत होने पर परिणाम बिल्कुल उल्टा (जैसे '8 2 /' का 4 की बजाय 2/8) हो जाता है।
3. Validity Invariants, Underflow & Multi-Digit Tokenization (वैधता जांच, अंडरफ्लो और बहु-अंकीय संख्या पार्सिंग)
[EN] After evaluating a valid Postfix expression, the stack must hold EXACTLY ONE value—the final result. Fewer than 2 operands present when reading a binary operator triggers Stack Underflow (too many operators), while >1 value left at the end indicates missing operators; both detect malformed expressions in O(n) time. Additionally, multi-digit numbers like '12 3 /' require space/delimiter tokenization so '12' isn't split into '1' and '2'.
[HI] सही पोस्टफिक्स व्यंजक पूरा होने पर स्टैक में ठीक एक ही अंतिम मान शेष रहना चाहिए। ऑपरेटर आने पर स्टैक में 2 से कम मान हों तो Underflow (अतिरिक्त ऑपरेटर) और अंत में 1 से अधिक मान बचें तो कम ऑपरेटर होने की त्रुटि पकड़ी जाती है। '12 3 /' जैसी बहु-अंकीय संख्याओं को अलग पहचानने हेतु स्पेस या डिलीमीटर आवश्यक है।
4. Comparing Postfix Evaluation with Prefix Evaluation (पोस्टफिक्स बनाम प्रीफिक्स मूल्यांकन की तुलना)
[EN] Both evaluations run in O(n) time and O(n) space, yet differ in scan direction and pop order. Postfix scans Left-to-Right and pops op2 first, op1 second (result = op1 op op2). Conversely, Prefix evaluation scans Right-to-Left from the end of the expression, pushes operands, and pops op1 FIRST (top), op2 SECOND before pushing (op1 op op2).
[HI] पोस्टफिक्स और प्रीफिक्स दोनों का मूल्यांकन O(n) समय में होता है, किंतु दिशा व पॉप क्रम उल्टा होता है। पोस्टफिक्स बाएं-से-दाएं स्कैन करता है (पहला पॉप op2, दूसरा op1), जबकि प्रीफिक्स मूल्यांकन दाएं-से-बाएं चलता है और पहले पॉप को op1 व दूसरे को op2 मानता है।
Syntax, Formula & Technical Example (Postfix Expression Evaluation using Stack)
/* Trace: 5 3 2 * + 9 - 4 / */
Token | Action | Operand Stack
5,3,2 | Push 5, Push 3, Push 2 | [5, 3, 2]
* | op2=2, op1=3 -> 3*2=6 | [5, 6]
+ | op2=6, op1=5 -> 5+6=11 | [11]
9 | Push 9 | [11, 9]
- | op2=9, op1=11 -> 11-9=2| [2]
4 | Push 4 | [2, 4]
/ | op2=4, op1=2 -> 2/4=0 | [0] (int div)
Postfix Expression Evaluation using Stack Quick Reference & Comparison Table
| Evaluation Component | Stack Rule & Scan Direction | Critical Exam Note |
|---|---|---|
| Numeric Operand | Push value directly onto Operand Stack | Multi-digit operands need delimiter separation |
| Binary Operator (Postfix) | Pop op2 first, op1 second; push (op1 op op2) | Order prevents sign/fraction errors on -, /, ^ |
| Final Valid Stack State | Exactly 1 item remains (the final answer) | >1 left or Underflow implies malformed expression |
| Prefix Evaluation Rule | Scan Right-to-Left; pop op1 first, op2 second | Both Prefix & Postfix evaluate in O(n) time |
Postfix Expression Evaluation using Stack Top 20 Bilingual MCQs with Answers
Q1. During Postfix Expression Evaluation using a stack, what items are pushed onto the stack?
(स्टैक द्वारा पोस्टफिक्स व्यंजक का मूल्यांकन करते समय स्टैक में किन्हें पुश किया जाता है?)
(A) Only operators (+, -, *, /)
(B) Parentheses and operators
(C) Operators first, then operands
(D) Operands (numeric values and intermediate computed results)
Correct Answer: (D)
[EN] Postfix evaluation pushes numeric operands and intermediate results onto the stack, applying operators immediately when scanned.
[HI] पोस्टफिक्स मूल्यांकन में स्टैक पर संख्यात्मक ऑपरेंड और गणना के मध्यवर्ती परिणाम पुश किए जाते हैं, न कि ऑपरेटर।
Q2. When evaluating Postfix '15 3 /' using a stack, after pushing 15 then 3, which value is popped first and what expression is computed?
(पोस्टफिक्स '15 3 /' का मूल्यांकन करते समय पहले 15 फिर 3 पुश करने के बाद, '/' आने पर पहले क्या पॉप होगा और कौन सी गणना चलेगी?)
(A) 3 is popped first (op1), 15 second (op2), computing 3 / 15 = 0
(B) Only 3 is popped and divided by stack bottom
(C) 15 is popped first (op1), 3 second (op2), computing 15 / 3
(D) 3 is popped first (op2), 15 is popped second (op1), computing 15 / 3 = 5
Correct Answer: (D)
[EN] The top of stack holds the latest operand (right operand op2 = 3), and below it sits left operand op1 = 15, yielding op1 / op2 = 5.
[HI] स्टैक के शीर्ष पर बाद में आया दायाँ ऑपरेंड (op2 = 3) होता है और नीचे बायाँ ऑपरेंड (op1 = 15), इसलिए गणना 15 / 3 = 5 होगी।
Q3. Evaluate the Postfix expression: 6 2 3 + - 3 8 2 / + * 2 ^ 3 +
(पोस्टफिक्स व्यंजक '6 2 3 + - 3 8 2 / + * 2 ^ 3 +' का सही अंतिम मान क्या होगा?)
(A) 49
(B) 52
(C) 55
(D) 28
Correct Answer: (B)
[EN] 2+3=5; 6-5=1; 8/2=4; 3+4=7; 1*7=7; 7^2=49; 49+3=52.
[HI] चरण: 2+3=5 -> 6-5=1 -> 8/2=4 -> 3+4=7 -> 1*7=7 -> 7^2=49 -> 49+3=52।
Q4. Evaluate the Postfix expression: 10 2 8 * + 3 -
(पोस्टफिक्स व्यंजक '10 2 8 * + 3 -' का सही मान क्या प्राप्त होगा?)
(A) 29
(B) 13
(C) 23
(D) 93
Correct Answer: (C)
[EN] Push 10, 2, 8 -> '*' gives 2*8=16 -> '+' gives 10+16=26 -> push 3 -> '-' gives 26-3=23.
[HI] 10, 2, 8 पुश -> 2*8=16 -> 10+16=26 -> 3 पुश -> 26-3=23 उत्तर आता है।
Q5. Evaluate the Postfix expression: 2 3 1 * + 9 -
(पोस्टफिक्स व्यंजक '2 3 1 * + 9 -' को हल करने पर क्या परिणाम प्राप्त होगा?)
(A) 14
(B) -4
(C) 4
(D) -2
Correct Answer: (B)
[EN] 3*1=3; 2+3=5; then op2=9, op1=5 gives 5 - 9 = -4.
[HI] 3*1=3 -> 2+3=5 -> अंत में op1=5 और op2=9 होने से 5 - 9 = -4 प्राप्त होता है।
Q6. Evaluate the Postfix expression: 12 3 / 2 3 ^ *
(पोस्टफिक्स व्यंजक '12 3 / 2 3 ^ *' का सटीक मान क्या होगा?)
(A) 32
(B) 64
(C) 36
(D) 24
Correct Answer: (A)
[EN] 12 / 3 = 4; push 2, 3; 2 ^ 3 = 8; 4 * 8 = 32.
[HI] 12 / 3 = 4, फिर 2 ^ 3 = 8, और अंत में 4 * 8 = 32 प्राप्त होता है।
Q7. Evaluate the Postfix expression: 4 3 2 ^ + 5 -
(पोस्टफिक्स व्यंजक '4 3 2 ^ + 5 -' का सही परिणाम क्या है?)
(A) 8
(B) 7
(C) 11
(D) 4
Correct Answer: (A)
[EN] 3 ^ 2 = 9; 4 + 9 = 13; 13 - 5 = 8.
[HI] 3 ^ 2 = 9, फिर 4 + 9 = 13, और अंत में 13 - 5 = 8 आता है।
Q8. When evaluating '10 2 8 * + 3 -', which elements sit inside the stack from bottom to top right BEFORE '*' executes?
('10 2 8 * + 3 -' का मूल्यांकन करते समय '*' ऑपरेटर चलने से ठीक पहले स्टैक में नीचे से ऊपर कौन से मान मौजूद होते हैं?)
(A) [10, 16]
(B) [10, 2, 8]
(C) [8, 2, 10]
(D) [2, 8]
Correct Answer: (B)
[EN] Tokens 10, 2, and 8 are pushed sequentially before '*' arrives, placing 8 on top above 2 and 10.
[HI] '*' आने से पहले क्रमशः 10, 2 और 8 स्टैक में पुश होते हैं, जिससे नीचे से ऊपर [10, 2, 8] रहता है।
Q9. After completing the scan of a valid Postfix expression, how many elements MUST remain inside the operand stack?
(किसी वैध पोस्टफिक्स व्यंजक का पूरा स्कैन समाप्त होने पर ऑपरेंड स्टैक में कितने तत्व शेष रहने चाहिए?)
(A) 2 elements
(B) Exactly 1 (the final evaluated result)
(C) Equal to the number of operators
(D) 0 (empty stack)
Correct Answer: (B)
[EN] Each binary operator reduces count by 1; a well-formed expression leaves exactly 1 item at the end.
[HI] प्रत्येक बाइनरी ऑपरेटर दो को एक में बदलता है; अंत में स्टैक में केवल 1 ही अंतिम परिणाम बचना चाहिए।
Q10. What happens if you scan Postfix '5 3 + *' with an operand stack?
(यदि पोस्टफिक्स स्ट्रिंग '5 3 + *' का स्टैक द्वारा मूल्यांकन किया जाए, तो क्या होगा?)
(A) It evaluates to 40
(B) It leaves two values [5, 3] on the stack
(C) Stack Underflow when '*' tries to pop 2 operands because only [8] is on the stack
(D) It evaluates to 8
Correct Answer: (C)
[EN] 5 + 3 pushes 8 (stack size 1); '*' requires 2 operands so the second pop fails with Underflow, revealing an invalid postfix string.
[HI] 5 + 3 से स्टैक में केवल [8] बचता है; इसके बाद '*' के लिए 2 ऑपरेंड न मिलने से Stack Underflow होकर अवैध व्यंजक पकड़ा जाता है।
Q11. What happens at the end of scanning '5 4 3 +' (missing an operator)?
(यदि अधूरे पोस्टफिक्स व्यंजक '5 4 3 +' का मूल्यांकन किया जाए, तो स्कैन समाप्त होने पर स्टैक की स्थिति क्या होगी?)
(A) Valid answer 12 is returned
(B) Valid answer 5 is returned
(C) Invalid expression detected because 2 items [5, 7] remain on the stack instead of 1
(D) Stack Underflow occurs during '+'
Correct Answer: (C)
[EN] 4 + 3 pushes 7 beside 5; ending with size > 1 proves too many operands / too few operators.
[HI] 4 + 3 = 7 होने के बाद स्टैक में [5, 7] दो मान बच जाते हैं (1 नहीं), जिससे अपूर्ण व्यंजक की त्रुटि पकड़ी जाती है।
Q12. In contrast to Postfix, how does Prefix Expression Evaluation scan tokens and assign op1/op2?
(पोस्टफिक्स के विपरीत, प्रीफिक्स व्यंजक का मूल्यांकन किस दिशा में होता है और op1 व op2 कैसे पॉप होते हैं?)
(A) Scans Left-to-Right; first popped is op2, second is op1
(B) Scans Right-to-Left; first popped is op2, second is op1
(C) Scans from middle outward
(D) Scans Right-to-Left; first popped value is op1 (left), second popped value is op2 (right)
Correct Answer: (D)
[EN] Scanning Prefix right-to-left sees right operand pushed before left operand, so top of stack is op1 and below it is op2.
[HI] प्रीफिक्स को दाएं-से-बाएं स्कैन करने पर पहले दायाँ और फिर बायाँ ऑपरेंड पुश होता है, अतः पहला पॉप op1 और दूसरा op2 बनता है।
Q13. Evaluate the Prefix expression: + * 2 3 - 8 4
(प्रीफिक्स व्यंजक '+ * 2 3 - 8 4' का सही मान क्या होगा?)
(A) 10
(B) 14
(C) -2
(D) 2
Correct Answer: (A)
[EN] Scanning R->L: push 4, 8 -> '-' computes 8-4=4; push 3, 2 -> '*' computes 2*3=6; '+' computes 6+4=10.
[HI] दाएं-से-बाएं: 8-4=4, फिर 2*3=6, और अंत में 6+4=10 उत्तर आता है।
Q14. What is the time and auxiliary space complexity of evaluating a valid n-token Postfix expression?
(n टोकन वाले किसी वैध पोस्टफिक्स व्यंजक के मूल्यांकन की टाइम और स्पेस कॉम्प्लेक्सिटी क्या होती है?)
(A) O(n^2) time and O(1) space
(B) O(n) time and O(n) worst-case space
(C) O(1) time and O(1) space
(D) O(n log n) time and O(n) space
Correct Answer: (B)
[EN] Each token is processed once in O(1), and up to (n+1)/2 operands can reside simultaneously on the stack (e.g., all numbers before operators).
[HI] प्रत्येक टोकन एक ही बार प्रोसेस होता है (O(n) समय), और स्टैक में अधिकतम O(n) ऑपरेंड जमा हो सकते हैं।
Q15. Why is writing '123+' without spaces ambiguous in a multi-digit Postfix evaluator?
(बहु-अंकीय संख्याओं वाले पोस्टफिक्स मूल्यांकनकर्ता में बिना स्पेस के '123+' लिखना अस्पष्ट क्यों होता है?)
(A) '+' cannot execute on integers larger than 9
(B) Spaces are treated as multiplication operators
(C) Postfix forbids two-digit integers
(D) The evaluator cannot tell whether '123' means (12 and 3), (1 and 23), or (1, 2, and 3)
Correct Answer: (D)
[EN] Without token delimiters (whitespace/commas), adjacent digits merge ambiguously; multi-digit RPN always requires separators.
[HI] स्पेस या कॉमा डिलीमीटर न होने पर यह पता नहीं चलता कि '123' का अर्थ '12 व 3' है या '1 व 23'; अतः विभाजक अनिवार्य है।
Q16. Which statement is FALSE about Postfix Expression Evaluation?
(पोस्टफिक्स एक्सप्रेशन मूल्यांकन के बारे में निम्नलिखित में से कौन सा कथन असत्य (FALSE) है?)
(A) It requires an operator precedence table during evaluation to decide which operator runs first
(B) It pops the right operand op2 before the left operand op1
(C) It completes in a single O(n) left-to-right pass
(D) It pushes numeric operands onto the stack rather than operators
Correct Answer: (A)
[EN] Postfix already encodes precedence in token ordering, so evaluation NEVER consults any precedence table or parentheses.
[HI] पोस्टफिक्स में प्राथमिकता पहले से ही क्रम में तय होती है; मूल्यांकन के समय किसी भी प्रेसिडेंस टेबल की आवश्यकता नहीं पड़ती।
Q17. Within Postfix Expression Evaluation using Stack, which evaluation component directly maps to: "Push value directly onto Operand Stack"?
(Postfix Expression Evaluation using Stack में कौन सा Evaluation Component सीधे "Push value directly onto Operand Stack" से संबंधित है?)
(A) Numeric Operand
(B) Binary Operator (Postfix)
(C) Prefix Evaluation Rule
(D) Final Valid Stack State
Correct Answer: (A)
[EN] In Postfix Expression Evaluation using Stack, 'Numeric Operand' handles 'Push value directly onto Operand Stack' (Multi-digit operands need delimiter separation).
[HI] Postfix Expression Evaluation using Stack में 'Numeric Operand' का कार्य/विवरण 'Push value directly onto Operand Stack' (Multi-digit operands need delimiter separation) है।
Q18. Which option accurately describes 'Binary Operator (Postfix)' in Postfix Expression Evaluation using Stack?
(Postfix Expression Evaluation using Stack के संदर्भ में 'Binary Operator (Postfix)' की सही विशेषता कौन सी है?)
(A) Push value directly onto Operand Stack
(B) Scan Right-to-Left; pop op1 first, op2 second
(C) Exactly 1 item remains (the final answer)
(D) Pop op2 first, op1 second; push (op1 op op2)
Correct Answer: (D)
[EN] 'Binary Operator (Postfix)' provides 'Pop op2 first, op1 second; push (op1 op op2)' — key point: Order prevents sign/fraction errors on -, /, ^.
[HI] 'Binary Operator (Postfix)' का मुख्य विवरण 'Pop op2 first, op1 second; push (op1 op op2)' है (Order prevents sign/fraction errors on -, /, ^)।
Q19. In Postfix Expression Evaluation using Stack, identify the correct parameter for the specification: "Exactly 1 item remains (the final answer)".
(Postfix Expression Evaluation using Stack में "Exactly 1 item remains (the final answer)" विवरण किस विकल्प के लिए सही है?)
(A) Numeric Operand
(B) Prefix Evaluation Rule
(C) Final Valid Stack State
(D) Binary Operator (Postfix)
Correct Answer: (C)
[EN] 'Final Valid Stack State' corresponds to 'Exactly 1 item remains (the final answer)' (>1 left or Underflow implies malformed expression).
[HI] 'Final Valid Stack State' का संबंध 'Exactly 1 item remains (the final answer)' (>1 left or Underflow implies malformed expression) से है।
Q20. Considering Postfix Expression Evaluation using Stack, what key behavior defines 'Prefix Evaluation Rule'?
(Postfix Expression Evaluation using Stack में 'Prefix Evaluation Rule' की मुख्य भूमिका या मान क्या है?)
(A) Push value directly onto Operand Stack
(B) Scan Right-to-Left; pop op1 first, op2 second
(C) Pop op2 first, op1 second; push (op1 op op2)
(D) Exactly 1 item remains (the final answer)
Correct Answer: (B)
[EN] 'Prefix Evaluation Rule' represents 'Scan Right-to-Left; pop op1 first, op2 second' (Both Prefix & Postfix evaluate in O(n) time).
[HI] 'Prefix Evaluation Rule' का अर्थ/मान 'Scan Right-to-Left; pop op1 first, op2 second' है (Both Prefix & Postfix evaluate in O(n) time)।
Postfix Expression Evaluation using Stack — Exam FAQs
Q1: What happens if a Postfix expression contains a bug where op1 - op2 is mistakenly coded as op2 - op1?
यदि पोस्टफिक्स मूल्यांकन कोड में गलती से op1 - op2 की बजाय op2 - op1 लिख दिया जाए, तो क्या असर होगा?
[EN] Commutative operators (+, *) still look right, masking the bug, while subtraction and division produce negated or inverted results (e.g., '10 3 -' gives -7 instead of +7).
[HI] + और * तो सही चलेंगे जिससे बग छिप सकता है, पर घटाव और भाग के उत्तर उल्टे आएंगे (जैसे '10 3 -' का उत्तर +7 की बजाय -7 आएगा)।
Q2: Why do calculators like HP RPN models and Forth/JVM use Postfix evaluation?
कुछ कैलकुलेटर और JVM/Forth जैसी वर्चुअल मशीनें पोस्टफिक्स मूल्यांकन क्यों चुनती हैं?
[EN] Because there are no parentheses keys or backtracking parsers needed—each entered operation fires immediately on the stack top in constant time.
[HI] क्योंकि इसमें कोष्ठक या बैकट्रैकिंग पार्सर नहीं चाहिए; हर ऑपरेटर सीधे स्टैक के ऊपरी दो मानों पर तुरंत गणना कर देता है।
Q3: Can a single-token Postfix expression like '42' (with 0 operators) be valid?
क्या बिना किसी ऑपरेटर वाला केवल एक संख्या '42' जैसा पोस्टफिक्स व्यंजक वैध है?
[EN] Yes! Pushing 42 leaves exactly 1 value on the stack at the end of scanning, which satisfies the single-result validity invariant.
[HI] हाँ! 42 को पुश करने के बाद अंत में स्टैक पर ठीक 1 मान (42) ही बचता है, जो वैध पोस्टफिक्स की शर्त पूरी करता है।
Post a Comment
Post a Comment