CONVERTING INFIX EXPRESSION INTO PREFIX EXPRESSION.

CONVERTING INFIX EXPRESSION INTO PREFIX EXPRESSION.

  12:27 PM    Unknown

---

#include <bits/stdc++.h>
#include <iostream>
#include <string.h>
#include <cctype>
#include <stdlib.h>
#include <conio.h>

using namespace std;

template <class Type>

class Infix2Prefix
{
private:
    Type *Stack;
    int Size, Top;

public:
    Infix2Prefix(int Siz)
    {
        Size = Siz;

        Stack = new Type[Size];
        strcpy(Stack, "\0");

        Top = -1;
    }

    void Push(Type Ch)
    {
        if( IsFull() )
        {
            cout << "\nSTACK OVERFLOWED!!!!!!!!!\n" << endl;
            exit(1);
        }

        Stack[++Top] = Ch;
    }

    Type Pop()
    {
        if( IsEmpty() )
        {
            cout << "\nSTACK UNDERFLOWED!!!!!!\n" << endl;
            exit(1);
        }

        return Stack[Top--];
    }

    Type TOP()
    {
        return Stack[Top];
    }

    bool IsOperator(char Ch)
    {
        return ( !isalpha(Ch) && !isdigit(Ch) );
    }

    int Priority(char Ch)
    {
        if(Ch == '^')
            return 3;

       else if( Ch == '*' || Ch == '/' )
            return 2;

        else if(Ch == '+' || Ch == '-')
            return  1;

            return 0;
    }

    string Convert(string Infix)
    {
        char Ch;
        string Prefix;

        reverse( Infix.begin(), Infix.end() );

        for(int I =0; I <Infix.length(); I++)
        {
            if( Infix[I] == '(' )
                Infix[I++] = ')';

            else if( Infix[I] == ')' )
                Infix[I++] = '(';
        }

        for(int I =0; I <Infix.length(); I++)
        {
            Ch = Infix[I];

            if( isalpha(Ch) || isdigit(Ch) )
                Prefix += Ch;

            else if( Ch == '(' )
                    Push(Ch);

            else if( Ch == ')' )
            {
                for(; TOP() !='(';)
                {
                    Prefix += Pop();
                }

                Pop();
            }

            else
            {
                if(IsOperator( TOP() ) )
                   {
                       while( Priority(Ch) <= Priority( TOP() ) )
                             {
                                 Prefix += Pop();
                             }

                             Push(Ch);
                    }
            }
}

Prefix += Pop();

reverse(Prefix.begin(), Prefix.end());

        return Prefix;
    }

    inline bool IsFull()
    {
        return (Top == Size - 1);
    }

    inline bool IsEmpty()
    {
        return (Top == -1);
    }

    ~Infix2Prefix()
    {
        cout << "\n\n\n****************PROGRAM ENDED*******************\n\n\n" << endl;
    }
};

int main()
{
    Infix2Prefix<char> Obj(100);
    string Expression;

    cout << "Enter any INFIX Expression: ";
    cin >> Expression;

    cout << "\nExpression After Converting To PRETFIX is: " << Obj.Convert(Expression) << endl;

    getch();
    return 0;
}