727 - Equation

Moderator: Board moderators

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

727,uva problem

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 *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 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

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

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

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

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

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

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

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

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

AC

Thanks brianfry173

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

Re: 727 - Equation

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

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

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

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

Thank you, i have forgotten to print a blank line