727 - Equation

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I m using ms VC 6, and your code returns wrong outputs. Make a file with the inputs and run your code.

And one important thing..

Code: Select all

``while(stack[k-1]!='(' && k>0)``
Now if k=0 then your code first checks stack[-1], then it checks k>0. Your code will try to access negative index. So, better to use

Code: Select all

``while(k>0 && stack[k-1]!='(')``
Hope these help.
Ami ekhono shopno dekhi...
HomePage

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

Code: Select all

``````
ACCEPTED
``````
Last edited by newton on Thu Jul 26, 2007 1:48 pm, edited 1 time in total.

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm
You are not checking for EOF. In fact the end of input is denoted by that. I had the same problem. Hope this helps.
Abhiram Natarajan.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
what's wrong with my code???
i'm getting WA

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <string>
#include <cctype>
#include <stack>

using namespace std;

int main()
{
stack<char> mystack;
string s;
char c[5];
int t;
cin >> t;
gets(c);
gets(c);
while (t--)
{
s = "";
while (!mystack.empty()) mystack.pop();
while (cin.getline(c, 5), c[0])
{
if (c[0] == '(')
{
mystack.push(c[0]);
continue;
}
if (isdigit(c[0]))
{
s += c[0];
continue;
}
if (c[0] == '+' || c[0] == '-')
{
if (!mystack.empty() && (mystack.top() == '*' || mystack.top() == '/'))
{
while(!mystack.empty() && mystack.top() != '(')
{
s += mystack.top();
mystack.pop();
}
mystack.push(c[0]);
} else mystack.push(c[0]);
continue;
}
if (c[0] == '*' || c[0] == '/')
{
mystack.push(c[0]);
continue;
}
if (c[0] == ')')
{
while(!mystack.empty() && mystack.top() != '(')
{
s += mystack.top();
mystack.pop();
}
if (!mystack.empty()) mystack.pop();
}
}
while(!mystack.empty())
{
s += mystack.top();
mystack.pop();
}
cout << s << endl;
}
}
``````

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
and another code with printf(), scanf()

Code: Select all

`````` #include <stdio.h>
#include <ctype.h>
#include <iostream>

using namespace std;

char a[100];
int i_a;

bool empty()
{
return i_a == -1;
}

void push(char c)
{
a[++i_a] = c;
}

void pop()
{
if (!empty()) i_a--;
}

char top()
{
if (!empty()) return a[i_a];
return 0;
}

void erase()
{
i_a = -1;
}

int size()
{
return i_a+1;
}

int main()
{
int t, l;
char c, s[5];
scanf("%d", &t);
getchar();
getchar();
for (l = 0; l < t; l++)
{
if (l) puts("");
erase();
while (1)
{
if (scanf("%c", &c) == EOF) break;
if (c == '\n') break;
getchar();
if (c == '(')
{
push(c);
continue;
}
if (isdigit(c))
{
putchar(c);
continue;
}
if (c == '+' || c == '-')
{
if (top() == '*' || top() == '/')
{
while (!empty() && top() != '(')
{
putchar(top());
pop();
}
push(c);
} else push(c);
continue;
}
if (c == '*' || c == '/')
{
push(c);
continue;
}
if (c == ')')
{
while (!empty() && top() != '(')
{
putchar(top());
pop();
}
if (!empty()) pop();
}
}
while (!empty())
{
putchar(top());
pop();
}
puts("");
}
return 0;
}

``````

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Check the io test here. You'll figure out whats wrong soon.
http://online-judge.uva.es/board/viewto ... hlight=727

(I did the same mistake )
----
Rio

kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka
PE!!!!! what to do?

Code: Select all

``````   deleted
``````
Last edited by kana on Wed Sep 12, 2007 8:38 pm, edited 1 time in total.

Sohel_Cuet
New poster
Posts: 4
Joined: Thu Nov 24, 2005 5:47 am
Contact:
Hi kana you should print a blank line between the output lines of two consecutive inputs.Here is an example for you.

Input :

Code: Select all

``````
2

2
+
3

3
*
4
``````
Output :

Code: Select all

``````23+

34*
``````
Hope it will work.Good Luck...
Keep dreaming.It costs nothing but makes you living

dgsquare
New poster
Posts: 1
Joined: Tue Sep 11, 2007 4:37 am
I also got WA, even I passed all of sample inputs.
Fortunately after I considered input format such as blank following character, I finally got AC.
How about checking input and output format again?

kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka
thanx Sohel

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

727-Equation[Runtime error]

I cannt findout where is the error in my code. Here is my code

Code: Select all

``````#include<stdio.h>
#include<string.h>

int taking_input(void);
void processing(void);
int pop(int);
void _calling(int);

struct x
{
char given_input[100000];
};
typedef struct x info;

char expression[100000], stack[100000];
info data[1000];

int taking_input(void)
{
int _cas;
char ch, str[10000],indexx=-1,n=-1;
scanf("%d%*c%*c",&_cas);
while( (ch = getchar()) != EOF )
{
if(ch == '\n')
{
str[++indexx] = NULL;
strcpy(data[++n].given_input,str);
indexx = -1;
}
else if(ch != '\n')
{
str[++indexx] = ch;
scanf("%*c");
}

}
if(n<_cas-1)
{
str[++indexx] = NULL;
strcpy(data[++n].given_input,str);
}
return _cas;
}

void _calling(int _cas)
{
int i;
for(i=0;i<_cas;i++)
{
strcpy(expression,data[i].given_input);
processing();
puts("");
}
}

void processing()
{
int i,top=-1;
for(i=0;expression[i];i++)
{
if(expression[i] >= '0' && expression[i] <= '9')
printf("%c",expression[i]);
else
{
if(expression[i] == '(')
stack[++top] = '(';
else if(expression[i] == ')')
{
while(stack[top] != '(')
{
printf("%c",stack[top--]);
}
top--;
}
else if(expression[i] == '*')
{
stack[++top]='*';
if((top - 1) > -1 && (stack[top - 1] == '/'))
{
top = pop(top);
stack[top] = '*';
}

}
else if(expression[i] == '/')
{
stack[++top]='/';
if((top - 1) > -1 && stack[top - 1] == '*')
{
top = pop(top);
stack[top] = '/';
}

}
else if(expression[i] == '+')
{
stack[++top]='+';
if((top - 1) > -1 && (stack[top - 1] == '-' || stack[top -1] == '*' || stack[top -1] == '/' || stack[top -1] == '+'))
{
top = pop(top);
stack[top] = '+';
}

}
else if(expression[i] == '-')
{
stack[++top]='-';
if((top - 1) > -1 && (stack[top - 1] == '+' || stack[top -1] == '*' || stack[top -1] == '/' || stack[top -1] == '-'))
{
top=pop(top);
stack[top] = '-';
}

}

}
}
while(top>-1)
{
printf("%c",stack[top--]);
}
}

int pop(int top)
{
printf("%c",stack[top - 1]);
top--;
}

int main()
{
//freopen("c:\\input.txt","r",stdin);
int _cas;
_cas = taking_input();
_calling(_cas);
return 0;
}

``````
No venture no gain

with best regards
------------------------
ishtiaq ahmed

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
To solve this problem, do recursive descent parsing, then just do dfs on the parse tree. Trying to do it with a stack is a source of trouble.

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 727 - Equation

why TLE....

Code: Select all

``CODE ACCEPTED``

Last edited by Ron on Fri May 23, 2008 2:09 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: 727 - Equation

Your code looks correct. I submitted it and got accepted.
Ami ekhono shopno dekhi...
HomePage

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 727 - Equation

To Jan ,
Thank U very much .!!!!!
I submitted it 3-4 times,and I was getting TLE.. .Now i accepted in 2.250...!!