I made a function infixToPostfix() which converts an infix expression to a postfix expression. But my program generates no output on running. Please point out the errors in my program.

Code:

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdlib>
using namespace std;

int isOperator(char x)
{
    return (x == '-' || x == ' ' || x == '/' || x == '*');
}

int precedenceOfOperators(char x)
{
    if (x == ' ' || x == '-')
    {
        return 1;
    }
    else if (x == '/' || x == '*')
    {
        return 2;
    }

    return 0;
}

char *infixToPostfix(char infix[])
{
    int i = 0, j = 0;
    stack<char> lobby;
    char *postfix = (char *)malloc((strlen(infix   1)) * sizeof(char));
    while (infix[i] != '\0')
    {
        if (!isOperator(infix[i]))
        {
            postfix[j] = infix[i];
            i  ;
            j  ;
        }
        else
        {
            if (!lobby.empty())
            {
                if (precedenceOfOperators(infix[i]) > precedenceOfOperators(lobby.top()))
                {
                    lobby.push(infix[i]);
                }
                else
                {
                    postfix[j] = lobby.top();
                    lobby.pop();
                    j  ;
                }
            }
            else if (lobby.empty())
            {
                lobby.push(infix[i]);
            }
        }
    }
    while (!lobby.empty())
    {
        postfix[j] = lobby.top();
        lobby.pop();
        j  ;
    }
    return postfix;
}

Implementation:

int main()
{
    char infix[] = {'a', '-', 'b', ' ', 'c', '*', 'd'};
    char *postfix = infixToPostfix(infix);
    for (int j = 0; postfix[j] != '\0'; j  )
    {
        cout << postfix[j];
    }
    return 0;
}

Logic:

1. I created a character pointer variable that will hold our postfix expression. Now, we iterate over our infix expression. If we receive an operand, we concatenate it to the postfix variable. Else if we encounter an operator, we proceed with the following steps:

• Keep in account the operator and its relative precedence ('/' and '*' have more precedence than ' ' and '-').
• If either the stack is empty or its topmost operator has lower relative precedence, push this operator-precedence pair inside the stack 'lobby'.
• Else, keep popping operators from the stack 'lobby' and concatenate them to the postfix expression until the topmost operator becomes weaker in precedence relative to the current operator.

2. If you reach the EOE, pop every element from the stack 'lobby', if there is any, and concatenate them as well to the postfix expression.

CodePudding user response：

Your code is exceeding the time limit because it is stuck in the infinite loop. You have not updated the i variable- which is the index of the infix array in the else part of the loop i.e when infix[i] is an operator. i.e. in this part of the code

else
        {
            if (!lobby.empty())
            {
                if (precedenceOfOperators(infix[i]) > precedenceOfOperators(lobby.top()))
                {
                    lobby.push(infix[i]);
                }
                else
                {
                    postfix[j] = lobby.top();
                    lobby.pop();
                    j  ;
                }
            }
            else if (lobby.empty())
            {
                lobby.push(infix[i]);
            }
        }

Here is the updated code which is giving perfect output. ( I have made some minor changes as per my convenience, you can keep the code the same and add the i in the else part)

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdlib>
using namespace std;

int isOperator(char x)
{
    return (x == '-' || x == ' ' || x == '/' || x == '*');
}

int precedenceOfOperators(char x)
{
    if (x == ' ' || x == '-')
    {
        return 1;
    }
    else if (x == '/' || x == '*')
    {
        return 2;
    }

    return 0;
}

string infixToPostfix(char infix[])
{
    int i = 0, j = 0;
    if(sizeof(infix)==0)
    {
        return "";
    }
    int n=sizeof(infix)/sizeof(infix[0]);
    stack<char> lobby;
    string postfix = "";
    while (i < n)
    {
        if (!isOperator(infix[i]))
        {   postfix=postfix infix[i];
            i  ;
            j  ;
        }
        else
        {
            if (!lobby.empty())
            {
                if (precedenceOfOperators(infix[i]) > precedenceOfOperators(lobby.top()))
                {
                    lobby.push(infix[i]);
                }
                else
                {
                    postfix = postfix lobby.top();
                    lobby.pop();
                    j  ;
                }
            }
            else if (lobby.empty())
            {
                lobby.push(infix[i]);
            }
            i  ;
        }
    }
    while (lobby.empty()==false)
    {
        postfix = postfix lobby.top();
        lobby.pop();
        j  ;
    }
    return postfix;
}
int main()
{
    char infix[] = {'a', '-', 'b', ' ', 'c', '*', 'd'};
    string postfix = infixToPostfix(infix);
    for (int j = 0; j < postfix.size() ; j  )
    {
        cout << postfix[j];
    }
    return 0;
}