Infix To Postfix

#include <iostream>
#define MAX 20
using namespace std;

class Stack
{
    char *STACK;
    int TOP = -1;

public:
    Stack();  // Default Constructer Declaration
    ~Stack(); // Destructer
    char top();
    bool empty();
    bool full();
    void push(char);
    char pop();
};

// Default Construter Definition
Stack::Stack()
{
    STACK = new (nothrow) char[MAX];
    if (!STACK)
    {
        cout << "\nMemory Allocation Failed\n";
    }
}

Stack::~Stack()
{
    delete STACK;
}

char Stack::top()
{
    if (TOP == -1)
        return '0';

    return STACK[TOP];
}

bool Stack::empty()
{
    return TOP == -1;
}

bool Stack::full()
{
    return TOP == MAX - 1;
}

void Stack::push(char ch)
{
    if (!full())
        STACK[++TOP] = ch;
    else
        cout << "\nStack OverFlow\n";
}

char Stack::pop()
{
    if (!empty())
        return STACK[TOP--];
    else
        return '0';
}

class InfixToPostfix
{
    // Stack To Store Characters of Infix Expressions
    Stack *stk;

public:
    char infix[MAX];
    char postfix[MAX];
    InfixToPostfix();  // Default Constructer Declaration
    ~InfixToPostfix(); // Destructer Declaration
    void takeInput();
    bool isValidExpression(string); // Function To Check Valid Expression
    int precedence(char); // Returns Operator of Maximum Precedence
    bool isOperator(char);// Function To Check Whether The Given Input is Operator or Not
    bool isBrackets(char);
    void infixToPostfix();
};

template <typename T>
T checkInput(T input, string content)
{
    while (!cin.good())
    {
        cout << "\nWrong Input, Please Enter It Correctly!!\n";
        cin.clear();
        cin.ignore();
        cout << content;
        cin >> input;
    }

    while (input < 0)
    {
        cout << "\nThis Input Cannot Be Negative!!\n";
        cin.clear();
        cin.ignore();
        cout << content;
        cin >> input;
    }
    return input;
}

InfixToPostfix::InfixToPostfix()
{
    stk = new (nothrow) Stack();
    if (!stk)
    {
        cout << "\nMemory Allocation Failed\n";
        exit(0);
    }
}

InfixToPostfix::~InfixToPostfix()
{
    delete stk;
}

bool InfixToPostfix::isOperator(char input)
{
    if (input == '^' || input == '/' || input == '*' || input == '+' || input == '-')
    {
        return 1;
    }
    return 0;
}

bool InfixToPostfix::isBrackets(char br)
{
    if (br == '{' || br == '}' || br == '(' || br == ')' || br == '[' || br == ']')
    {
        return 1;
    }
    return 0;
}

void InfixToPostfix::takeInput()
{
    cin.ignore();
    cout << "\nEnter a Infix Expression\n";
label1:
    cin.getline(infix, 100, '\n');

    for (int i = 0; infix[i] != '\0'; i++)
    {
        if (isalpha(infix[i]))
        {
            continue;
        }

        else if (isOperator(infix[i]))
        {
            continue;
        }

        else if (isBrackets(infix[i]))
        {
            continue;
        }

        else
        {
            cout << "\nString is Not Valid\n";
            cout << "\nPlease, Enter It Again\n";
            goto label1;
        }
    }

    cout << "\nEntered Infix Expression is : " << infix << "\n";
}

bool InfixToPostfix::isValidExpression(string infix)
{
    Stack *st = new (nothrow) Stack();
    if (!st)
    {
        cout << "\nMemory Allocation Failed\n";
        exit(0);
    }

    if (infix[0] == '}' || infix[0] == ']' || infix[0] == ')')
    {
        return 0;
    }

    string brackets;
    for (char ch : infix)
    {
        if (isBrackets(ch))
        {
            brackets.push_back(ch);
        }
    }

    for (char br : brackets)
    {
        if (br == '{' || br == '[' || br == '(')
        {
            st->push(br);
            continue;
        }

        if (st->empty())
        {
            return 0;
        }

        else if (br == '}')
        {
            char pop = st->pop();
            if (pop == '[' || pop == '(')
            {
                return 0;
            }
        }

        else if (br == ']')
        {
            char pop = st->pop();
            if (pop == '{' || pop == '(')
            {
                return 0;
            }
        }

        else if (br == ')')
        {
            char pop = st->pop();
            if (pop == '[' || pop == '{')
            {
                return 0;
            }
        }
    }
    bool empty = st->empty();
    delete st;
    return empty;
}

int InfixToPostfix::precedence(char op)
{
    if (op == '^')
    {
        return 3;
    }

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

    else if (op == '+' || op == '-')
    {
        return 1;
    }

    else
    {
        return 0;
    }
}

void InfixToPostfix::infixToPostfix()
{
    if (!isValidExpression(infix))
    {
        cout << "\nThe Expression is Not Valid!!\n";
        return;
    }

    int j = 0;
    for (int i = 0; infix[i] != '\0'; i++)
    {
        if (infix[i] == '(' || infix[i] == '[' || infix[i] == '{')
        {
            stk->push(infix[i]);
        }

        else if (isOperator(infix[i]))
        {
            if (stk->empty())
            {
                stk->push(infix[i]);
            }

            else
            {
                char top = stk->top();
                while (precedence(top) >= precedence(infix[i]))
                {
                    postfix[j++] = stk->pop();
                    top = stk->top();
                }

                if (precedence(top) < precedence(infix[i]))
                {
                    stk->push(infix[i]);
                }
            }
        }

        else if (infix[i] == '}' || infix[i] == ']' || infix[i] == ')')
        {
            char top = stk->top();
            while (top != '(' && top != '[' && top != '{')
            {
                postfix[j++] = stk->pop();
                top = stk->top();
            }
            stk->pop();
        }

        else
        {
            postfix[j++] = infix[i];
        }
    }

    while (!stk->empty())
    {
        char pop = stk->pop();
        postfix[j++] = pop;
    }
    postfix[j] = '\0';
    cout << "\nInfix Expression is Successfully Converted Into Postfix Expression\n";
}

int main()
{
    bool isInput = false;
    bool isInfixToPostfix = false;
    InfixToPostfix *ITP = new (nothrow) InfixToPostfix();
    if (!ITP)
    {
        cout << "\nMemery Allocation Failed\n";
    }

    while (true)
    {
        int userInput;
        string content("\n1. Press 1 To Take Input\n2. Press 2 To Convert From Infix To Postfix\n
                    3. Press 3 To Print Postfix Expression\n4. Press 4 To Exit\n>>>> ");
        cout << content;
        cin >> userInput;
        userInput = checkInput(userInput, content);

        switch (userInput)
        {
        case 1:
            ITP->takeInput();
            isInput = true;
            break;

        case 2:
            if (!isInput)
            {
                cout << "\nYou Have Not Taken Any Input!!\n";
                break;
            }

            ITP->infixToPostfix();

            if (!(ITP->postfix[0] == '\0'))
            {
                isInfixToPostfix = true;
            }
            break;

        case 3:
            if (!isInfixToPostfix)
            {
                cout << "\nInfix Expression is Not Converted Into Postfix Expression\n";
                break;
            }
            cout << "\nPostfix Expression : ";
            for (int i = 0; ITP->postfix[i] != '\0'; i++)
            {
                cout << ITP->postfix[i];
            }
            cout << "\n";
            break;

        case 4:
            exit(0);

        default:
            cout << "\nPlease Enter Correct Input!!\n";
            break;
        }

    label1:
        char userInput2;
        cout << "\nPress 'c' To Continue And 'e' To Exit\n";
        cin >> userInput2;
        if (tolower(userInput2) == 'c')
        {
            continue;
        }

        else if (tolower(userInput2) == 'e')
        {
            exit(0);
        }

        else
        {
            cout << "\nPlease Enter Correct Input!!\n";
            goto label1;
        }
    }
    delete ITP;
    return 0;
}

// Output

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Postfix
// 3. Press 3 To Print Postfix Expression
// 4. Press 4 To Exit
// >>>> 2

// You Have Not Taken Any Input!!

// Press 'c' To Continue And 'e' To Exit
// w

// Please Enter Correct Input!!

// Press 'c' To Continue And 'e' To Exit
// c

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Postfix
// 3. Press 3 To Print Postfix Expression
// 4. Press 4 To Exit
// >>>> 3

// Infix Expression is Not Converted Into Postfix Expression

// Press 'c' To Continue And 'e' To Exit
// w

// Please Enter Correct Input!!

// Press 'c' To Continue And 'e' To Exit
// c

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Postfix
// 3. Press 3 To Print Postfix Expression
// 4. Press 4 To Exit
// >>>> 1

// Enter a Infix Expression
// a+b*c

// Entered Infix Expression is : a+b*c

// Press 'c' To Continue And 'e' To Exit
// c

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Postfix
// 3. Press 3 To Print Postfix Expression
// 4. Press 4 To Exit
// >>>> 2

// Infix Expression is Successfully Converted Into Postfix Expression

// Press 'c' To Continue And 'e' To Exit
// c

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Postfix
// 3. Press 3 To Print Postfix Expression
// 4. Press 4 To Exit
// >>>> 3

// Postfix Expression : abc*+

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Postfix
// 3. Press 3 To Print Postfix Expression
// 4. Press 4 To Exit
// >>>> 1

// Enter a Infix Expression
// a+b-c*d/e

// Entered Infix Expression is : a+b-c*d/e

// Press 'c' To Continue And 'e' To Exit
// c

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Postfix
// 3. Press 3 To Print Postfix Expression
// 4. Press 4 To Exit
// >>>> 2

// Infix Expression is Successfully Converted Into Postfix Expression

// Press 'c' To Continue And 'e' To Exit
// c

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Postfix
// 3. Press 3 To Print Postfix Expression
// 4. Press 4 To Exit
// >>>> 3

// Postfix Expression : ab+cd*e/-

// Press 'c' To Continue And 'e' To Exit
// e

Comments

Post a Comment

Popular posts from this blog

Ticket Booking System

// Group C // Q 20. The Ticket Booking System of Cinemax Theatre Has To Be Implemented Using C++ Program. //       There Are 10 Rows And 7 Seats in Each Row. Doubly Circular Linked List Has To Be Maintained  //       To Keep Track of Free Seats At Rows. Assume Some Random Booking To Start With.  //       Use Array To Store Pointers(Head Pointers) To Each Row. On Demand //           A) The List of Available Seats is to be Displayed. //        ...
Read more

Student Database

/* OOP Group A - 1 Q2. Develop A Program In C++ To Create A Database Of Student's Information System Containing The Following Information : Name, Roll Number, Class, Division, Date Of Birth, Blood Group, Telephone No And  Other. Consruct The Database With Suitable Member Functions. Make Use Of Constructer, Default Constructer, Copy Constructer, Destructer, Static Member Functions, friend Class, this Pointer, inline Code, Dynamic Memory Allocation, Operators - new and delete As Well As Exception Handling. */ #include   <iostream> using   namespace   std ; class   Student { private:      st...
Read more

Generalised Linked List

  #include   <iostream> using   namespace   std ; class   Node { public:      bool  Tag;     Node *Next;      union     {          char  Data;         Node *SubList;     }; }; class   GeneralisedLinkedList  :  public   Node { public:     Node *Front, *Tail;      GeneralisedLinkedList ();  // Default Constructer      bool   empty ();      void   push_back ();      void   push_front ();      void   pop_back ();      void   pop_front ();      void   traverse ( Node   * ); }; template  < typename   T > T   c...
Read more