Answers for "infix to postfix c++"

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<<"nnExpression   Stack   Postfixn"<<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<<"nnFINAL STRING : "<<out<<endl;


}

infix to postfix conversion

Best Solution
-------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;

int prec(char c) {
    if(c == '^') {
        return 3;
    }
    else if(c == '*' || c == '/') {
        return 2;
    }
    else if(c == '+' || c =='-') {
        return 1;
    }
    else {
        return -1;
    }
}

string infixToPostfix(string s) {
    stack<char> st;
    string res;

    for (int i = 0; i < s.length(); i++)
    {
        if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
            res += s[i];
        }
        else if(s[i] == '(') {
            st.push(s[i]);
        }
        else if(s[i] == ')') {
            while (!st.empty() && st.top() != '(')
            {
                res += st.top();
                st.pop();
            }
            if(!st.empty()) {
                st.pop(); // Popping '(' here
            }
        }
        else {
            while (!st.empty() && prec(st.top()) >= prec(s[i]))
            {
                res += st.top();
                st.pop();
            }
            st.push(s[i]);
        }
    }
    
    while (!st.empty())
    {
       res += st.top();
       st.pop();
    }
    
    return res;
}

int main() {
    string exp = "a+b*(c^d-e)^(f+g*h)-i";
    cout<<infixToPostfix(exp);
    return 0;
}

infix to postfix conversion c program

/* This program converts infix expression to postfix expression.
 * This program assume that there are Five operators: (*, /, +, -,^) 
	in infix expression and operands can be of single-digit only.
 * This program will not work for fractional numbers.
 * Further this program does not check whether infix expression is 
 valid or not in terms of number of operators and operands.*/

#include<stdio.h>
#include<stdlib.h>      /* for exit() */
#include<ctype.h>     /* for isdigit(char ) */
#include<string.h>

#define SIZE 100


/* declared here as global variable because stack[]
* is used by more than one fucntions */
char stack[SIZE];
int top = -1;

/* define push operation */

void push(char item)
{
	if(top >= SIZE-1)
	{
		printf("nStack Overflow.");
	}
	else
	{
		top = top+1;
		stack[top] = item;
	}
}

/* define pop operation */
char pop()
{
	char item ;

	if(top <0)
	{
		printf("stack under flow: invalid infix expression");
		getchar();
		/* underflow may occur for invalid expression */
		/* where ( and ) are not matched */
		exit(1);
	}
	else
	{
		item = stack[top];
		top = top-1;
		return(item);
	}
}

/* define function that is used to determine whether any symbol is operator or not
(that is symbol is operand)
* this fucntion returns 1 if symbol is opreator else return 0 */

int is_operator(char symbol)
{
	if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol =='-')
	{
		return 1;
	}
	else
	{
	return 0;
	}
}

/* define fucntion that is used to assign precendence to operator.
* Here ^ denotes exponent operator.
* In this fucntion we assume that higher integer value
* means higher precendence */

int precedence(char symbol)
{
	if(symbol == '^')/* exponent operator, highest precedence*/
	{
		return(3);
	}
	else if(symbol == '*' || symbol == '/')
	{
		return(2);
	}
	else if(symbol == '+' || symbol == '-')          /* lowest precedence */
	{
		return(1);
	}
	else
	{
		return(0);
	}
}

void InfixToPostfix(char infix_exp[], char postfix_exp[])
{ 
	int i, j;
	char item;
	char x;

	push('(');                               /* push '(' onto stack */
	strcat(infix_exp,")");                  /* add ')' to infix expression */

	i=0;
	j=0;
	item=infix_exp[i];         /* initialize before loop*/

	while(item != '')        /* run loop till end of infix expression */
	{
		if(item == '(')
		{
			push(item);
		}
		else if( isdigit(item) || isalpha(item))
		{
			postfix_exp[j] = item;              /* add operand symbol to postfix expr */
			j++;
		}
		else if(is_operator(item) == 1)        /* means symbol is operator */
		{
			x=pop();
			while(is_operator(x) == 1 && precedence(x)>= precedence(item))
			{
				postfix_exp[j] = x;                  /* so pop all higher precendence operator and */
				j++;
				x = pop();                       /* add them to postfix expresion */
			}
			push(x);
			/* because just above while loop will terminate we have
			oppped one extra item
			for which condition fails and loop terminates, so that one*/

			push(item);                 /* push current oprerator symbol onto stack */
		}
		else if(item == ')')         /* if current symbol is ')' then */
		{
			x = pop();                   /* pop and keep popping until */
			while(x != '(')                /* '(' encounterd */
			{
				postfix_exp[j] = x;
				j++;
				x = pop();
			}
		}
		else
		{ /* if current symbol is neither operand not '(' nor ')' and nor
			operator */
			printf("nInvalid infix Expression.n");        /* the it is illegeal  symbol */
			getchar();
			exit(1);
		}
		i++;


		item = infix_exp[i]; /* go to next symbol of infix expression */
	} /* while loop ends here */
	if(top>0)
	{
		printf("nInvalid infix Expression.n");        /* the it is illegeal  symbol */
		getchar();
		exit(1);
	}
	if(top>0)
	{
		printf("nInvalid infix Expression.n");        /* the it is illegeal  symbol */
		getchar();
		exit(1);
	}


	postfix_exp[j] = ''; /* add sentinel else puts() fucntion */
	/* will print entire postfix[] array upto SIZE */

}

/* main function begins */
int main()
{
	char infix[SIZE], postfix[SIZE];         /* declare infix string and postfix string */

	/* why we asked the user to enter infix expression
	* in parentheses ( )
	* What changes are required in porgram to
	* get rid of this restriction since it is not
	* in algorithm
	* */
	printf("ASSUMPTION: The infix expression contains single letter variables and single digit constants only.n");
	printf("nEnter Infix expression : ");
	gets(infix);

	InfixToPostfix(infix,postfix);                   /* call to convert */
	printf("Postfix Expression: ");
	puts(postfix);                     /* print postfix expression */

	return 0;
}

infix to postfix conversion c++

//Easiet way to solve infix to postfix expression
bool isOperator(char c)
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
	{
		return true;
	}
	else
	{
		return false;
	}
}

int precedence(char c) 
{ 
    if(c == '^') 
    return 3; 
    else if(c == '*' || c == '/') 
    return 2; 
    else if(c == '+' || c == '-') 
    return 1; 
    else
    return -1; 
} 

string InfixToPostfix(stack<char> s, string infix)
{
	string postfix;
	for(int i=0;i<infix.length();i++)
	{
		if((infix[i] >= 'a' && infix[i] <= 'z')
		||(infix[i] >= 'A' && infix[i] <= 'Z'))
		{
			postfix+=infix[i];
		}
		else if(infix[i] == '(')
		{
			s.push(infix[i]);
		}
		else if(infix[i] == ')')
		{
			while((s.top()!='(') && (!s.empty()))
			{
				char temp=s.top();
				postfix+=temp;
				s.pop();
			}
			if(s.top()=='(')
			{
				s.pop();
			}
		}
		else if(isOperator(infix[i]))
		{
			if(s.empty())
			{
				s.push(infix[i]);
			}
			else
			{
				if(precedence(infix[i])>precedence(s.top()))
				{
					s.push(infix[i]);
				}	
				else if((precedence(infix[i])==precedence(s.top()))&&(infix[i]=='^'))
				{
					s.push(infix[i]);
				}
				else
				{
					while((!s.empty())&&( precedence(infix[i])<=precedence(s.top())))
					{
						postfix+=s.top();
						s.pop();
					}
					s.push(infix[i]);
				}
			}
		}
	}
	while(!s.empty())
	{
		postfix+=s.top();
		s.pop();
	}
	
	return postfix;
}

int main() 
{  

  	string infix_exp, postfix_exp;
  	cout<<"Enter a Infix Expression :"<<endl;
  	cin>>infix_exp;
  	stack <char> stack;
	cout<<"INFIX EXPRESSION: "<<infix_exp<<endl;
  	postfix_exp = InfixToPostfix(stack, infix_exp);
  	cout<<endl<<"POSTFIX EXPRESSION: "<<postfix_exp;
	  
	return 0;
}