Infix to Postfix conversion in C++ using stack. We are assuming that both operators and operands in input will be single character.

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

your code is good zz

MODAK27 kidding man

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...

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

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.

**/// 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

Do we know each other?

…

On Thu, Feb 6, 2020, 12:48 PM SeongmanPark ***@***.***> wrote: your code is good zz — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <https://gist.github.com/7867739?email_source=notifications&email_token=AJ7P7CWLFJXZMKESB2MANHLRBO2ULA5CNFSM4HMJWHC2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAGBLQ4#gistcomment-3168014>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AJ7P7CU4UMZ256KWT2UUBCDRBO2ULANCNFSM4HMJWHCQ> .

Depends. You seen me somewhere?

Thank you for your wonderful work.

…

On Tue, 25 Aug, 2020, 7:59 AM Hamza Kyamanywa, ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ Depends. You seen me somewhere? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <https://gist.github.com/7867739#gistcomment-3429771>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AP3MQHN3TQ2PUOI3KBIRKU3SCMOW7ANCNFSM4HMJWHCQ> .

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.

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!

#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

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

}`