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

Post Reply
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton »

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

Post by abhiramn »

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

Post by hamedv »

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

Post by hamedv »

and another code with printf(), scanf()
:cry:

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

Post by rio »

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

Post by kana »

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
Location: Bangladesh
Contact:

Post by Sohel_Cuet »

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... :D
Keep dreaming.It costs nothing but makes you living

dgsquare
New poster
Posts: 1
Joined: Tue Sep 11, 2007 4:37 am

Post by dgsquare »

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

Post by kana »

thanx Sohel :D

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

727-Equation[Runtime error]

Post by ishtiaq ahmed »

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--;
	return 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
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

Post by Ron »

why TLE....

Code: Select all

CODE ACCEPTED
Please help me.......

:(
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
Location: Dhaka, Bangladesh
Contact:

Re: 727 - Equation

Post by Jan »

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

Post by Ron »

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

Post Reply

Return to “Volume 7 (700-799)”