हैलो दोस्तों, स्वागत है हमारे ब्लॉक में। आज की पोस्ट में हम बात करेंगे कि एक Infix expression को prefix expression में कैसे convert किया जाता है? यह एक बहुत ही simple operation है जिसे समझना बहुत ही important है अगर आप अच्छे से Data structures and algorithms पढ़ना चाहते हैं. Infix to prefix conversion using stack के लिए कुछ rules को follow करना पड़ता है, जिन्हें follow करके आप आसानी से Infix to prefix conversion कर सकते हैं आज की पोस्ट में हम rules for Infix to prefix conversion using stack in Hindi पर बात करेंगे. जिसके बाद infix to prefix conversion using stack करने में आपको कोई problem नहीं होगी।
Rules for Infix to prefix conversion using stack in Hindi
किसी भी दिए गए इन Infix expression को following rules को use करके prefix expression में convert किया जा सकता है
Rule 1 : सबसे पहले दिए गए Infix expression को reverse करके लिख दीजिए.
Rule 2: अब सभी characters को एक array की तरह मान लीजिए और इसे Left to Right की ओर solve करना शुरू करते हैं
Rule 3: जब भी expression में कोई operand आता है तो उसे आउटपुट में print कर देते हैं.
Rule 4: अगर expression में कोई Operator आता है और stack empty है तब operator को stack में push कर देते हैं.
Rule 5: अगर incoming Operator की precedence Stack के top से ज्यादा है तब incoming Operator को stack में push कर देते हैं.
Rule 6: अगर incoming ऑपरेटर की precedence Stack के top के बराबर है तो incoming ऑपरेटर को stack में push कर देते हैं.
Rule 7: अगर incoming Operator की precedence Stack के top से कम है, तब stack के top को pop करके आउटपुट में print कर देते हैं तथा फिर से incoming Operator की precedence Stack के top से check करते हैं, अगर precedence ज्यादा या same है तो ऑपरेटर को Stack में push कर देते हैं.
Rule 8: अगर incoming ऑपरेटर ' ^ ' Caret symbol है और stack का top भी caret symbol है तब stack के top को pop कर के आउटपुट में print कर देते हैं. और जैसे ही यह condition false हो जाती है, caret operator को स्टैक में push कर देते हैं
Rule 9: अगर incoming ऑपरेटर ' ) ' है तब इसे stack में push कर देते हैं.
Rule 10: अगर incoming ऑपरेटर ' ( ' है तब stack के top को pop करके आउटपुट में तब तक print करते हैं जब तक की corresponding ' ) ' ना मिल जाए
Rule 11: जब expression end हो जाए, और कोई ऑपरेटर तथा Operand ना बचा हो, तब सभी ऑपरेटर को stack से LIFO manner में pop कर के आउटपुट में print कर देते हैं
Rule 12: End में आउटपुट को reverse कर देते हैं.
Infix to prefix conversion using stack in Hindi
नीचे कुछ उदाहरण दिए गए हैं जिन्हें ऊपर लिखे गए सभी रूल्स को फॉलो करके solve किया गया है इन examples से आपको Infix to prefix conversion को आसानी से समझने में मदद मिलेगी।
इन्हें सॉल्व करने के लिए हमने एक टेबल बनाई है, जिसमें सबसे पहले column में incoming ऑपरेटर लिखा है, जिसमें one by one Array के characters को लिखा गया है. दूसरे column में stack है जिसमें ऑपरेटर पर push and pop ऑपरेशन किए जाएंगे तथा तीसरे कॉलम में आउटपुट लिखा गया है।
Example 1: K+L-M*N+(O^P)*W/U/V*T+Q
Rule 1: Reverse Expression
Q+T*V/U/W*)P^O(+N*M-L+K
| Incoming Character | Stack | Output |
|---|---|---|
| Q | Empty | Q |
| + | + (rule 4) | Q |
| T | + | QT |
| * | +* (rule 5) | QT |
| V | +* | QTV |
| / | +*/ (rule 6) | QTV |
| U | +*/ | QTVU |
| / | +*// (rule 6) | QTVU |
| W | +*// | QTVUW |
| * | +*//* (rule 6) | QTVUW |
| ) | +*//*) (rule 9) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ (rule 8) | QTVUWP |
| O | +*//*)^ | QTVUWPO |
| ( | +*//* (rule 10) | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | ++* (rule 5) | QTVUWPO^*//*N |
| M | ++* | QTVUWPO^*//*NM |
| - | ++- (rule 7) | QTVUWPO^*//*NM* |
| L | ++- | QTVUWPO^*//*NM*L |
| + | ++-+ (rule 6) | QTVUWPO^*//*NM*L |
| K | ++-+ | QTVUWPO^*//*NM*LK |
| empty | pop & print all the operators (rule 11) | QTVUWPO^*//*NM*LK+-++ |
Rule 12: Reverse output: ++-+KL*MN*//*^OPWUVTQ
Finale prefix expression : + + - +K L*MN*//*^OPWUVTQ
Related Posts:
Infix, prefix and postfix expressions in Data Structure in Hindi
Rules to convert Infix to postfix Using stack in Hindi with example