infix to postfix conversion using stack code example

Example 1: infix to postfix program in c++

/*https://github.com/Sudhanshu1304/Stack-Application*/

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



class Stack{


private:


    char A[5];
    int Size;

public:
    int top;
    Stack(){

        top=-1;
        Size=sizeof(A)/sizeof(char);

    }



    bool IsFull(){

        if(top==Size-1){
            return true;
        }
        else{
            return false;
        }
    }

    bool IsEmpty(){

        if(top==-1){
            return true;
        }
        else{
            return false;
        }
    }

    char peek(){

        return A[top];
    }

    void Push(char val){

        if (IsFull()==false){
            top++;
            A[top]=val;
        }
        else{
            cout<<"\nThe Stack is Full"<<endl;
        }
    }

    char Pop(){

        if(IsEmpty()==false){
            char temp=A[top];
            A[top]='0';
            top--;
            return temp;
        }
        else{
            return '-1';
        }

    }

    void Show_Stack(){


        for(int i=0;i<top+1;i++){
            cout<<A[i];
        }


    }

};


int Search(char A){


    string CHAR[]={"([","{)","]}","+-","*/","^$"};
    int Size=(sizeof(CHAR)/sizeof(string));

    for(int i=0;i<Size;i++){

        if(A==CHAR[i][0]){
                if(i+i>=6){
                    return i+i;
                }
                else{
                    return i+i+0;
                }

        }
        else if(CHAR[i][1]==A){
             if(i+i>=6){
                    return i+i;
                }
                else{
                    return i+i+1;
                }
        }
    }
    return -1;

}




void Display(char ch,string vari, Stack &s){

    int Size=s.top+1;


    cout<<"\n   "<<ch<<"           ";
    s.Show_Stack();
    for(int i=0;i<10-Size;i++){
        cout<<" ";
    }
    cout<<vari<<endl;

}


int main(){

    Stack STACK;
    char temp;
    string exp;//"A+B*C";
    cout<<"Enter Your Expression :";
    cin>>exp;

    string out="";
    cout<<"\n\nExpression   Stack   Postfix\n"<<endl;
    for(int i=0;i<exp.size();i++){

        temp=exp[i];

        int ab=Search(temp);

        if (ab!=-1){

            /* If We ENCOUNTER CLOSING BRACKETS*/
            if(ab<=5 && ab>=3){



                while(Search(STACK.peek())>2){
                    char val=STACK.Pop();
                        out=out+val;

                    Display(temp,out,STACK);
                }
                STACK.Pop();
                Display(temp,out,STACK);
                }
            /* Search Precedence*/
            else{
                if (Search(temp)>=0 && Search(temp)<=2){
                    STACK.Push(temp);
                    Display(temp,out,STACK);
                }

                /* If TOP < Temp */

                else if(Search(STACK.peek())<ab){

                        STACK.Push(temp);
                        Display(temp,out,STACK);
                }
                else{
                    /* if STACK= +,* and temp= + then we have to remove two times */


                    while(Search(STACK.peek())>=ab){

                        char val=STACK.Pop();
                            out=out+val;
                        Display(temp,out,STACK);
                    }
                    STACK.Push(temp);
                    Display(temp,out,STACK);
                }
            }
        }
        /* If an Alphabet */
        else{

            out=out+temp;
            Display(temp,out,STACK);

            }


    }
    while(STACK.IsEmpty()==false){

        char val=STACK.Pop();

            out=out+val;
        Display(temp,out,STACK);

    }
    cout<<"\n\nFINAL STRING : "<<out<<endl;


}

Example 2: Infix to postfix converstion using stack

/*
  Infix to postfix conversion in C++ 
  Input Postfix expression must be in a desired format. 
  Operands and operator, both must be single character.
  Only '+'  ,  '-'  , '*', '/' and '$' (for exponentiation)  operators are expected. 
*/
#include<iostream>
#include<stack>
#include<string>

using namespace std;

// Function to convert Infix expression to postfix 
string InfixToPostfix(string expression);

// Function to verify whether an operator has higher precedence over other
int HasHigherPrecedence(char operator1, char operator2);

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C);

// Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not. 
bool IsOperand(char C);

int main() 
{
	string expression; 
	cout<<"Enter Infix Expression \n";
	getline(cin,expression);
	string postfix = InfixToPostfix(expression);
	cout<<"Output = "<<postfix<<"\n";
}

// Function to evaluate Postfix expression and return output
string InfixToPostfix(string expression)
{
	// Declaring a Stack from Standard template library in C++. 
	stack<char> S;
	string postfix = ""; // Initialize postfix as empty string.
	for(int i = 0;i< expression.length();i++) {

		// Scanning each character from left. 
		// If character is a delimitter, move on. 
		if(expression[i] == ' ' || expression[i] == ',') continue; 

		// If character is operator, pop two elements from stack, perform operation and push the result back. 
		else if(IsOperator(expression[i])) 
		{
			while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i]))
			{
				postfix+= S.top();
				S.pop();
			}
			S.push(expression[i]);
		}
		// Else if character is an operand
		else if(IsOperand(expression[i]))
		{
			postfix +=expression[i];
		}

		else if (expression[i] == '(') 
		{
			S.push(expression[i]);
		}

		else if(expression[i] == ')') 
		{
			while(!S.empty() && S.top() !=  '(') {
				postfix += S.top();
				S.pop();
			}
			S.pop();
		}
	}

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

	return postfix;
}

// Function to verify whether a character is english letter or numeric digit. 
// We are assuming in this solution that operand will be a single character
bool IsOperand(char C) 
{
	if(C >= '0' && C <= '9') return true;
	if(C >= 'a' && C <= 'z') return true;
	if(C >= 'A' && C <= 'Z') return true;
	return false;
}

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C)
{
	if(C == '+' || C == '-' || C == '*' || C == '/' || C== '$')
		return true;

	return false;
}

// Function to verify whether an operator is right associative or not. 
int IsRightAssociative(char op)
{
	if(op == '$') return true;
	return false;
}

// Function to get weight of an operator. An operator with higher weight will have higher precedence. 
int GetOperatorWeight(char op)
{
	int weight = -1; 
	switch(op)
	{
	case '+':
	case '-':
		weight = 1;
	case '*':
	case '/':
		weight = 2;
	case '$':
		weight = 3;
	}
	return weight;
}

// Function to perform an operation and return output. 
int HasHigherPrecedence(char op1, char op2)
{
	int op1Weight = GetOperatorWeight(op1);
	int op2Weight = GetOperatorWeight(op2);

	// If operators have equal precedence, return true if they are left associative. 
	// return false, if right associative. 
	// if operator is left-associative, left one should be given priority. 
	if(op1Weight == op2Weight)
	{
		if(IsRightAssociative(op1)) return false;
		else return true;
	}
	return op1Weight > op2Weight ?  true: false;
}

Example 3: python postfix conversion

"""
Author : ITVoyagers (itvoyagers.in)

Date :31st October 2019

Description : Program to show use of stack in infix to postfix conversion using python.
"""
class infix_to_postfix:
    precedence={'^':5,'*':4,'/':4,'+':3,'-':3,'(':2,')':1}
    def __init__(self):
        self.items=[]
        self.size=-1
    def push(self,value):
        self.items.append(value)
        self.size+=1
    def pop(self):
        if self.isempty():
            return 0
        else:
            self.size-=1
            return self.items.pop()
    def isempty(self):
        if(self.size==-1):
            return True
        else:
            return False
    def seek(self):
        if self.isempty():
            return false
        else:
            return self.items[self.size]
    def isOperand(self,i):
        if i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
            return True
        else:
            return False
    def infixtopostfix (self,expr):
        postfix=""
        print('postfix expression after every iteration is:')
        for i in expr:
            if(len(expr)%2==0):
                print("Incorrect infix expr")
                return False
            elif(self.isOperand(i)):
                postfix +=i
            elif(i in '+-*/^'):
                while(len(self.items)and self.precedence[i]<=self.precedence[self.seek()]):
                    postfix+=self.pop()
                self.push(i)
            elif i is '(':
                self.push(i)
            elif i is ')':
                o=self.pop()
                while o!='(':
                    postfix +=o
                    o=self.pop()
            print(postfix)
                #end of for
        while len(self.items):
            if(self.seek()=='('):
                self.pop()
            else:
                postfix+=self.pop()
        return postfix
s=infix_to_postfix()
expr=input('enter the expression ')
result=s.infixtopostfix(expr)
if (result!=False):
    print("the postfix expr of :",expr,"is",result)