Infix To PostFix and Postfix Evaluation


// Infix to Postfix Conversion 
// Name - Tirthraj Mahajan

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



// Check whether the character is an Operand
bool isOperand(char ch){
    if (ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&ch!='('&&ch!=')'&&ch!='^') {
        return true;
    }
    else{
        return false;
    }
}

string infixToPostfix(string infix){

    //Create a map of operators with their order of precedence
    map<char,int> precedence = {
        {'+',1},
        {'-',1},
        {'*',2},
        {'/',2},
        {'^',3}
    };

    //Create an empty Postfix string
    string postfix = "";

    //Create an empty stack to maintain the operators
    stack<char> st;

    //Create a flag variable to reset the precedence stack if there is a parenthesis which is set to false initially

    bool flag = false;

    for(int i=0; i<infix.length(); i++){
        if(isOperand(infix[i])){
            postfix += infix[i];
        }
        else{
            if(infix[i]=='('){
                //Set the flag to true to reset the precedence

                flag = true;
                st.push('(');
            }
            else if(infix[i]==')'){
                flag = false;

                //while the top of stack if not (, pop the elements and append them to postfix
                // But do check for edge cases like stack underflow incase of invalid parenthesis

                while(st.top()!='('&&!st.empty()){
                    postfix += st.top();
                    st.pop();
                }
                if(!st.empty()) st.pop(); //Remove the '(' from stack

            }

            // If the stack is empty, i.e if it is the first operator, then insert the operator as it is
            // Set the flag to false just in case it became true in earlier call

            else if(st.empty()){
                flag = false;
                st.push(infix[i]);
            }

            // If the previous entry index[i-1] was an open parenthesis or the precedence of the current operator is higher than the operator on top then insert the operator as it is in the stack and set the flag to false

            else if(flag==true || precedence[infix[i]]>precedence[st.top()]){
                flag = false;
                st.push(infix[i]);
            }

            // if the flag is false and the precedence if current element is less then that of top of stack then pop all elements from stack and append to the postfix string and then push the current element to the stack.

            else if(precedence[infix[i]]<precedence[st.top()]){
                while(!st.empty()){
                    postfix += st.top();
                    st.pop();
                }
                st.push(infix[i]);
            }

            // If the current element has the same precedence as that of the top operator of the stack then pop the stack and append it in the postfix string. Then push the current element onto the stack

            else if(precedence[infix[i]]==precedence[st.top()]){
                postfix+=st.top();
                st.pop();
                st.push(infix[i]);
            }

        }
    }

    //At the end of the string, remaining operands will insert into the postfix

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

    return postfix;
}


int main() {
    string infix;
    cout<<"Enter the infix expression:"<<endl;
    cin>>infix;
    string postfix = infixToPostfix(infix);
    cout<<"Postfix Expression: "<<postfix<<endl;

    return 0;
}


// Infix to Postfix 
// Name: Tirthraj Mahajan 


function isOperand(val){
    if(val=='('||val==')'||val=='+'||val=='-'||val=='/'||val=='*'||val=='^'||val=='–'){
        return false;
    }
    return true;
}

function infixToPostfix(expression){
    let expressionArr = expression.split(" ");
    console.log("Expression Array: ",expressionArr);
    let stack = [];
    
    let precedence = new Map([
        ["(",0],
        ["+",1],
        ["-",1],
        ["–",1],
        ["*",2],
        ["/",2],
        ["^",3]
    ]);
    let postfix = "";
    for(let i=0; i<expressionArr.length; i++){
        if(isOperand(expressionArr[i])){
            postfix+=expressionArr[i];
            postfix+=" ";
        }
        else{
            if(stack.length==0){
                stack.push(expressionArr[i]);
            }
            else if(expressionArr[i]=="("){
                stack.push(expressionArr[i]);
            }
            else if(expressionArr[i]==")"){
                while((stack.length!=0)&&(stack[stack.length-1]!="(")){
                    postfix += stack.pop();
                    postfix+=" ";
                }
                stack.pop();
            }
            else if((precedence.get(expressionArr[i])>precedence.get(stack[stack.length-1]))||(stack[stack.length-1] == "(")){
                stack.push(expressionArr[i]);
            }
            else{
                while (
                    stack.length != 0 &&
                    precedence.get(stack[stack.length - 1]) >= precedence.get(expressionArr[i])
                ) {
                    postfix += stack.pop();
                    postfix+=" ";
                }
                stack.push(expressionArr[i]);
            }
        }

    }

    while(stack.length!=0){
        postfix += stack.pop();
        postfix+=" ";
    }
    return postfix;

}

let expression = "( ( A + B ) – C * ( D / E ) ) + F";
let postfix = infixToPostfix(expression);
console.log("Postfix: ",postfix);

Infix to Postfix Converter