Converting infix to postfix using stack data structure with linked list

Question

I am trying to create a program to convert an infix expression to a postfix expression using stack data structure in c++ using a structure Node. The related functions are there to push, pop values from the stack. The program compiles but after i enter a infix expression example 'a+b' in the output window, there is a runtime error. Here is the complete code..

#include <iostream>
#include<cstring>

using namespace std;

struct Node{
    char data;
    struct Node * next;
}*top=NULL;

void Push(char x)
{   struct Node* p=new Node;
    if(p==NULL)
        cout<<"\nStack Overflow";
    else{
        p->data=x;
        p->next=top;
        top=p;
    }
}  

char Pop(){
    int x=-1;
    struct Node * p;
    if(top==NULL)
        cout<<"\nStack is Empty";
    else{
         p=top;
         x=p->data;
         top = top->next;
         delete p;
    }
    return x;
}

int isEmpty(){
    return top?0:1;
}

int Pre(char ch){
    if(top==NULL)
        return 0;
    else if(ch == '-' || ch == '+')
        return 1;
    else if(ch == '*' || ch == '/')
        return 2;
    else
        return 3;
}
char * InToPost(char *infix){
    char *postfix = new char[strlen(infix)+1];
    int i=0,j=0;
    while(infix[i]!='\0')
    {
        if(Pre(infix[i]>Pre(top->data)))
            Push(infix[i++]);
        else{
            while(Pre(infix[i])<=Pre(top->data))
                postfix[j++]= Pop();
          }
    }
    while(!isEmpty())
        postfix[j++]=Pop();
    postfix[j] = '\0';
    return postfix;
}

int main(){
    char *infix = new char[30];
    cin>>infix;
   cout<<InToPost(infix);
}

Madhur Vashistha Madhur Vashistha · Accepted Answer · 2020-06-19T12:16:04

The reason for the error may be that you have not incremented the value of 'i' in the else part of the while loop. This is what leads to an infinite loop. Also, you might have mistakenly placed the parenthesis incorrectly in the if condition of the while loop. But, even if you make these changes it will not give you the correct results. I think you are trying a wrong approach. Every alphabet should be pushed directly into the 'postfix' array and not in the stack. We have to check the precendences of the operators only and not for the alphabets. You can try implementing the following code. I have not used the linked implementation of the stack but directly used the stack from STL, but you can do the required changes according to your need.Here I have pushed an additional charater 'A' into the stack so as to check if the stack has no operators in it.

int prec(char ch){
    if(ch == '^')
        return 3;
    if(ch == '*' or ch == '/')
        return 2;
    if(ch == '+' or ch == '-')
        return 1;
    return -1;
}

string infixToPostfix(string x)
{
    stack<char> s;
    s.push('A');
    string ans;
    int n = x.length();

    for(int i = 0 ; i < n; i++){

        if((x[i] >= 'a' and x[i] <= 'z') or (x[i] >= 'A' and x[i] <= 'Z'))
            ans += x[i];

        else if(x[i] == '(')
            s.push(x[i]);

        else if(x[i] == ')'){

            while(s.top() != 'A' and s.top() != '('){
                ans += s.top();
                s.pop();
            }
            if(s.top() == '('){
                s.pop();
            }
        }
        else{

            while(s.top() != 'A' and prec(x[i]) <= prec(s.top())){
                ans += s.top();
                s.pop();
            }
            s.push(x[i]);

        }

    }

    while(s.top() != 'A'){
        ans += s.top();
        s.pop();
    }

    return ans;
}

Try this. It should work! It will also work for expressions containing paranthesis, like a+b*(c+d)+(f+g)

Converting infix to postfix using stack data structure with linked list

2 Answers