हैलो दोस्तों, आज की पोस्ट में हम बात करेंगे कि data structures में Infix to postfix expression को stack की सहायता से कैसे solve करें. यह बहुत ही आसान है बस आपको कुछ rules का ध्यान रखना है जिन्हें आज हम इस पोस्ट में बताने वाले हैं. इस पोस्ट को पढ़ने के बाद आपको Infix to postfix conversion के सवाल करने में कोई दिक्कत नहीं होगी तो पोस्ट को end तक जरूर पढ़िए, चलिए शुरू करते हैं Infix to postfix expression conversion rules using stack in Hindi
किसी भी Infix expression को postfix expression में बदलने के लिए आप उसे Array एक की तरह देख सकते हैं जिसमें सभी Operators और Operands, Array का एक element है. Expression को solve करने के लिए हम उसे Left to Right पढ़ना शुरू करते हैं और निम्नलिखित rules का use करके आसानी से postfix expression प्राप्त कर सकते हैं
Infix to postfix expression conversion rules Using stack in Hindi
Rule 1) जैसे ही expression में कोई operand आता है उसे as it is output में print कर देते हैं
Rule 2) अगर stack empty है या left paranthesis उसके top में है तो आने वाले operator को directly stack में push कर देते हैं
Rule 3) अगर incoming Operator left paranthesis ' ( ' है तो उसे stack में push देते हैं
Rule 4) अगर incoming Operator right paranthesis ' ) ' है तो stack को तब तक pop और print करते हैं जब तक left paranthesis ना मिल जाए, और paranthesis को discard कर देते हैं
Rule 5) अगर incoming Operator की precedence Stack के top से ज्यादा है तो इसे directly Stack में push कर देते हैं
Rule 6) अगर incoming Operator की precedence, Stack के top से कम है तो stack के top को pop करके output में print कर देते हैं तथा फिर से incoming Operator की precedence Stack के top से check करते हैं
Rule 7) अगर incoming Operator की precedence Stack के top के बराबर है तो Operators की associativity check करते हैं जिसके निम्नलिखित rules है
A) अगर associativity, left to right है तब stack के top को pop करके output में print कर देते हैं, जिसके बाद फिर से precedence check करते हैं और फिर incoming Operator को stack में push कर देते हैं
B) अगर associativity, right to left है तो Operator को directly stack में push कर देते हैं
Rule 8) last में जब हमारे पास कोई Operand नहीं है तब सभी Operators को LIFO manner में pop and print कर देते हैं
Finally
दोस्तों आइए आप एक example लेते हैं जिसे ऊपर दिए गए rules की मदद से step by step solve करते हैं-
How to convert Infix to postfix expression using stack in Hindi
Infix to postfix conversion Step by step explanation:
Expression को solve करने के लिए left to right पढ़ना शुरू करते हैं।
Step 1) सबसे पहले expression में A आता है जो कि एक operand है इसीलिए rule 1 को follow करते हुए A को output में print कर देते हैं
Step 2) दूसरा character minus ' - ' है जोकि एक Operator है अब हम stack के top को check करते हैं, क्योंकि Stack पूरी तरह खाली है इसीलिए Rule 2 को follow करते हुए ' - ' को stack में push कर देते हैं
Step 3) तीसरा character B है जो कि एक Operand है इसलिए फिर से Rule 1 को follow करते हुए B को output में print कर देते हैं
Step 4) चौथा character ' / ' है जोकि एक Operator है, अब stack के top से के साथ ' / ' precedence check करते हैं जोकि top से ज्यादा है, इसीलिए Rule 5 को follow करते हुए इसे stack में push कर देते हैं
Step 5) पांचवा character C है जो कि एक Operand है इसलिए Rule 1 को follow करते हुए इसे output में print कर देते हैं.
Step 6) 6th character ' * ' है जो कि एक Operator है. इसीलिए stack के top के साथ इसकी precedence check करते हैं क्योंकि * और / दोनों की precedence same है इसीलिए Rule 7 follow करके इनकी associativity check करते हैं
Associativity, left to right है इसीलिए Rule 7A follow करके / को pop करके output में print करते हैं.
अब फिर से * की precedence Stack के top से check करते हैं top में ' - ' है जिसकी precedence कम है, इसीलिए Rule 5 को follow करते हुए करते हुए इसे stack में push कर देते हैं.
Step 7) सातवा character 'D' है जो कि एक Operand है इसीलिए Rule 1 को follow करते हुए इसे output में print कर देते हैं.
Step 8) आठवां character + है जो कि एक Operator है इसीलिए stack के top से इसकी precedence check करते हैं.
Stack के top पर * है, + की precedence * से कम है इसीलिए Rule 6 को follow करते हुए * को stack से pop करके output में print करेंगे तथा फिर से + की precedence Stack के top से check करेंगे.
Stack के top में - है, अब + और - दोनों की precedence same है इसीलिए Rule 7 को follow करते हुए दोनों की associativity check करते हैं जोकि left to right है
इसीलिए Rule 7A को follow करते हुए - को stack से pop करके output में print कर देते हैं तथा फिर से + की precedence, Stack के top से check करते हैं क्योंकि top empty है इसीलिए Rule 2 को follow करते हुए + को stack में push कर देते हैं
Step 9) अब 9th character E है जो कि एक Operand है इसीलिए Rule 1 को follow करते हुए इसे output में print कर देते हैं.
Step 10) अब expression में कोई character नहीं बचा है इसीलिए Rule 8 को follow करते हुए stack में बचे हुए सभी Operators को Last In First Out manner में output में print कर देते हैं.
इस प्रकार से हमें postfix expression मिल जाता है।