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