InfixToPrefix.cpp

#include <iostream>
using namespace std;
const int Size = 50;

struct Stack
{
    string arr[Size];
    int top = -1;
};

void push(Stack &stack, string value)
{
    if (stack.top == Size - 1)
    {
        cout << "Stack is full" << value << endl;
        return;
    }
    stack.arr[++stack.top] = value;
}

string pop(Stack &stack)
{
    if (stack.top == -1)
    {
        return " ";
    }
    return stack.arr[stack.top--];
}
string peek(Stack &stack)
{
    if (stack.top == -1)
    {
        return " ";
    }
    return stack.arr[stack.top];
}

void display(Stack &stack)
{
    if (stack.top == -1)
    {
        cout << "Stack is empty." << endl;
        return;
    }
    cout << "Stack elements From top to bottom:";
    for (int i = stack.top; i >=0 ; i--)
    {
        cout << stack.arr[i] << " ";
    }
    cout << endl;
}
/*Order of Evaluation:
Parentheses: Operations within parentheses are evaluated first. 
Arithmetic Operators: Multiplication, Division, and Modulus are evaluated before Addition and Subtraction. 
Comparison Operators: Operators like <, >, <=, >=, ==, and != are evaluated next. 
Logical Operators: Logical AND (&&), Logical OR (||), and Logical NOT (!) are evaluated last. */
int precedence(string op){
    if (op == "*" || op == "%"|| op == "/")
    {
        return 4;
    }
    else if (op == "+" || op == "-")
    {
        return 3;
    }
    else if (op == "<" || op == ">" || op == "<=" || op == ">=" || op == "==" || op =="!=")
    {
        return 2;
    }
    else if (op == "&&" || op == "||" || op == "!")
    {
        return 1;
    }
    else{
        return 0;
    }
}
void infixToPostfix(Stack &operatorStack, string &postfixExp, string exp)
{
    string c;
    string character;
    for (size_t i = 0; i < exp.length(); i++)
    {
        c = exp[i];
        if ((exp[i] >= 'a' && exp[i] <= 'z') || (exp[i] >= '0' && exp[i]<= '9'))
        {
            //push the operands in postfix stack
            postfixExp  += c;
        }
        else
        {
            if (exp[i] == '(' || peek(operatorStack) == "(")
            {
                //directly push "(" or operator after the opening bracket
                push(operatorStack,c);
                display(operatorStack);
            }
            else if (exp[i] == ')')
            {
                //when closing bracket encounters,Pop remaining operators till the opening bracket
                while (operatorStack.top > -1 && peek(operatorStack) != "(") {
                    character = pop(operatorStack);
                    postfixExp += character;
                }
                //remove the opening bracket afterwards
                pop(operatorStack);
            }
            else{
                //if the operator is "<=",">=","==","!=","&&","||"
                if (((exp[i] =='!'|| exp[i] =='<' || exp[i] =='>') && exp[i+1] == '=') || ((exp[i] =='&' && exp[i+1] == '&') || exp[i] == '|' && exp[i+1] == '|'))
                {
                    c+= exp[i+1];
                    //skip the other character b/c it is part of the operator
                    i++;
                }
                //when precendence of the infix exp oerator <= top of operatorStack
                while (operatorStack.top > -1 && precedence(c) <= precedence(peek(operatorStack)))
                {
                    character = pop(operatorStack);
                    postfixExp += character;
                }
                //when precendence of the infix exp oerator > top of operatorStack || operatorStack is empty
                push(operatorStack, c);
                display(operatorStack);
            }
        }
    }
    // Pop remaining operators when infix expression ends
    while (operatorStack.top > -1) {
        character = pop(operatorStack);
        postfixExp += character;
    }
}
string reverseExp(string exp){
    string revExp;
    for (int i = exp.length()-1; i >=0 ; i--)
    {
        if (exp[i] == '(')
        {
            revExp += ')';
        }
        else if (exp[i] == ')')
        {
            revExp += '(';
        }
        else
        {
            revExp += exp[i];
        }
    }
    return revExp;
}
string reversePostfixExp(string postfixExp){
    string prefixExp;
    for (int i = postfixExp.length()-1; i >=0 ; i--)
    {
        prefixExp += postfixExp[i];
    }
    return prefixExp;
}
int main(int argc, char const *argv[])
{
    Stack operatorStack;
    string postfixExp;
    string exp;
    cout << "Enter the infix expression: ";
    getline(cin, exp);

    exp = reverseExp(exp);
    cout<<exp;
    infixToPostfix(operatorStack,postfixExp,exp);
    cout<<"PreFix Expression: ";
    cout<<reversePostfixExp(postfixExp)<<endl;

    return 0;
}