Infix To Prefix

 #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';
}

string reverse(string); // Function Declaration

class InfixToPrefix
{
    // Stack To Store Characters of Infix Expressions
    Stack *stk;
    string postfix;

public:
    string infix;
    string reverseInfix;
    string prefix;
    InfixToPrefix();  // Default Constructer Declaration
    ~InfixToPrefix(); // 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 infixToPrefix();
};

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;
}

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

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

string reverse(string str)
{
    string reverseStr;
    for (int i = str.length() - 1; i >= 0; i--)
    {
        switch (str[i])
        {
        case '(':str[i] = ')';break;

        case '[':str[i] = ']';break;

        case '{':str[i] = '}';break;

        case ')':str[i] = '(';break;

        case ']':str[i] = '[';break;

        case '}':str[i] = '{';break;
        }
        reverseStr.append(1, str[i]);
    }
    return reverseStr;
}

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

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

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

    for (int i = 0; i < infix.length(); 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 InfixToPrefix::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 InfixToPrefix::precedence(char op)
{
    if (op == '^')
    {
        return 3;
    }

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

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

    else
    {
        return 0;
    }
}

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

    for (int i = 0; i < reverseInfix.length(); i++)
    {
        if (reverseInfix[i] == '(' || reverseInfix[i] == '[' || reverseInfix[i] == '{')
        {
            stk->push(reverseInfix[i]);
        }

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

            else
            {
                char top = stk->top();
                while (precedence(top) >= precedence(reverseInfix[i]))
                {
                    postfix.push_back(stk->pop());
                    top = stk->top();
                }

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

        else if (reverseInfix[i] == '}' || reverseInfix[i] == ']' || reverseInfix[i] == ')')
        {
            char top = stk->top();
            while (top != '(' && top != '[' && top != '{')
            {
                postfix.push_back(stk->pop());
                top = stk->top();
            }
            stk->pop();
        }

        else
        {
            postfix.push_back(reverseInfix[i]);
        }
    }

    while (!stk->empty())
    {
        char pop = stk->pop();
        postfix.push_back(pop);
    }
    prefix = reverse(postfix);
    cout << "\nInfix Expression is Successfully Converted Into Prefix Expression\n";
}

int main()
{
    bool isInput = false;
    bool isInfixToPrefix = false;
    InfixToPrefix *ITP = new (nothrow) InfixToPrefix();
    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 Prefix\n3. Press 3 To Print Prefix Expression\n4. Press 4 To Exit\n>>>> ");
        cout << content;
        cin >> userInput;
        userInput = checkInput(userInput, content);

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

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

            ITP->infixToPrefix();

            if (!(ITP->prefix.length() == 0))
            {
                isInfixToPrefix = true;
            }
            break;

        case 3:
            if (!isInfixToPrefix)
            {
                cout << "\nInfix Expression is Not Converted Into Prefix Expression\n";
                break;
            }
            cout << "\nPostfix Expression : ";
            cout << ITP->prefix << "\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 Prefix
// 3. Press 3 To Print Prefix Expression
// 4. Press 4 To Exit
// >>>> 2

// You Have Not Taken Any Input!!

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

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

// Infix Expression is Not Converted Into Prefix Expression

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

// 1. Press 1 To Take Input
// 2. Press 2 To Convert From Infix To Prefix
// 3. Press 3 To Print Prefix 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 Prefix
// 3. Press 3 To Print Prefix Expression
// 4. Press 4 To Exit
// >>>> 2

// Infix Expression is Successfully Converted Into Prefix Expression

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

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

// Postfix Expression : +a-b*c/de

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

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

// Enter a Infix Expression
// (a+b)*{c-d}

// Entered Infix Expression is : (a+b)*{c-d}

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

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

// Infix Expression is Successfully Converted Into Prefix Expression

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

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

// Postfix Expression : *+ab-cd

// 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