Infix To Postfix Contest 2

CodeChef-DSA-learners
1

What is wrong in my code, please help

#include <bits/stdc++.h>
using namespace std;

int Precedence(char c)
{
    if(c == '+' || c == '-')
    {
        return(1);
    }
    else if(c == '*' || c == '/')
    {
        return(2);
    }
    else if(c == '^')
    {
        return(3);
    }
    return(0);
}

int isOperand(char c)
{
    if(c == '+' || c == '-' || c == '(' || c == ')' || c == '*' || c == '/' || c == '^')
    {
        return(0);
    }
    else
    {
        return(1);
    }
}

void inTopost(string s,int l)
{
    stack<char> st;
    int i = 0;
    
    while(i < l)
    {
        if(isOperand(s[i]))
        {
            cout<<s[i];
            i++;
        }
        else
        {
            if(st.empty() || s[i] == '(')
            {
                st.push(s[i]);
                i++;
            }
            else 
            {
                if(s[i] == ')')
    			{
    				while(st.top() != '(' && !st.empty())
    				{
						cout<<st.top();
						st.pop();	
    				}
				    st.pop();
				    i++;	   
    			}
    			else if(Precedence(s[i]) > Precedence(st.top()))
    			{
    				st.push(s[i]);
    				i++;
    			}
    			else
    			{
    			    while(Precedence(s[i]) <= Precedence(st.top()) && !st.empty())
				    {
				        cout<<st.top();
					    st.pop();   
				    }
				    st.push(s[i]);
				    i++;
    			}
            }
        }
    }
    
    while(!st.empty())
    {
		cout<<st.top();
    	st.pop();
    }
    
    cout<<endl;
}

int main() 
{
    ios_base::sync_with_stdio(0);
    
    int t;
    cin>>t;
    
    while(t--)
    {
    	int len;
    	cin>>len;
    	
        string s;
        cin>>s;
        
        inTopost(s,len);
    }
    
	return 0;
}
2

Hi @riri_4

Check lines 56 and 71 in your code, those lines contained the error. I have fixed it.

#include <bits/stdc++.h>
using namespace std;

int Precedence(char c)
{
    if(c == '+' || c == '-')
    {
        return(1);
    }
    else if(c == '*' || c == '/')
    {
        return(2);
    }
    else if(c == '^')
    {
        return(3);
    }
    return(0);
}

int isOperand(char c)
{
    if(c == '+' || c == '-' || c == '(' || c == ')' || c == '*' || c == '/' || c == '^')
    {
        return(0);
    }
    else
    {
        return(1);
    }
}

void inTopost(string s,int l)
{
    stack<char> st;
    int i = 0;
    
    while(i < l)
    {
        if(isOperand(s[i]))
        {
            cout<<s[i];
            i++;
        }
        else
        {
            if(st.empty() || s[i] == '(')
            {
                st.push(s[i]);
                i++;
            }
            else 
            {
                if(s[i] == ')')
    			{
    				while(!st.empty() && st.top() != '(')
    				{
						cout<<st.top();
						st.pop();	
    				}
				    st.pop();
				    i++;	   
    			}
    			else if(Precedence(s[i]) > Precedence(st.top()))
    			{
    				st.push(s[i]);
    				i++;
    			}
    			else
    			{
    			    while(!st.empty() && Precedence(s[i]) <= Precedence(st.top()))
				    {
				        cout<<st.top();
					    st.pop();   
				    }
				    st.push(s[i]);
				    i++;
    			}
            }
        }
    }
    
    while(!st.empty())
    {
		cout<<st.top();
    	st.pop();
    }
    
    cout<<endl;
}

int main() 
{
    ios_base::sync_with_stdio(0);
    
    int t;
    cin>>t;
    
    while(t--)
    {
    	int len;
    	cin>>len;
    	
        string s;
        cin>>s;
        
        inTopost(s,len);
    }
    
	return 0;
}
3

Hi @anon85470456
It is still giving Runtime Error (Segmentation Fault)

4

Why have you removed the !st.empty() conditions? You just needed to change the order of those as I did in the above code

1 Like
6

@anon85470456
Oh Okay!
But can you explain why with just by changing their position it got accepted?
Thankyou in advance!

7

Let’s take this syntax for example :

while(st.top() != '(' && !st.empty())

When this statement it executed it first checks if st.top() != ‘(’. Now in a case if st (the stack) is empty, you are doing st.top() on an empty stack which results in error.

Now, on changing the order in the syntax to this:

while(!st.empty() && st.top() != '(')

It will first check if !st.empty() is true or false and if it is false the entire value of this statement will be false irrespective of the value of st.top() because we are doing and (&&) operation there and st.top() will not get executed.

2 Likes
8

Got it!
Thankyou very much