727 - Equation

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

software
New poster
Posts: 3
Joined: Tue Aug 27, 2013 12:15 am

727,uva problem

Post by software » Tue Aug 27, 2013 11:02 pm

Problem ID:727
Here is my code:
//polish notation
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{
char data;
struct node *next;
struct node *prev;
}node;
char a[1000][1000];
node* push(node *head,char ch)
{

node *cursor=head;
node *new_node=(node *)malloc(sizeof(node));
if(cursor==NULL)
{
new_node->next=NULL;
new_node->prev=NULL;
new_node->data=ch;
return new_node;
}
else
{
new_node->next=NULL;
new_node->data=ch;
cursor->next=new_node;
new_node->prev=cursor;
return new_node;

}


}
void pop(node *last)
{

node *back=last->prev;
if(back!=NULL)
{
back->next=NULL;
free(last);
}

}
node* my_fnc1(char output[],int *j,node *new_node)
{
node *first,*last,*p,*q;
node *cursor;
last=new_node;
cursor=new_node;
while(cursor->data!='(')
{
cursor=cursor->prev;
}
first=cursor;
cursor=last;
while(cursor!=first)
{


p=cursor;
cursor=cursor->prev;
if(p==last)
{
pop(p);
}
else if(p!=last)
{
output[*j]=p->data;
(*j)++;
pop(p);
}

}
q=cursor->prev;
pop(cursor);
return q;

}

int main()
{
node *new_node=NULL;
char input[1000];
char output[1000];
int i,n,k;
char ch;
char str[1000];
scanf("%d",&n);
getchar();
getchar();
for(k=0;k<n;k++)
{
i=0;
while(gets(str))
{
if(str[0]=='\0')
break;
ch=str[0];
input[i++]=ch;
}
input='\0';
strcpy(a[k],input);
}

for(k=0;k<n;k++)
{
int j=0;
new_node=push(new_node,'(');
for(i=0;a[k]!='\0';i++)
{
if(a[k]=='('||a[k]=='+'||a[k]=='-'||a[k]=='*'||a[k]=='/'||a[k]==')')
{
new_node=push(new_node,a[k]);
node *cursor=new_node;
node *p;
while((cursor->data=='+'||cursor->data=='-')&&(cursor->prev->data=='*'||cursor->prev->data=='/'))
{
p=cursor;
output[j]=cursor->prev->data;
j++;
cursor->prev->data=cursor->data;
cursor=cursor->prev;
pop(p);
new_node=cursor;
}
while((cursor->data=='/'&&cursor->prev->data=='*')||(cursor->data=='*'&&cursor->prev->data=='/')||(cursor->data=='+'&&cursor->prev->data=='-')||(cursor->data=='-'&&cursor->prev->data=='+'))
{
p=cursor;
output[j]=cursor->prev->data;
j++;
cursor->prev->data=cursor->data;
cursor=cursor->prev;
pop(p);
new_node=cursor;
}
if(new_node->data==')')
new_node=my_fnc1(output,&j,new_node);

}
else
{
output[j]=a[k];
j++;
}
}
new_node=push(new_node,')');
my_fnc1(output,&j,new_node);
output[j]='\0';
printf("%s\n\n",output);
}


return 0;

}

I can not understand why my code get RE .Please help me.
I did not get any reply though I sent another message .

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 727,uva problem

Post by brianfry713 » Wed Aug 28, 2013 10:02 pm

Don't double post.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 727,uva problem

Post by brianfry713 » Wed Aug 28, 2013 10:11 pm

Print a blank line between different expressions. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

727 - Equation - RE

Post by lukai » Mon Sep 23, 2013 8:17 pm

Code: Select all

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cctype>
#include <cstring>
#include <typeinfo>
#include <exception>
#include <stdexcept>
#include <memory>
#include <fstream>
#include <string>
#include <sstream>
#include <functional>
#include <iterator>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cstdio>
#include <locale>
#include <limits>
#include <utility>

using namespace std;

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    string given,temp,output;
    stack<char>maintanance;
    int cases;
    cin>>cases;
    getchar();
    getchar();
    while(cases--)
    {
        while(getline(cin,temp)&&temp.size())
        {
            given+=temp;
            temp.clear();
        }
        for(int i=0;i<given.size();i++)
        {
            if(given[i]=='(')
            {
                maintanance.push(given[i]);
            }
            else if(given[i]==')')
            {
                if(maintanance.size())
                {
                    while(maintanance.top()!='(')
                    {
                        output+=maintanance.top();
                        maintanance.pop();
                    }
                }
                maintanance.pop();
            }
            else if(given[i]=='/'||given[i]=='*')
            {
                if(maintanance.size())
                {
                    while((maintanance.top()=='*'||maintanance.top()=='/'))
                    {
                        output+=maintanance.top();
                        maintanance.pop();
                    }
                }

                maintanance.push(given[i]);
            }
            else if((given[i]=='+'||given[i]=='-'))
            {
                if(maintanance.size())
                {
                    while(maintanance.top()=='*'||maintanance.top()=='/'||maintanance.top()=='+'||maintanance.top()=='-')
                    {
                        output+=maintanance.top();
                        maintanance.pop();
                    }
                }
                maintanance.push(given[i]);
            }
            else
            {
                output+=given[i];
            }

        }
        while(!maintanance.empty())
        {
            output+=maintanance.top();
            maintanance.pop();
        }
        cout<<output<<endl;
        if(cases>0)
        {
            cout<<endl;
        }
        given.clear();
        temp.clear();
        output.clear();
        maintanance=stack<char>();

    }
	return 0;
}
I tried to find out the bug , but can't find it. I really don't get any point of getting runtime error.

plz help :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 727 - Equation - RE

Post by brianfry713 » Tue Sep 24, 2013 2:06 am

Try input:

Code: Select all

2

3
+
2
*
5

3
*
2
+
5
Output should be:

Code: Select all

325*+

32*5+
Check input and AC output for thousands of problems on uDebug!

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

Re: 727 - Equation - RE

Post by lukai » Tue Sep 24, 2013 7:15 am

For your given I/O , the output matches with mine, and there is no problem running the code. Still I'm getting Runtime Error, and can't find the problem

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 727 - Equation - RE

Post by brianfry713 » Tue Sep 24, 2013 10:52 pm

Check input and AC output for thousands of problems on uDebug!

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

Re: 727 - Equation - RE

Post by lukai » Wed Sep 25, 2013 4:29 am

But it runs well in my PC :( i can't get it.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 727 - Equation - RE

Post by brianfry713 » Fri Sep 27, 2013 11:20 pm

Your code is throwing a seg fault on line 88:
while(maintanance.top()=='*'||maintanance.top()=='/'||maintanance.top()=='+'||maintanance.top()=='-')

Perhaps you should be checking if maintanance is empty.
Check input and AC output for thousands of problems on uDebug!

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

Re: 727 - Equation - RE

Post by lukai » Sat Sep 28, 2013 1:40 pm

AC :D

Thanks brianfry173

MohammadFatafta
New poster
Posts: 1
Joined: Tue Jan 21, 2014 12:40 pm

Re: 727 - Equation

Post by MohammadFatafta » Sat Jan 25, 2014 1:20 am

my code gots WA although it passes all the i/o in this thread! any idea why? :S

Code: Select all

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
using namespace std;

int main()
{
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);		
	int t;
	char ch;
	cin>>t;
	cin.get();
	cin.get();
	while(t--)
	{
		stack<char> ops;
		while(cin.get(ch))
		{
			if(ch=='\n' || ch==EOF)
				break;
			if(ch>='0'&& ch<='9')
				{cout<<ch;goto end;}
			if(ch=='(' || ops.empty() || (ch=='*' && ops.top()!='/' && ops.top()!='*' ) || (ch=='/'&& ops.top()!='*' &&ops.top()!='/') ||  (ch=='+' && ops.top()=='(') || (ch=='-' && ops.top()=='(') )
				{ops.push(ch);goto end;}
			if(ch=='+' || ch=='-')
			{
				while(!ops.empty()&&ops.top()!='(')
				{
					cout<<ops.top();ops.pop();
				}
				ops.push(ch);
				goto end;
	
			}
			else if(ch=='/' || ch=='*')
			{
				cout<<ops.top();ops.pop();
				ops.push(ch);
				goto end;
			}
			else if (ch==')')
			{
				while(ops.top()!='(')
					{cout<<ops.top();ops.pop();}
				ops.pop();
			}
			end:
			cin.get(ch);
		}
		while(!ops.empty())
			{cout<<ops.top();ops.pop();}cout<<endl;
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 727 - Equation

Post by brianfry713 » Mon Jan 27, 2014 10:32 pm

Don't read and write to files.
Check input and AC output for thousands of problems on uDebug!

shaficse
New poster
Posts: 5
Joined: Sun Aug 17, 2014 8:20 pm

Re: 727 - Equation

Post by shaficse » Sun Aug 24, 2014 10:14 pm

I am getting wrong answer though i have gotten equivalent postfix expression. may be i am not printing a blank line properly. pls help me .

here my code :
#include <iostream>
#include<cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;
int precedence(char ch)
{
if(ch=='(') return 0;
else if(ch=='+' || ch=='-') return 1;
else if(ch=='*' || ch=='/' ) return 2;
return 3;
}
string infixToPostfix(char* infix)
{
stack<char> store;
string post;
int len=strlen(infix);
for(int i=0;i<len;i++)
{
char ch=infix;
if(isalnum(infix)) post.push_back(ch);
else if(ch=='(') store.push(ch);
else if(ch==')')
{
while(!store.empty())
{
ch=store.top();
store.pop();
if(ch=='(') break;
post.push_back(ch);
}
}
else if(ch=='+' || ch=='-' || ch=='/' ||ch=='*')
{
while(!store.empty() && (precedence(ch) <=precedence(store.top())))
{
post.push_back(store.top());
store.pop();
}
store.push(ch);
}
}
while(!store.empty())
{
post.push_back(store.top());
store.pop();
}
return post;

}

int main()
{
char infix[10000];
int test;
scanf("%d\n",&test);
while(test--)
{
int k=0;
char ch[10];
while(gets(ch))
{
if(strlen(ch)==0) break;
infix[k++]=ch[0];
}
infix[k]='\0';
cout<<infixToPostfix(infix)<<"\n";
if(test) printf("\n");
}

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 727 - Equation

Post by brianfry713 » Thu Aug 28, 2014 12:44 am

That is AC code.
Check input and AC output for thousands of problems on uDebug!

shaficse
New poster
Posts: 5
Joined: Sun Aug 17, 2014 8:20 pm

Re: 727 - Equation

Post by shaficse » Wed Sep 03, 2014 10:51 pm

Thank you, i have forgotten to print a blank line

Post Reply

Return to “Volume 7 (700-799)”