Skip to content

Instantly share code, notes, and snippets.

@mycodeschool

mycodeschool/InfixToPostfix.cpp

Created December 9, 2013 05:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mycodeschool/7867739 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mycodeschool/7867739 to your computer and use it in GitHub Desktop.
Download ZIP
Infix to Postfix conversion in C++ using stack. We are assuming that both operators and operands in input will be single character.
Raw
InfixToPostfix.cpp
/*
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;
}
@PREPONDERANCE
Copy link

PREPONDERANCE commented Jan 13, 2023

#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

AymanUzayr commented May 28, 2023

`#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