Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Created December 9, 2013 05:34
Show Gist options
  • Save mycodeschool/7867739 to your computer and use it in GitHub Desktop.
Save mycodeschool/7867739 to your computer and use it in GitHub Desktop.
Infix to Postfix conversion in C++ using stack. We are assuming that both operators and operands in input will be single character.
/*
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;
}
@OmarBeshary
Copy link

OmarBeshary commented Feb 15, 2017

sir , this test case gives me a wrong answer

  • A+B*C+D
    it should be :
  • ABC*+D+
    and the code gives me :
  • ABC*+D+
    you should break after every case , after getting operator's weight .

@varun-995
Copy link

Comment on line 46 is wrong. Please modify it.

@varun-995
Copy link

@rakesh-bs
our code consists of only basic mathematical operations like +, -, *, / which are left associative.

Consider this segment of code

if(op1Weight == op2Weight) {
	if(IsRightAssociative(op1)) {
                return false;
        } else {
                return true;
        }
}

Now assume a situation where + is already present in stack and while parsing we encounter other +. Now a call to HasHigherPrecedence(+, +) is made. IsRightAssociative(+) checks whether the operator is $ and it is not and hence false is returned and hence in above code segment else condition runs and it returns true i.e. operator in stack is of higher priority.

In short we can say that it is a workaround because we ourselves know that our expression will never contain a $ as an operator and all the operators(+, -, *, /) that are present in our expression will be left associative so every time when top operator in stack matches to operator in expression that we are currently parsing we already know that IsRightAssociative(op1) will always return false and hence operator in stack will be given higher priority.

@Amrismail132
Copy link

Amrismail132 commented May 17, 2017

how to make this on code
handle the associativity of the power operator '^', as it associates to the right, not to the left. Consider the following example:

2 ^ 3 ^ 2 should output:
2 3 2 ^ ^
512 = (2 ^ (3 ^ 2)),
not
2 3 ^ 2 ^
64 = ((2 ^ 3) ^ 2).

You also need to use a stack of your own implementation, not the C++/STL stack.
Sorry if I wasn't clear

@Amrismail132
Copy link

how to make this code
Infix to Postfix Conversion
Initialize a stack of characters to hold the operators (^, *, /, +, -)
• Parse the infix string left to right:
If an operand is read:
• Then output it into the postfix expression expression
Else if ‘(‘ is read
• Then push it into the stack
• Else if E ‘)’ is read:
• Then pop and output into the postfix expression until matching ‘(‘ is popped from the stack
• Else if an operator Xis read:
• If the stack is empty or character Y(top of the stack) = ‘(‘ or Yis an operator of lower precedence than X, then push X
• While Y is an operator of higher or equal precedence than X, pop and output Y
• Then push X
• When we reach the end of input, pop and output until stack is empty

@mohammedshawky00
Copy link

// 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 an operator is right associative or not.
int IsRightAssociative(char op)
{
if(op == '$') return true;
return false;
}

please , explain 2 codes above .. they are ambiguous and thanks in advance

@zizoo4949
Copy link

it is really amazing program believe me the a lot of amazing technics thank you so much i have written so much about the same topic form different books videos and notes it is the best the best

@zizoo4949
Copy link

this is program for c
#include<stdio.h>
#include<conio.h>
#define max 50
char s[max];
int top;
void ev();//evaluate the expressions
int lfas(char);//left associated
int hp(char,char);//high precdent
int we(char);//find the weight of the opreators
int em();//isempty
int fu();//isfull
void push(char a);//elememnt push to stack
char pop();//element pop from stack
int od(char);//is opreand
int op(char);//is oprator
int pa(char);//is open parenthesis
char in[50],po[50];
int main()
{
top=-1;
printf("enter the infix expression \n");
scanf("%s",in);
ev();
printf("the infix expression\n%s\n",in);
printf("the postfix expression\n%s\n",po);
return 0;
}
void ev()
{
int i,j;
i=j=0;
char temp;
for(i=0;in[i]!='\0';i++)
{
temp=in[i];
if(od(temp))
{
po[j]=temp;
j++;
}
else if(op(in[i]))
{
while((!em())&&(!pa(temp))&&(hp(s[top],temp)))
{
temp=pop();
po[j]=temp;
j++;
}
push(in[i]);

                }
                else if(pa(temp))
                push(in[i]);
                else if(temp==')')
                {
                temp=pop();	
               	while(!pa(temp))
               	{
 po[j]=temp;
 j++; 
 temp=pop();                 	
                   	
                 }
                pop();
                	
                }
	
}
while(!em())
{
temp=pop();
po[j]=temp;
j++;	
	
}

}
int lfas(char a)
{
if(a == '$'|| a== '^')
return 0;
else
return 1;
}
int hp(char a,char b)
{
int w1,w2;
w1=we(a);
w2=we(b);
if(w1==w2)
{
if(lfas(a))
return 1;
else
return 0;
}
return ( w1>w2? 1:0);

}
int we(char a)
{
int p;
switch(a)
{
case'-':
case'+':p=1;
break;
case'*':
case'/':
case'%':p=2;
break;
case'^':
case'$':p=3;
break;
}
return p;
}
int em()
{
if(top==-1)
return 1;
else
return 0;
}
int fu()
{
if(top==max-1)
return 1;
else
return 0;
}
void push(char a)
{
if(!fu())
{
top++;
s[top]=a;
}
else
printf("an error \n");
}
char pop()
{
char t;
if(!em())
{
t=s[top];
top--;
return(t);
}
else
return '@';

}
int od(char a)
{
if(a>='a'&& a<='z'||a>='A'&& a<='Z'||a>='0'&&a<='9')
return 1;
else
return 0;
}
int op(char a)
{
if(a=='+'||a=='-'||a=='*'||a=='/'||a=='%'||a=='^'||a=='$')
return 1;
else
return 0;
}
int pa(char a)
{
if(a=='(')
return 1;
else
return 0;
}

@iruvingu
Copy link

iruvingu commented Mar 6, 2018

@amna013
Copy link

amna013 commented Mar 9, 2018

#include"stack.h"
#include
#include
using namespace std;
bool is_operator(char o);
bool chk_prec(char c1, char c2);
string infix_to_postfix(string exp);
void main()
{
string exp,c;
cout << "Please enter expression" << endl;
cin >> exp;
c=infix_to_postfix(exp);
cout << "Postfix expression is " << c << endl;
system("pause");
}
bool is_operator(char o)
{
if (o == '')
return true;
else if (o == '+')
return true;
else if (o == '-')
return true;
else if (o == '/')
return true;
else if (o == '^')
return true;
else
return false;
}
bool chk_prec(char c1, char c2)
{
if ((c1 == '
') && (c2 == ''))
return true;
else if ((c1 == '
') && (c2 == '^'))
return false;
else if ((c1 == '') && (c2 == '+'))
return true;
else if ((c1 == '
') && (c2 == '-'))
return true;
else if ((c1 == '') && (c2 == '/'))
return true;
else if ((c1 == '^') && (c2 == '^'))
return true;
else if ((c1 == '^') && (c2 == '/'))
return true;
else if ((c1 == '^') && (c2 == '
'))
return true;
else if ((c1 == '^') && (c2 == '+'))
return true;
else if ((c1 == '^') && (c2 == '-'))
return true;
else if ((c1 == '/') && (c2 == '/'))
return true;
else if ((c1 == '/') && (c2 == '^'))
return false;
else if ((c1 == '/') && (c2 == ''))
return true;
else if ((c1 == '/') && (c2 == '+'))
return true;
else if ((c1 == '/') && (c2 == '-'))
return true;
else if ((c1 == '+') && (c2 == '+'))
return true;
else if ((c1 == '+') && (c2 == '^'))
return true;
else if ((c1 == '+') && (c2 == '
'))
return false;
else if ((c1 == '+') && (c2 == '/'))
return false;
else if ((c1 == '+') && (c2 == '-'))
return true;
else if ((c1 == '-') && (c2 == '^'))
return false;
else if ((c1 == '-') && (c2 == '/'))
return false;
else if ((c1 == '-') && (c2 == '*'))
return false;
else if ((c1 == '-') && (c2 == '+'))
return true;
else if ((c1 == '-') && (c2 == '-'))
return true;
else
return false;
}
template
string infix_to_postfix(string exp)
{
stack s1;
char t;
string postfix = " ";
for (int i = 0; i <= exp.size(); i++)
{
t = exp[i];
if (is_operator(t))
postfix += t;
else
{
while (!s1.empty() && chk_prec(s.top(), t))
{
postfix += s1.top;
s1.pop();
}
s1.push(t);
}

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

}

What is the mistake in this code?

@amna013
Copy link

amna013 commented Mar 9, 2018

#include"stack.h"
#include
#include
using namespace std;
bool is_operator(char o);
bool chk_prec(char c1, char c2);
string infix_to_postfix(string exp);
void main()
{
string exp,c;
cout << "Please enter expression" << endl;
cin >> exp;
c=infix_to_postfix(exp);
cout << "Postfix expression is " << c << endl;
system("pause");
}
bool is_operator(char o)
{
if (o == '')
return true;
else if (o == '+')
return true;
else if (o == '-')
return true;
else if (o == '/')
return true;
else if (o == '^')
return true;
else
return false;
}
bool chk_prec(char c1, char c2)
{
if ((c1 == '
') && (c2 == ''))
return true;
else if ((c1 == '
') && (c2 == '^'))
return false;
else if ((c1 == '') && (c2 == '+'))
return true;
else if ((c1 == '
') && (c2 == '-'))
return true;
else if ((c1 == '') && (c2 == '/'))
return true;
else if ((c1 == '^') && (c2 == '^'))
return true;
else if ((c1 == '^') && (c2 == '/'))
return true;
else if ((c1 == '^') && (c2 == '
'))
return true;
else if ((c1 == '^') && (c2 == '+'))
return true;
else if ((c1 == '^') && (c2 == '-'))
return true;
else if ((c1 == '/') && (c2 == '/'))
return true;
else if ((c1 == '/') && (c2 == '^'))
return false;
else if ((c1 == '/') && (c2 == ''))
return true;
else if ((c1 == '/') && (c2 == '+'))
return true;
else if ((c1 == '/') && (c2 == '-'))
return true;
else if ((c1 == '+') && (c2 == '+'))
return true;
else if ((c1 == '+') && (c2 == '^'))
return true;
else if ((c1 == '+') && (c2 == '
'))
return false;
else if ((c1 == '+') && (c2 == '/'))
return false;
else if ((c1 == '+') && (c2 == '-'))
return true;
else if ((c1 == '-') && (c2 == '^'))
return false;
else if ((c1 == '-') && (c2 == '/'))
return false;
else if ((c1 == '-') && (c2 == '*'))
return false;
else if ((c1 == '-') && (c2 == '+'))
return true;
else if ((c1 == '-') && (c2 == '-'))
return true;
else
return false;
}
template
string infix_to_postfix(string exp)
{
stack s1;
char t;
string postfix = " ";
for (int i = 0; i <= exp.size(); i++)
{
t = exp[i];
if (is_operator(t))
postfix += t;
else
{
while (!s1.empty() && chk_prec(s.top(), t))
{
postfix += s1.top;
s1.pop();
}
s1.push(t);
}

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

}

wht is the mistake in this code?

@marksharkpark
Copy link

Can someone explain what line 143 is and does?

@19mayank19
Copy link

please provide code in C language for the same

@ms1797
Copy link

ms1797 commented Oct 1, 2018

The code given in the link is partially correct. I have made the required changes.
LINK to the code is =>>
https://gist.github.com/ms1797/982b11b310a521367c5fd83de81d2851

@MODAK27
Copy link

MODAK27 commented May 12, 2019

you forgot to add break statement in your code in switch case. that thing just ruined my 1 hour to find the errors. :-(

@SeongmanPark
Copy link

your code is good zz

@SeongmanPark
Copy link

MODAK27 kidding man

Copy link

ghost commented Mar 16, 2020

In function int GetOperatorWeight(char op), you forgot to put break statements in Switch Case. So, it is always returning weight 3.

yes!!i think when $ comes into picture it will fail...

Copy link

ghost commented Mar 16, 2020

In function int GetOperatorWeight(char op), you forgot to put break statements in Switch Case. So, it is always returning weight 3.

but I checked for - and *,its is working..something is fishy

@arsharaj
Copy link

Here is my implementation in C++ itself.

// Include all the required files
#include<iostream>
#include<stack>
#include<string>

// Define the namespace for standard library
using namespace std;

// Check weather the given character is an opening bracket or not
// Return true if it is an opening bracket else return false.
int IsOpeningBracket(char openbracket){
  return (openbracket=='('||openbracket=='{'||openbracket=='[');
}

// Check weather the given character is a closing bracket or not
// Return true if it is an closing bracket else return false.
int IsClosingBracket(char closedbracket){
  return (closedbracket==')'||closedbracket=='}'||closedbracket==']');
}

// Check weather the given character is a number or not
// Return true if it is a number else return false.
int IsNumber(char num){
  // Subtract the ascii value of 0 to get the real value of the 
  // numbers
  return ((int)num-'0'>=0 && (int)num-'0'<=9);
}

// Check weather the character is Operator or not.
// Return true if it is an operator else return false.
int IsOperator(char op){
  // All the supported operators
  return (op=='+'||op=='-'||op=='*'||op=='/'||op=='^'); 
}

// Give the precedence value of the character or operator
// Return the provided precedence value.
int PrecedenceValue(char a){
  // Since the operators are less so I implemented the if-else
  // loop. However if you want to make the precedence table of all
  // operators then make a hashtable for it.
  // Map the operator to a value in that hashtable. 
  if(a=='^'){
    return 3;
  }else if(a=='*'||a=='/'){
    return 2;
  }else if(a=='+'||a=='-'){
    return 1;
  }else{
    return 0;
  }
}

// Operator Precedence Check
// If precedence of first operator is greater than other then return true 
// else return false.
int CheckPrecedence(char first_op, char second_op){
  // Check the precedence value of first operator and second operator
  // If the precedence value of first operator is greater then
  // return true else return false.
  return (PrecedenceValue(first_op)>PrecedenceValue(second_op));
}

// Convert the infix expression to postfix expression according to 
// an algorithm. 
// Return the postfix expression in the form of string if valid
// else return the error message.
string ConvertPostfix(string infix){
  int i;  // Variable declarations
  char mychar;
  string postfix="";
  stack<char> char_stack;

  for(i=0;i<infix.length();i++){  // Iterate through all the characters
    mychar=infix[i];  // temp_storage

    if(IsOpeningBracket(mychar)){ 
      // If the character is opening bracket then push it onto stack.
      char_stack.push(mychar);
    }else if(IsClosingBracket(mychar)){
      // If it is closing bracket then then do the following things from the 
      // stack.
      // 1. Pop all elements until opening bracket is encountered or stack 
      // becomes empty.
      while(!IsOpeningBracket(char_stack.top())){
        postfix+=char_stack.top();
        char_stack.pop();
        if(char_stack.empty()) break;
      }
      // 2. Popping the opening bracket after handling segmentation fault. 
      if(!char_stack.empty()){
        char_stack.pop();
      }
    }else if(IsNumber(mychar)){
      // If the character is a number.
      postfix+=mychar;
    }else if(IsOperator(mychar)){
      // If the chacter is an operator then do this.
      if(char_stack.empty()||IsOpeningBracket(char_stack.top())){
        char_stack.push(mychar);
        continue;
      }

      // Check for the precedence first then do the approprite thing.
      if(CheckPrecedence(mychar,char_stack.top())){
        char_stack.push(mychar);
      }else{
        while(!IsOpeningBracket(char_stack.top())){
          postfix+=char_stack.top();
          char_stack.pop();
          if(char_stack.empty()) break;
        }
        char_stack.push(mychar);
      }
    }else{
      // If the expression contain some invalid symbols then print an error.
      return "Invalid Symbols in expressions!!";
    }
  }

  // If the stack is still not empty and contain some characters then do this.
  while(!char_stack.empty()){
    postfix+=char_stack.top();
    char_stack.pop();
  }

  return postfix;
} // End of Infix to Postfix expression

Implement the main function as per your need.

@untilhamza
Copy link

**/// Improved Version "$" replaced as "^"

include

include

include

using namespace std;

bool IsOperand(char ch)
{
if ((ch >= '0' && ch <= '9') || (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) {
return true;
}
return false;
}

bool IsOperator(char C)
{
if (C == '+' || C == '-' || C == '*' || C == '/' || C == '^') {
return true;
}
return false;
}
bool IsLeftParenthesis(char ch)
{
if (ch == '(') {
return true;
}
return false;
}

bool IsRightParenthesis(char ch)
{
if (ch == ')') {
return true;
}
return false;
}

bool Flag(char ch)
{
if (!IsOperand(ch) || !IsOperator(ch) || !IsLeftParenthesis(ch) || !IsRightParenthesis(ch)) {
return false;
}
return true;
}

int IsRightAssociative(char op)
{
if (op == '^') {
return true;
}
return false;
}

int GetOperatorWeight(char op)
{
int weight = -1;
switch (op) {
case '+':
case '-':
weight = 1;
break;
case '*':
case '/':
weight = 2;
break;
case '^':
weight = 3;
break;
}
return weight;
}

bool 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.
// BUT REMEMBER...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;

}

string InfixToPostfix(string expression)
{
stack S;
string postfix = "";
for (auto& elem : expression) {
if (Flag(elem)) {
continue;
}
// If character is operator, pop two elements from stack, perform operation and push the result back.
else if (IsOperator(elem)) {
while (!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(), elem)) {
postfix += S.top();
S.pop();
}
S.push(elem);
}
else if (IsOperand(elem)) {
postfix += elem;
}
else if (elem == '(') {
S.push(elem);
}
else if (elem == ')') {
while (!S.empty() && S.top() != '(') {
postfix += S.top();
S.pop();
}
S.pop();
}
}

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

return postfix;

}

int main()
{
// std::string expression = "5_4/(5^2)+(6^2^3)";
std::string expression = "A+(B_C-(D/E^F)_G)_H";
std::string postfix = InfixToPostfix(expression);
std::cout << "Output = " << postfix << "\n";
}
**

this is really good

@amanraihot
Copy link

amanraihot commented Aug 11, 2020 via email

@untilhamza
Copy link

Depends. You seen me somewhere?

@kabilan27
Copy link

kabilan27 commented Aug 25, 2020 via email

@keshavgbpecdelhi
Copy link

keshavgbpecdelhi commented Oct 8, 2021

There are a lot of mistakes in this.

@ghost very good observation & very easy to say this. Why don't you provide the flawless implementation!?

People who do good for us, some of us always comes under influence of satan to pull there legs.

@yphbb
Copy link

yphbb commented Dec 9, 2021

In function int GetOperatorWeight(char op), you forgot to put break statements in Switch Case. So, it is always returning weight 3.

It really help me out! Thx!

@PREPONDERANCE
Copy link

#include
#include
using namespace std;

void InfixToPostfix(char *);
bool digit(int);
bool isoperator(int);
bool compare(int, int);
bool openbrackets(int);
bool closebrackets(int);

int main(int argc, char *argv[]) {
char s[100];
fgets(s, sizeof(s), stdin);

InfixToPostfix(s);
cout << "Infix to Postfix " << ": ";
cout << s << endl;

return 0;

}

void InfixToPostfix(char *exp){
static int i = 0, j = 0;
stack s;

for(; exp[i] != '\n'; i++){
	if( exp[i] == ' ' || exp[i] == ',' )
		continue;
	else if( digit(exp[i]) ){
		while( digit(exp[i]) )
			exp[j++] = exp[i++];
		if( exp[i] == '.' ){
			exp[j++] = exp[i++];
			while( digit(exp[i]) )
				exp[j++] = exp[i++];
		}
		exp[j++] = ' ';
		i--;
	}else if( exp[i] == '-' ){
		if( digit(exp[i+1]) ){
			exp[j++] = exp[i++];
			while( digit(exp[i]) )
				exp[j++] = exp[i++];
			exp[j++] = ' ';
			i--;
		}else{
			if( s.empty() )
				s.push('-');
			else{
				while( !s.empty() ){
					exp[j++] = s.top();
					exp[j++] = ' ';
					s.pop();
				}
				s.push('-');
			}
		}
	}else if( isoperator(exp[i]) ){
		if( s.empty() || compare(s.top(), exp[i]))
			s.push(exp[i]);
		else if( !compare(s.top(), exp[i]) ){
			while( !s.empty() ){
				exp[j++] = s.top();
				exp[j++] = ' ';
				s.pop();
			}
			s.push(exp[i]);
		}
	}else if( openbrackets(exp[i]) ){
		i++;
		InfixToPostfix(exp);
	}else if( closebrackets(exp[i]) ){
		while( !s.empty() ){
			exp[j++] = s.top();
			exp[j++] = ' ';
			s.pop();
		}
		return;
	}
}
while( !s.empty() ){
	exp[j++] = s.top();
	exp[j++] = ' ';
	s.pop();
}
exp[j] = '\0';

}

bool digit(int c){
return (c >= '0' && c <= '9' ) ? true : false;
}

bool isoperator(int c){
return (c == '*' || c == '+' || c == '/' || c == '%') ? true : false;
}

bool compare(int a, int b){
bool res = false;
if( b == '' || b == '/' || b == '%' && !(a == '' || a == '/' || a == '%') )
res = true;
return res;
}

bool openbrackets(int c){
return (c == '(' || c == '{' || c == '[') ? true : false;
}

bool closebrackets(int c){
return (c == ')' || c == '}' || c == ']') ? true : false;
}
// My own cpp codes covering more scenarios including floating numbers and negative numbers

@AymanUzayr
Copy link

`#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100

char stack[MAX_SIZE];
int top = -1;

void push(char x)
{
if(top == MAX_SIZE -1) return;
else{
stack[++top] = x;
}
}
char pop()
{
if(top == -1) return -1;
else{
return stack[top--];
}
}

bool isEmpty() {
return top == -1;
}

bool IsOperator(char C){
if (C == '+' || C == '-' || C == '*' || C == '/' || C == '^')
{
return true;
}
return false;
}

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;
}

bool IsRightAssociative(char op){
if(op == '^') return true;
return false;
}

int GetOperatorPriority(char op){
int priority = -1;
switch(op){
case '+':
case '-':
priority = 1;
break;
case '*':
case '/':
priority = 2;
break;
case '^':
priority = 3;
break;
}
return priority;
}

bool HasHigherPrecedence(char op1, char op2){
int op1Priority = GetOperatorPriority(op1);
int op2Priority = GetOperatorPriority(op2);
if(op1Priority == op2Priority){
if (IsRightAssociative(op1)) return false;
else
{
return true;
}
}
return op1Priority > op2Priority;
}

char* InfixToPostfix(char* expression){
int len = strlen(expression);
char* postfix = (char*)malloc(sizeof(char) * (len + 2));
int j = 0;
for(int i = 0; i < len; i++){
if(expression[i] == ' ' || expression[i] == ',') continue;
if(IsOperator(expression[i])){
while(!isEmpty() && stack[top] != '(' && HasHigherPrecedence(stack[top], expression[i])){
postfix[j++] = pop();
}
push(expression[i]);
}

        if(IsOperand(expression[i])){
            postfix[j++] = expression[i];
        }
        else if(expression[i] == '('){
            push(expression[i]);
        }
        else if (expression[i] == ')')
        {
            while (!isEmpty() && stack[top] != '(')
            {
                postfix[j++] = pop(); 
            }
            if (!isEmpty() && stack[top] == '(') {
                pop();
        }
        }

}
while (!isEmpty())
{
postfix[j++] = pop();

    }
    postfix[j] = '\0';
    return postfix;

}

int main(){
char infix[MAX_SIZE] = "a+b*(c^d-e)^(f+g*h)-i";

// Function call
char* postfix = InfixToPostfix(infix);
printf("%s\n", postfix);
free(postfix);
return 0;

}`

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment