Infix to Postfix and Postfix Evaluation

Infix to Postfix and Postfix Evaluation

Expressions को represent करने के अलग-अलग तरीके होते हैं। Programming और data structures में मुख्यतः Infix, Prefix और Postfix notations का उपयोग किया जाता है। Stack का उपयोग विशेष रूप से Infix expression को Postfix में convert करने और Postfix expression को evaluate करने में किया जाता है।

Types of Expression Notation

1. Infix Expression

जिस expression में operator अपने operands के बीच में लिखा जाता है, उसे Infix Expression कहते हैं। सामान्य mathematical expressions प्रायः infix notation में लिखे जाते हैं।

उदाहरण:

Infix expression मनुष्य के लिए पढ़ना आसान है, लेकिन computer द्वारा इसे directly evaluate करने के लिए operator precedence और parentheses को handle करना पड़ता है।

2. Prefix Expression

जिस expression में operator operands से पहले आता है, उसे Prefix Expression कहते हैं।

उदाहरण:

3. Postfix Expression

जिस expression में operator operands के बाद आता है, उसे Postfix Expression कहते हैं। इसे Reverse Polish Notation (RPN) भी कहा जाता है।

उदाहरण:

Postfix expression में सामान्यतः parentheses की आवश्यकता नहीं होती क्योंकि operators का स्थान evaluation का क्रम स्पष्ट कर देता है।

Infix vs Postfix

Operator Precedence

Infix expression को postfix में convert करते समय operators की precedence को ध्यान में रखना आवश्यक है। Higher precedence वाला operator पहले process किया जाता है।

Associativity

जब दो operators की precedence समान होती है, तो associativity यह निर्धारित करती है कि कौन-सा operator पहले process होगा। सामान्य arithmetic operators जैसे +, -, *, /, % left-to-right associativity रखते हैं।

Infix to Postfix Conversion Using Stack

Infix expression को postfix में convert करने के लिए एक stack का उपयोग किया जाता है। Expression को left से right की ओर scan किया जाता है।

Basic Rules for Conversion

1. यदि scanned symbol operand है, तो उसे सीधे output में add करें।
2. यदि symbol '(' है, तो उसे stack में push करें।
3. यदि symbol ')' है, तो stack से operators को pop करके output में add करें जब तक '(' न मिल जाए। फिर '(' को remove करें।
4. यदि symbol operator है, तो stack के top operator की precedence की तुलना current operator से करें।
5. यदि stack का top operator higher या equal precedence का है, तो उसे pop करके output में add करें।
6. Current operator को stack में push करें।
7. Expression समाप्त होने के बाद stack में बचे सभी operators को pop करके output में add करें।

Example 1: A + B

Expression: A + B

Example 2: A + B * C

यहाँ * की precedence + से अधिक है। इसलिए multiplication पहले postfix में आएगा।

Example 3: (A + B) * C

Parentheses की वजह से A + B पहले process होगा।

Step-by-Step Conversion of (A + B) * C

C++ Program for Infix to Postfix

नीचे C++ program stack की सहायता से infix expression को postfix expression में convert करता है। यह example single-character operands और सामान्य arithmetic operators के लिए है।

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;

int precedence(char op)
{
    if (op == '+' || op == '-')
        return 1;

    if (op == '*' || op == '/' || op == '%')
        return 2;

    return 0;
}

string infixToPostfix(string infix)
{
    stack<char> s;
    string postfix;

    for (char ch : infix)
    {
        if (isalnum(ch))
        {
            postfix += ch;
        }
        else if (ch == '(')
        {
            s.push(ch);
        }
        else if (ch == ')')
        {
            while (!s.empty() && s.top() != '(')
            {
                postfix += s.top();
                s.pop();
            }

            if (!s.empty())
                s.pop();
        }
        else
        {
            while (!s.empty() &&
                   precedence(s.top()) >= precedence(ch))
            {
                postfix += s.top();
                s.pop();
            }

            s.push(ch);
        }
    }

    while (!s.empty())
    {
        postfix += s.top();
        s.pop();
    }

    return postfix;
}

int main()
{
    string infix = "A+B*C";

    cout << "Infix: " << infix << endl;
    cout << "Postfix: " << infixToPostfix(infix);

    return 0;
}

Postfix Evaluation

Postfix expression को evaluate करने के लिए भी stack का उपयोग किया जाता है। Expression को left से right scan किया जाता है।

Rules for Postfix Evaluation

1. Expression को left से right scan करें।
2. यदि symbol operand है, तो उसे stack में push करें।
3. यदि symbol operator है, तो stack से दो operands pop करें।
4. पहला popped value second operand होता है और दूसरा popped value first operand होता है।
5. Operation perform करके result को stack में push करें।
6. Expression समाप्त होने पर stack में बचा हुआ element final result होता है।

Example: Postfix Evaluation of 23*5+

Postfix expression:

Important Point in Postfix Evaluation

Subtraction और division जैसे operations में operands का order बहुत महत्वपूर्ण होता है। उदाहरण के लिए postfix expression 82- में:

इसी प्रकार 82/ का result होगा:

C++ Program for Postfix Evaluation

नीचे दिया गया program single-digit operands वाले postfix expression को evaluate करता है।

#include <iostream>
#include <stack>
#include <cctype>
using namespace std;

int main()
{
    string postfix = "23*5+";

    stack<int> s;

    for (char ch : postfix)
    {
        if (isdigit(ch))
        {
            s.push(ch - '0');
        }
        else
        {
            int second = s.top();
            s.pop();

            int first = s.top();
            s.pop();

            int result;

            switch (ch)
            {
                case '+':
                    result = first + second;
                    break;

                case '-':
                    result = first - second;
                    break;

                case '*':
                    result = first * second;
                    break;

                case '/':
                    result = first / second;
                    break;

                case '%':
                    result = first % second;
                    break;
            }

            s.push(result);
        }
    }

    cout << "Result = " << s.top();

    return 0;
}

Another Example of Postfix Evaluation

Consider the postfix expression:

Step-by-step:

• 5 push
• 2 push
• + → 5 + 2 = 7
• 8 push
• 3 push
• - → 8 - 3 = 5
• * → 7 × 5 = 35

Infix to Postfix vs Postfix Evaluation

Applications

Infix to postfix conversion और postfix evaluation का उपयोग कई programming और computer science applications में किया जाता है:

• Expression evaluation में।
• Compiler और interpreter design में।
• Calculators में।
• Programming language expression processing में।
• Stack-based computation में।
• Arithmetic expression parsing में।

Important Points

• Infix में operator operands के बीच होता है।
• Prefix में operator operands से पहले होता है।
• Postfix में operator operands के बाद होता है।
• Postfix को Reverse Polish Notation भी कहा जाता है।
• Infix to postfix conversion में stack का उपयोग किया जाता है।
• Postfix evaluation में भी stack का उपयोग किया जाता है।
• Operands को postfix conversion के दौरान सीधे output में भेजा जाता है।
• Operators को precedence के अनुसार stack में रखा जाता है।
• Postfix evaluation में operand मिलने पर उसे stack में push किया जाता है।
• Operator मिलने पर दो operands pop करके operation किया जाता है।
• Subtraction और division में पहला popped element second operand होता है।
• Postfix expression में parentheses की आवश्यकता सामान्यतः नहीं होती।

Board Focus

Board Important Questions

Very Short Answer Questions

Q1. Infix expression क्या है?

Answer: जिस expression में operator operands के बीच में होता है, उसे infix expression कहते हैं।

Q2. Postfix expression क्या है?

Answer: जिस expression में operator operands के बाद आता है, उसे postfix expression कहते हैं।

Q3. Postfix notation का दूसरा नाम क्या है?

Answer: Reverse Polish Notation (RPN)।

Q4. Infix to postfix conversion में किस data structure का उपयोग किया जाता है?

Answer: Stack का उपयोग किया जाता है।

Q5. Postfix evaluation में किस data structure का उपयोग किया जाता है?

Answer: Stack का उपयोग किया जाता है।

Q6. A + B का postfix क्या होगा?

Answer: AB+

Q7. A * B का postfix क्या होगा?

Answer: AB*

Q8. A + B * C का postfix क्या होगा?

Answer: ABC*+

Short Answer Questions

Q9. Infix और Postfix notation में अंतर बताइए।

Answer: Infix notation में operator operands के बीच होता है, जबकि postfix notation में operator operands के बाद आता है। उदाहरण: A + B का postfix AB+ है।

Q10. Infix to postfix conversion में operator precedence का क्या महत्व है?

Answer: Operator precedence यह निर्धारित करती है कि कौन-सा operator पहले process किया जाएगा। Higher precedence वाले operators को lower precedence वाले operators से पहले postfix output में रखा जाता है।

Q11. Postfix expression में parentheses की आवश्यकता क्यों नहीं होती?

Answer: Postfix notation में operators का स्थान evaluation का क्रम स्पष्ट करता है, इसलिए सामान्यतः parentheses की आवश्यकता नहीं होती।

Q12. Postfix evaluation में operator मिलने पर क्या किया जाता है?

Answer: Stack से दो operands pop किए जाते हैं, उन पर operator का operation किया जाता है और result को वापस stack में push किया जाता है।

Q13. Postfix evaluation में operand मिलने पर क्या किया जाता है?

Answer: Operand को stack में push किया जाता है।

Expression-Based Questions

Q14. निम्न Infix expressions को Postfix में convert कीजिए:

• A + B → AB+
• A + B * C → ABC*+
• (A + B) * C → AB+C*
• A * B + C → AB*C+
• (A + B) / (C - D) → AB+CD-/
• A * (B + C) → ABC+*

Q15. निम्न Postfix expressions को evaluate कीजिए:

• 23+ → 5
• 23* → 6
• 23*5+ → 11
• 52+83-* → 35
• 82/3+ → 7

Long Answer Questions

Q16. Infix expression को postfix expression में convert करने के rules समझाइए।

Answer: Expression को left से right scan किया जाता है। Operand को सीधे output में भेजा जाता है। Opening parenthesis को stack में push किया जाता है। Closing parenthesis मिलने पर opening parenthesis तक operators को pop किया जाता है। Operator मिलने पर precedence के आधार पर stack से operators को pop करके output में भेजा जाता है और current operator को push किया जाता है। Expression समाप्त होने के बाद stack में बचे सभी operators को output में भेज दिया जाता है।

Q17. Postfix expression को evaluate करने की प्रक्रिया समझाइए।

Answer: Postfix expression को left से right scan किया जाता है। प्रत्येक operand को stack में push किया जाता है। Operator मिलने पर stack से दो operands pop किए जाते हैं। Operation perform करने के बाद result को stack में push किया जाता है। Expression समाप्त होने पर stack में बचा element final result होता है।

Q18. Infix expression A + B * C को postfix में convert करने का C++ program लिखिए।

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int precedence(char op)
{
    if (op == '+' || op == '-')
        return 1;

    if (op == '*' || op == '/')
        return 2;

    return 0;
}

int main()
{
    string infix = "A+B*C";
    string postfix;
    stack<char> s;

    for (char ch : infix)
    {
        if (ch >= 'A' && ch <= 'Z')
        {
            postfix += ch;
        }
        else
        {
            while (!s.empty() &&
                   precedence(s.top()) >= precedence(ch))
            {
                postfix += s.top();
                s.pop();
            }

            s.push(ch);
        }
    }

    while (!s.empty())
    {
        postfix += s.top();
        s.pop();
    }

    cout << "Postfix: " << postfix;

    return 0;
}

Q19. Postfix expression 23*5+ को evaluate करने का C++ program लिखिए।

#include <iostream>
#include <stack>
#include <cctype>
using namespace std;

int main()
{
    string postfix = "23*5+";
    stack<int> s;

    for (char ch : postfix)
    {
        if (isdigit(ch))
        {
            s.push(ch - '0');
        }
        else
        {
            int b = s.top();
            s.pop();

            int a = s.top();
            s.pop();

            if (ch == '+')
                s.push(a + b);
            else if (ch == '-')
                s.push(a - b);
            else if (ch == '*')
                s.push(a * b);
            else if (ch == '/')
                s.push(a / b);
        }
    }

    cout << "Result = " << s.top();

    return 0;
}

Quick Revision

• Infix: A + B
• Prefix: + A B
• Postfix: A B +
• Postfix का दूसरा नाम: Reverse Polish Notation
• Infix to Postfix: Stack का उपयोग
• Postfix Evaluation: Stack का उपयोग
• Operand: Conversion में output, evaluation में push
• Operator: Conversion में precedence के अनुसार process
• Postfix Evaluation: Operator मिलने पर दो operands pop
• First popped: Second operand
• Second popped: First operand

Practice Questions

1. Infix, Prefix और Postfix notation को उदाहरण सहित समझाइए।
2. Postfix notation को Reverse Polish Notation क्यों कहा जाता है?
3. Stack की सहायता से infix को postfix में convert करने के rules लिखिए।
4. A + B का postfix लिखिए।
5. A + B * C का postfix लिखिए।
6. (A + B) * C का postfix लिखिए।
7. A * (B + C) का postfix लिखिए।
8. (A + B) / (C - D) का postfix लिखिए।
9. Postfix expression को evaluate करने के steps लिखिए।
10. 23*5+ को evaluate कीजिए।
11. 52+83-* को evaluate कीजिए।
12. Infix to postfix conversion का C++ program लिखिए।
13. Postfix expression evaluation का C++ program लिखिए।
14. Operator precedence का infix to postfix conversion में क्या महत्व है?
15. Postfix evaluation में operands के order का महत्व उदाहरण सहित समझाइए।