727 - Equation

[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.

[newton]

Code: Select all

ACCEPTED

[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]

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]

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]

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]

PE!!!!! what to do?

Code: Select all

   deleted

[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...

[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]

thanx Sohel

[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;
}

[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]

why TLE....

Code: Select all

CODE ACCEPTED

Please help me.......

[Jan]

Your code looks correct. I submitted it and got accepted.

[Ron]

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