Question

I need an infix to postfix function that accounts for all (, ), {, }, [, ].. For example.

8-{{(1-[0+4]+8)}}

In c++ please.

Answer 1

Here is the source code in C++ for infix to postfix function. I have shared multiple solutions for your convenience.

Kindly give a Thumbs up/Like if you find this answer helpful. It means a lot to me. God bless you !!

Solution1

// C++ Program infix to postfix expression using stack (array) in data structure
#include<iostream>
#include<string>
#define MAX 20
using namespace std;

char stk[20];
int top=-1;
// Push function here, inserts value in stack and increments stack top by 1
void push(char oper)
{
    if(top==MAX-1)
    {
        cout<<"stackfull!!!!";
    }
   
    else
    {
        top++;
        stk[top]=oper;
    }
}
// Function to remove an item from stack.  It decreases top by 1
char pop()
{
    char ch;
    if(top==-1)
    {
        cout<<"stackempty!!!!";
    }
    else
    {
        ch=stk[top];
        stk[top]='\0';
        top--;
        return(ch);
    }
    return 0;
}
int priority ( char alpha )
{
    if(alpha == '+' || alpha =='-')
    {
        return(1);
    }
 
    if(alpha == '*' || alpha =='/')
    {
        return(2);
    }
 
    if(alpha == '$')
    {
        return(3);
    }
 
    return 0;
}
string convert(string infix)
{
    int i=0;
    string postfix = "";   
    while(infix[i]!='\0')
    {       
        if(infix[i]>='a' && infix[i]<='z'|| infix[i]>='A'&& infix[i]<='Z')          
        {
            postfix.insert(postfix.end(),infix[i]);
            i++;
        }       
        else if(infix[i]=='(' || infix[i]=='{'  || infix[i]=='[')
        {
            push(infix[i]);
            i++;
        }        
        else if(infix[i]==')' || infix[i]=='}'  || infix[i]==']')
        {
            if(infix[i]==')')
            {
                while(stk[top]!='(')
                {               postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
            if(infix[i]==']')
            {
                while(stk[top]!='[')
                {
                    postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
 
            if(infix[i]=='}')
            {
                while(stk[top]!='{')
                {
                    postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
        }
        else            
        {
            if(top==-1)
            {
                push(infix[i]);
                i++;
            }
 
            else if( priority(infix[i]) <= priority(stk[top])) {
                postfix.insert(postfix.end(),pop());
               
                while(priority(stk[top]) == priority(infix[i])){
                    postfix.insert(postfix.end(),pop());
                    if(top < 0) {
                        break;
                    }
                }
                push(infix[i]);
                i++;
            }
            else if(priority(infix[i]) > priority(stk[top])) {
                push(infix[i]);
                i++;
            }
        }
    }
    while(top!=-1)
    {
        postfix.insert(postfix.end(),pop());
    }
    cout<<"The converted postfix string is : "<<postfix; //it will print postfix conversion  
    return postfix;
}

int main()
{
    int cont;
    string infix, postfix;
    cout<<"\nEnter the infix expression : "; //enter the expression
    cin>>infix;
    postfix = convert(infix);
    return 0;
}

Solution2

/* C++ implementation to convert infix expression to postfix*/
// Note that here we use std::stack for Stack operations 
#include<bits/stdc++.h> 
using namespace std; 

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

// The main function to convert infix expression 
//to postfix expression 
void infixToPostfix(string s) 
{ 
        std::stack<char> st; 
        st.push('N'); 
        int l = s.length(); 
        string ns; 
        for(int i = 0; i < l; i++) 
        { 
                // If the scanned character is an operand, add it to output string. 
                if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z')) 
                ns+=s[i]; 

                // If the scanned character is an ‘(‘, push it to the stack. 
                else if(s[i] == '(') 
                
                st.push('('); 
                
                // If the scanned character is an ‘)’, pop and to output string from the stack 
                // until an ‘(‘ is encountered. 
                else if(s[i] == ')') 
                { 
                        while(st.top() != 'N' && st.top() != '(') 
                        { 
                                char c = st.top(); 
                                st.pop(); 
                        ns += c; 
                        } 
                        if(st.top() == '(') 
                        { 
                                char c = st.top(); 
                                st.pop(); 
                        } 
                } 
                
                //If an operator is scanned 
                else{ 
                        while(st.top() != 'N' && prec(s[i]) <= prec(st.top())) 
                        { 
                                char c = st.top(); 
                                st.pop(); 
                                ns += c; 
                        } 
                        st.push(s[i]); 
                } 

        } 
        //Pop all the remaining elements from the stack 
        while(st.top() != 'N') 
        { 
                char c = st.top(); 
                st.pop(); 
                ns += c; 
        } 
        
        cout << ns << endl; 

} 

//Driver program to test above functions 
int main() 
{ 
        string exp = "a+b*(c^d-e)^(f+g*h)-i"; 
        infixToPostfix(exp); 
        return 0; 
} 

Driver program to test above functions

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

Solution 3

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

Solution 4

#include <iostream>
#include <stack>
#include <string>
using namespace std;


// Simply determine if character is one of the four standard operators.
bool isOperator(char character) {
    if (character == '+' || character == '-' || character == '*' || character == '/') {
        return true;
    }
    return false;
}


// If the character is not an operator or a parenthesis, then it is assumed to be an operand.
bool isOperand(char character) {
    if (!isOperator(character) && character != '(' && character != ')') {
        return true;
    }
    return false;
}


// Compare operator precedence of main operators.
// Return 0 if equal, -1 if op2 is less than op1, and 1 if op2 is greater than op1.
int compareOperators(char op1, char op2) {
    if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) { return -1; }
    else if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/')) { return 1; }
    return 0;
}


int main()
{
    // Empty character stack and blank postfix string.
    stack<char> opStack;
    string postFixString = "";
        
    char input[100];

    // Collect input
    cout << "Enter an expression: ";
    cin >> input;

    // Get a pointer to our character array.
    char *cPtr = input;

    // Loop through the array (one character at a time) until we reach the end of the string.
    while (*cPtr != '\0') {
        // If operand, simply add it to our postfix string.
        // If it is an operator, pop operators off our stack until it is empty, an open parenthesis or an operator with less than or equal precedence.
        if (isOperand(*cPtr)) { postFixString += *cPtr; }
        else if (isOperator(*cPtr)) {
            while (!opStack.empty() && opStack.top() != '(' && compareOperators(opStack.top(),*cPtr) <= 0) {
                postFixString += opStack.top();
                opStack.pop();
            }
            opStack.push(*cPtr);
        }
        // Simply push all open parenthesis onto our stack
        // When we reach a closing one, start popping off operators until we run into the opening parenthesis.
        else if (*cPtr == '(') { opStack.push(*cPtr); } 
        else if (*cPtr == ')') {
            while (!opStack.empty()) {
                if (opStack.top() == '(') { opStack.pop(); break; }
                postFixString += opStack.top();
                opStack.pop();
            }
        }

        // Advance our pointer to next character in string.
        cPtr++;
    }

    // After the input expression has been ran through, if there is any remaining operators left on the stack
    // pop them off and put them onto the postfix string.
    while (!opStack.empty()) {
        postFixString += opStack.top();
        opStack.pop();
    }


    // Show the postfix string at the end.
    cout << "Postfix is: " << postFixString << endl;
    return 0;
}

Kindly give a Thumbs up/Like if you find this answer helpful. It means a lot to me. God bless you !!