Convert from an Infix Expression to Postfix (C++) Using Stacks

Infix to Postfix Converter in C++ gives no output

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

Infix to Postfix using stack

You really should learn how to use a debugger, it's a great tool for figuring out problems like these. However, I ran it and figured out your problem:

On this line:

while(precedence(list->top->data)<=precedence(string[i])){

When you're iterating through the list, you need to check whether the stack is empty each time, not only before you go into the loop. So, do something like this:

while(!isEmpty(list) && precedence(list->top->data)<=precedence(string[i])){

instead.

infix to postfix conversion using stack shows an infinite loop

Code stuck on ')'.

Adding a i++; somewhere in the else if(infix[i] == ')') { .... } block resulted in below. Else code continues to parse ')'.

postfix is xyz/-kd*-

---

How bug was found:

Added a debug print.

while (infix[i] != '\0') {
  printf("Infix: %d %c\n", infix[i], infix[i]);  // added

That led to see code stuck when ')' was parsed.

---

Related Topics