Question

This programming assignment needs to be written so that it can do infix expression to postfix expression (explained in the direction below). When the infix expression is translated into postfix, the parser needs to check if the operators and operands are accepted or rejected. It must look like the what is in the first page, asking the user to continue or end the translation.

Answer 1

Infix Expression: Expression of the form a op b. When an operator is in-between every pair of operands.

Postfix Expression: Expression of the form a b op. When an operator is followed for every pair of operands.

Algorithm:

1. Scan the infix expression from left to right.

2.If the scanned character is an operand,output it.

3. Else,

3.1 If the precedence of the scanned operator is greater than the precendence of the operator in the stack contains a'('),push it.

3.2 Else pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing the push the scanned operator of the stack.

4.If the scanned character is an '(' ,push it to the stack.

5. If the scanned character is an ')' , pop the stack and output it until a '(' is encountered,and discard both the parenthesis.

6. Repeat steps 2-6 until infix expression is scanned.

7. Print the output.

8. Pop and output from the stack until it is not empty.

Program in C++:

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

}