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

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by 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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by 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
New poster
Posts: 1
Joined: Wed Jul 06, 2005 12:18 pm
Location: Dhaka, Bangladesh.
Contact:

Please give me some critical input and output for 727

Post by captainsun »

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

Thank you.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

727 Still WA

Post by 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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

No test cases ? :o

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by 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
Last edited by mamun on Fri Dec 09, 2005 8:27 pm, edited 1 time in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by 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. :D

jack999
New poster
Posts: 1
Joined: Tue Jan 03, 2006 4:45 pm

727

Post by 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
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by 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
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

727 WA

Post by 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
New poster
Posts: 7
Joined: Sat Apr 01, 2006 8:00 pm

727 --> why RTE?

Post by 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
New poster
Posts: 14
Joined: Mon Mar 07, 2005 7:10 pm
Location: Bosnia and Herzegovina
Contact:

727 -- Equation Problems (WA)

Post by 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
New poster
Posts: 1
Joined: Sat Jul 08, 2006 8:31 am

727

Post by 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");
}
}
< Israel ><

Post Reply

Return to “Volume 7 (700-799)”