Question

In: Computer Science

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

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

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

In c++ please.

Solutions

Expert Solution

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


Related Solutions

**write a java program infix to postfix**showing the expression tree*** I. Input All input data are...
**write a java program infix to postfix**showing the expression tree*** I. Input All input data are from a file "in.dat". The file contains a sequence of infix form expressions, one per line. The character '$' is an end mark. For example, the following file has four infix form expressions: 1 + 2 * 3 ^ ! ( 4 == 5 ) $ 3 * ( 6 - 4 * 5 + 1) + 2 ^ 2 ^ 3 $ 77...
Using STL stack class, implement in C++ a function that converts an infix expression to postfix...
Using STL stack class, implement in C++ a function that converts an infix expression to postfix expression,
Convert an infix expression to its postfix representation in JAVA
Convert an infix expression to its postfix representation in JAVA
how do I write a class PostFix that has one method covert that converts an infix...
how do I write a class PostFix that has one method covert that converts an infix expression (as a string input) to postfix in java?
Please make sure that these infix and postfix equations have these answers nothing else: Infix: (3...
Please make sure that these infix and postfix equations have these answers nothing else: Infix: (3 * 4 - (2 + 5)) * 4 / 2 = valid expression 10 + 6 * 11 -(3 * 2 + 14) / 2 = valid expression Postfix: 9 3 / 6 / 4 * 10 - = -8 9 3 / 6 / 4 * -10 - = 12 (a) Using java.util.stack to write a java program to validate and calculate the...
(Convert infix to postfix) Note: Postfix notation is a way of writing expression without using parentheses....
(Convert infix to postfix) Note: Postfix notation is a way of writing expression without using parentheses. For example, the expression ( 11 + 12 ) * 13 would be written as 11 12 + 13 * Assume that ALWAYS there is a space between operands and operators in the input expression. Use two stacks, one to store the operands and one to store the operators. Your program only accpets following operators : ( ) + - / * Write a...
C++ program that can take in EITHER "infix" or "prefix" (NOT POSTFIX) and transforms it into...
C++ program that can take in EITHER "infix" or "prefix" (NOT POSTFIX) and transforms it into the other one. Should use stack and have infixToPrefix and prefixToInfix functions with a simple main function for execution.
Write a program that takes an infix expression as input and produces a postfix expression. The...
Write a program that takes an infix expression as input and produces a postfix expression. The infix and postfix expressions are in the form of vectors of strings. We will test with a main method that takes a file name as input from the command line. We will test your implementation using printPostFix() method.   There are sample input and output files in this folder. You may edit the header file. Example 1 infix expression = apple + banana * cat...
Using java.util.Stack and java.util.StringTokenizer to write a program that converts an infix expression to a postfix...
Using java.util.Stack and java.util.StringTokenizer to write a program that converts an infix expression to a postfix expression using data from infix.dat. Make sure your program can handle negative number. If the input expression can’t be converted, display error message.(1.5 points) (Should remove parentheses) infix.dat 5 * 6 + -10 3 - 2 + 4 7 ( 3 * 4 - (2 + 5)) * 4 / 2 10 + 6 * 11 -(3 * 2 + 14) / 2 2...
Implement an infix expression to postfix expression convertor in C++. Note: - Support +, -, *,...
Implement an infix expression to postfix expression convertor in C++. Note: - Support +, -, *, /, ( and ) in infix expressions. - Operands will be nonnegative only. - Assume infix expressions are valid and well formatted (one blank space to separate operand/operator) For example, - 3 * 4 + 5 ➔ 3 4 * 5 + - 3 + 4 * 5 ➔ 3 4 5 * + - (3 + 4) * (5 + 6) ➔ 3...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT