727 - Equation

[dumb dan]

Yes, 727 is a multiple input problem. And no, there could be (and probably is) more than one expression. Multiple input problems have a special form of input.

The fact that it is a multiple input problem is not specified in the problem specification, but rather in the problem list:

http://acm.uva.es/cgi-bin/OnlineJudge?Volume:7

Notice the blue icon to the left of the problem number. Different colored icons mean different things (see top of page for explaination). There's also a perfectly clear explaination of what multiple input means if you follow the link at the top of the page... read it!

http://acm.uva.es/problemset/minput.html

[Sedefcho]

Thanks, dumb dan.

Yes, I know what multiple input is. And I know that the Blue Icon
marks multiple input. It is just quite strange to me that the
Blue Icon in this case clearly contradicts to the problem
statement itself. That is why I asked the above questions.

Anyway, I will have in mind the Multiple Input
for Problem 727.

[captainsun]

I need critical input and output for this problem.
Anyone could help by giving some data...

Thank you.

[mamun]

After getting rid of RTE (due to multiple input, several months ago) now I am fighting against WA. I've gone through all the threads (14 I think) before this. My program passes all the samples given in the threads along with the special invalid ones. Now what?

Somebody please give me very special cases which only AC program can pass!

Thanks in advance.

[mamun]

No test cases ?

should I paste my code so that somebody can have a look?

[mamun]

Well, here is my code. Just to restate, even after passing all the samples in previous threads I'm getting WA. Please tell me where I went wrong.

Code: Select all

Deleted

[mamun]

Seems I am the only one reading this.
Didn't anybody find anything wrong with my code?

[mf]

Well, for at least this input your program produces wrong output:

Code: Select all

1

1
+
(
2
*
3
)
*
4

btw, shouldn't it be *much* easier to solve this problem with a recursive parser?
Complicated algorithms lead to more oppurtunities to make mistakes.

[mamun]

Thanks a lot mf. Your input was good enough for my problem. Just changing

Code: Select all

out[j++]=stack[--top];

to

Code: Select all

while(top)	out[j++]=stack[--top];

was enough.
Thanks once again.

[jack999]

i am solving problem 727 .
basically i m using microsoft environment i have write the following code
that produce the required result.
but when i submit it on acm give error i think it is filing problem
any body tell me how to solve the problem of filing
my code

Code: Select all

#include<stack>
#include<string>
#include<fstream>
#include<iostream>
using namespace std;
int priority(char value);
bool isOperator(char value);
void readFile(char * ptr);

string arr[6];
void main()
{
	//-----------------------------


string s="";

char temp;
	stack <char> ab;		
readFile("ab.txt");

cout<<endl;

	//-------------------------------------------
	string len1=arr[0];
	 int newlen=len1.length();
	char * ptrlen=0;
	ptrlen=new char[newlen+1];
	len1.copy(ptrlen,newlen,0);


 int noOfexp =atoi(ptrlen); 
 for(int j=1;j<=noOfexp; j++)
 {
	string exp=arr[j];
	for(int i=0;i<exp.length();i++)
	{
		char input=(char)exp[i];
		if(isOperator(input)==false)
			cout<<input;
		else
		{
			if(input=='(')
				ab.push(input);
			else if(input==')')
			{
				while(temp=ab.top()!='(')
				{
						
					cout<<ab.top();
					ab.pop();
					//cout<<temp;
				}
				ab.pop();
			}
			else if(ab.empty())
				ab.push(input);
			else if(priority(input)>priority(ab.top()))
				ab.push(input);
			else
			{
				while(ab.empty()!=true && priority(input)<priority(ab.top()))
				{
					cout<<ab.top();
					ab.pop();
					//cout<<temp;
					
				}
				ab.push(input);
			}
		}
	}
	while(ab.empty()==false)
			{
				cout<<ab.top();
				ab.pop();
			//	cout<<temp;
			}
			
		
		
	
	
	cout<<endl;

 }	
	
}
int priority(char value)
{
	switch(value)
	{
	case '+':
		return 1;
	case '-':
		return 1;
	case '*':
		return 2;
	case '/':
		return 2;
	default :
		return -1;
	}
}
bool isOperator(char value)
{
	switch(value)
	{
	case '+':
		return true;
	case '-':
		return true;
	case '*':
		return true;
	case '/':
		return true;
	case '(':
		return true;
	case ')':
		return true;
	default :
		return false;

	}
}

void  readFile(char* f1)
{
	
	ifstream inFile(f1);
if(!inFile)
cout<<"\n File Could not be opened:";
char ch1;

string s="";
int j=0;
while(inFile.get(ch1))
{
s+=ch1;


}


string s3="";
int len=s.length();
for(int k=0; k<len ;k++)
{
	if(s[k]=='\n' && k<len && s[k+1]=='\n')
		s3+=" ";
	else if(s[k]!='\n')
		s3+=s[k];
}
cout<<"s3 :"<<s3;
char * s4=0;
int len2=s3.length();
s4=new char[len2+1];
s3.copy(s4,len,0);
s4[len2]=0;

char* tokenPtr;
tokenPtr=strtok(s4," ");

int p=0;
while(tokenPtr!=NULL)
{
	arr[p++]=tokenPtr;
	tokenPtr=strtok(NULL," ");
}


}

[trulo17]

well, you are supossed to read from the standard input, or in other words, you don't need to open any file in order to solve a problem.

[IRA]

Why WA!?
I can't find my bug...
Please help me to find the bug.
Thanks in advance!

Code: Select all

#include <cstdio>
#include <cstdlib>

int stack[10000];
int top=-1;

int main()
{
	int num,i;
	char sen[100];
	char temp;

	gets(sen);
	num=atoi(sen);
	gets(sen);
	
	for(i=0;i<num;i++)
	{
		top=-1;
		while( gets(sen) )
		{
			if(sen[0]==0)
				break;

			if(sen[0]>='0'&&sen[0]<='9')
				printf("%s",sen);
			else if(sen[0]=='(')
				stack[++top]=sen[0];
			else if(sen[0]=='+'||sen[0]=='-')
			{
				temp=stack[top];

				if(temp=='*'||temp=='/')
				while(temp!='(')
				{
					printf("%c",temp);
					temp=stack[--top];
					if(top==-1)
						break;
				}

				stack[++top]=sen[0];
			}
			else if(sen[0]=='*'||sen[0]=='/')
			{
				temp=stack[top];

				if(temp=='*'||temp=='/')
				while(temp!='(')
				{
					printf("%c",temp);
					temp=stack[--top];
					if(top==-1)
						break;
				}
				stack[++top]=sen[0];
			}
			else if(sen[0]==')')
			{
				while( (temp=stack[top--])!='(' )
					printf("%c",temp);
			}
		}
		while(top!=-1)
			printf("%c",stack[top--]);
		printf("\n");
	}
	return 0;
}

[d31mOZ]

Each time i submit the next code, i get RTE, WHY??????

Code: Select all

#include <iostream.h>
#include <stdio.h>
//727

int Prioridad(char c, bool t)
{
        int prior;
        switch (c)
        {
                case ')':
                case '(': if (t) prior = 5; else prior = 1; break;
                case '+':
                case '-': prior = 2; break;
                case '*':
                case '/': prior = 3; break;
                case '^': prior = 4; break;
                default: prior = 0; break;
        }
        return prior;
}

int main()
{
        int n;
        cin >> n;
        char c, expresion[1000], pila[1000];
        int c_expresion, c_pila;
        for (int i = 0; i < n; i++)
        {
                c_pila = 0; c_expresion = 0;
                if (i == 0)
                {
                        c = getchar();
                        c = getchar();
                }
                while ((c = getchar()) && (c != '\n'))
                {
                        if (c == ')')
                        {
                                while (pila[c_pila - 1] != '(')
                                {
                                        expresion[c_expresion++] = pila[c_pila - 1];
                                        c_pila--;
                                }
                                c_pila--;
                                c = getchar();
                                continue;
                        }

                        if (Prioridad(c, true) == 0)
                        {
                                expresion[c_expresion++] = c;
                                c = getchar();
                                continue;
                        } else
                        {
                                for (;;)
                                {
                                        if (c_pila == 0)
                                        {
                                                pila[c_pila++] = c;
                                                c = getchar();
                                                break;
                                        }

                                        if (Prioridad(c,true) > Prioridad(pila[c_pila - 1], false))
                                        {
                                                pila[c_pila++] = c;
                                                c = getchar();
                                                break;
                                        } else
                                        {
                                                expresion[c_expresion++] = pila[c_pila - 1];
                                                c_pila--;
                                        }
                                }
                        }
                }
                if (c_pila > 0)
                        for (int i = c_pila - 1; i >= 0; i--)
                                expresion[c_expresion++] = pila[i];
                for (int i = 0; i < c_expresion; i++) cout << expresion[i];
                cout << endl;
        }
        return 0;
}

Greetings...

[Pasa Yildirim]

Hello everybody!

I'm stuck in 727. My program passes all sample inputs on the boards. And i dont know where is the problem. Can anybodu help me?

Code: Select all

#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

/// FILE* fi = freopen ("input.txt", "r", stdin);
/// FILE* fo = freopen ("output.txt", "w", stdout);

vector<char> o;
vector<char> result;

int main (void) 
{	
	int n; scanf ("%d\n\n", &n);
	char s[10];
	
	while (n--) {
		o.clear();
		result.clear();
		
		while (fgets (s, 10, stdin) && strcmp (s, "\n")) 
		{
			if (isdigit (s[0]))
				result.push_back (s[0]);
			else 
			{
				if (s[0] == ')') 
				{
					int l = o.size();
					for (int i = l - 1; o[i] != '('; i--) 
					{
						result.push_back (o[i]);
						o.pop_back ();
					}
					o.pop_back ();
				}
				else 
				{				
					int l = o.size();
					if (l) if (s[0] == '+' || s[0] == '-')
						for (int i = l - 1; i >= 0 && o[i] != '('; i--) 
						{
							result.push_back (o[i]);
							o.pop_back ();
						}			
					o.push_back (s[0]);
				}
			}
		}
		
		int l = o.size ();	
		if (l) for (int i = l - 1; i >= 0; i--) 
		{
			result.push_back (o[i]);
			o.pop_back ();
		}
		
		for (int i = 0; i < result.size(); i++) 
			printf ("%c", result[i]);
		printf ("\n\n");
	}
	
///	system ("pause");
	return 0;	
}

Thank you!

[ibgg_11]

I've another solution, this is better than the last (I know) please help me I can't find my error.

This is my new code:

#include <stdio.h>
#include <stack>
#include <stdlib.h>
#include <string.h>

using namespace std;

int esoperador(char car)
{
if (car == '*' || car == '/' || car == '+' || car == '-')
return 1;
else return 0;
}

int prioridad(char car)
{
if (car == '*' || car == '/') return 1;
else return 0;
}

int esoperando(char c)
{
if(c == '(' || c == ')' || c >= '0' && c <= '9') return 1;
else return 0;
}

void postfija(char car[])
{
stack <char> P;
char c;
int i=0;

if (strlen(car) == 0) return;
do
{
if (car == ' ')
{
i++;
continue;
}
if (car == '(')
{
P.push(car);
i++;
continue;
}

if (car == ')')
{
while (1)
{
c = P.top();
P.pop();
if (c == '(') break;
printf("%c", c);
}
i++;
continue;
}

if (esoperador(car))
{
if (P.empty() || prioridad(car) > prioridad(P.top()) || P.top() == '(')
{
P.push(car);
i++;
continue;
}
else
{
c = P.top();
P.pop();
printf("%c", c);
continue;
}
}
else
{
printf("%c", car);
i++;
continue;
}

}while (i < strlen(car));

while (!P.empty())
{
printf("%c", P.top());
P.pop();
}
}

main()
{
char cadena[200], c;
int i, j, casos;

scanf("%d\n", &casos);
for (i = 0; i < casos; ++i)
{
j = -1;
scanf("%c\n", &c);
while(1)
{
if(c == '\n') scanf("%c", &c);
if (c == '\n' || c == EOF) break;
cadena[++j] = c;
cadena[j+1] = 0;
if(scanf("%c", &c) < 0) break;
}

// for (j = 0; j < strlen(cadena); ++j)
// {
// if (!esoperador(cadena[j]) && !esoperando(cadena[j]))
// cadena[j] = ' ';
// }

// printf("strlen %d\n", strlen(cadena));
// printf("%d", j);
// printf("\ncadena = %s\n", cadena);
// printf("\nPostfija: ");
postfija(cadena);
printf("\n");
}
}