[vari] Contest 6 - Parsing

[Vincenzo1968]

Per riempire il buco lasciato da Gugo nella numerazione dei contest, propongo il seguente:

Problema 1:
Sia dato, in input, un array di stringhe; ogni stringa rappresenta un'espressione aritmetica.
Gli operatori validi sono: - (unario e binario), + (unario e binario), *, /, ^.
Quest'ultimo rappresenta l'operatore di elevamento a potenza:

2^3 si legge 2 elevato a 3.

Si produca, in output, un file di testo in cui ogni riga contiene l'espressione seguita dal segno di uguale seguito dal risultato.
Per esempio, se in input abbiamo la seguente espressione:

3 * (2.5 + 5)

in output avremo:

3 * (2.5 + 5) = 22.5

In caso di errori, dopo il segno di uguale, va riportata la descrizione dell'errore.
Per esempio:

3 * (2.5 + 5 = Errore: parentesi non bilanciate.

I file possono essere scaricati da QUI.

La prima riga del file contiene il numero di espressioni da valutare; le righe restanti contengono le espressioni(una per ogni riga).


Problema 2:
Sia dato, in input, un array di stringhe contenenti espressioni in formato RPN.
Fornire, in output, un file di testo che contenga le espressioni equivalenti(seguite dal segno di uguale e dal risultato) in notazione infissa.

Per esempio:

input: 3 5 * 4 +
output : 3 * 5 + 4 = 19


I file per il secondo problema possono essere scaricati da QUI

il file espressioni3.txt è quello piccolo; espressioni4.txt è quello grosso.

ATTENZIONE: nella notazione RPN, per distinguere il meno unario da quello binario, è necessario utilizzare due diversi simboli. Nei file suindicati, il simbolo ~ rappresenta il meno unario. Il meno binario è rappresentato dal simbolo usuale: -

[Vincenzo1968]

Questi i link ai contest precedenti:

Contest 1

Contest 2

Contest 3

Contest 4

Contest 5

Contest 7

[DanieleC88]

Bello, proviamo a lavorarci un po'.

[DanieleC88]

Il formato è libero? Numeri e simboli possono essere separati da un qualsiasi numero di spazi?

[Vincenzo1968]

Originariamente inviato da DanieleC88

Bello, proviamo a lavorarci un po'.

Grazie

Questi sono i miei tempi:

sul file piccolo:


sul file grosso:


La mia macchina:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3

Questa è la prima parte dei file di output:

file piccolo:


file grosso:



Il sorgente in C può essere scaricato da qui

Ne riporto solo una parte:

void Calcola(Array *pArray, char *szFileName)
{
	double dblResult;
	char szResult[1024] = "";
	char szError[256] = "";
	int k;
	FILE *fp;

	fp = fopen(szFileName, "w+");

	for (k = 0; k < pArray->size; k++)
	{
		nNextPos = 0;
		PreviousTokenType = EOL;
		sp_op = 0; 
		sp_val = 0;              

		dblResult = EvalInfix(pArray->m[k], szError);
		if ( szError[0] != '\0' )
			sprintf(szResult, "%s = %s\n", pArray->m[k], szError);
		else
			sprintf(szResult, "%s = %lf\n", pArray->m[k], dblResult);
		fwrite(szResult, strlen(szResult), 1, fp);
	}

	fclose(fp);
}

int main()
{
	Stati stato;
	Array myArray;
	char *szFileName = "espressioni1.txt";
	char *szFileNameOutput = "output1.txt";
	int k;
	clock_t c_start, c_end;

	c_start = clock();
	myArray.m = NULL;
	stato = DFA(szFileName, &myArray);
	c_end = clock();

	printf("\nTempo impiegato per il caricamento dei dati -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	if ( stato != S_ERROR )
		Calcola(&myArray, szFileNameOutput);

	if ( myArray.m != NULL )
	{
		for(k = 0; k < myArray.size; k++)
		{
			if ( myArray.m[k] != NULL )
				free(myArray.m[k]);
		}
		free(myArray.m);
	}
	c_end = clock();

	printf("\nTempo impiegato per il calcolo delle espressioni -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	return 0;
}

Ho utilizzato l'algoritmo conosciuto col nome di Operator Precedence Parsing.

P.S. Dimenticavo: se volete, potete utilizzare tools come Yacc/Bison o ANTLR.
Sono a disposizione per la spiegazione dell'algoritmo che ho utilizzato

[Vincenzo1968]

Originariamente inviato da DanieleC88

Il formato è libero? Numeri e simboli possono essere separati da un qualsiasi numero di spazi?

Si: gli spazi possono esserci come in:

5.8 + 3.9

oppure no come in:

5.8+3.9

[Vincenzo1968]

Originariamente inviato da DanieleC88

Il formato è libero? Numeri e simboli possono essere separati da un qualsiasi numero di spazi?

Le espressioni non contengono nomi di variabili. I token sono costituiti esclusivamente da numeri in virgola mobile, operatori e parentesi.

[wizard1993]

un dettaglio ma se seguo quello che mi hanno insegnato a scuola metà delle espressioni sono sbagliate: mi spiego
-8.5 + 49.96/(3 + -77.83/2)
è errata perchè ci sono due segni ( ... + -77.83....) in successione; a me a scuola quando scrivo una cosa del genere la prof fa un segno rosso e mette il cacolo sbagliato; quando usi quella notazione dte intendi dire questo?
( ... + (-77.83)....)

[Vincenzo1968]

Originariamente inviato da wizard1993

un dettaglio ma se seguo quello che mi hanno insegnato a scuola metà delle espressioni sono sbagliate: mi spiego
-8.5 + 49.96/(3 + -77.83/2)
è errata perchè ci sono due segni ( ... + -77.83....) in successione; a me a scuola quando scrivo una cosa del genere la prof fa un segno rosso e mette il cacolo sbagliato; quando usi quella notazione dte intendi dire questo?
( ... + (-77.83)....)

Prova a compilare queste righe in C:

	double dbl = -8.5 + 49.96/(3 + -77.83/2);
	printf("valore -> %lf\n", dbl);

vedrai che il compilatore non si lamenta

[wizard1993]

Originariamente inviato da Vincenzo1968

Prova a compilare queste righe in C:

	double dbl = -8.5 + 49.96/(3 + -77.83/2);
	printf("valore -> %lf\n", dbl);

vedrai che il compilatore non si lamenta

nemmeno il jdk di lamenta; era solo un dettaglio che mi sembrava giusto chiarire

[VICIUS]

Questi sono i tempi per il primo file, togliendo i vari output.

Macintosh:Desktop mirco$ time ruby contest6.rb 

real	0m3.078s
user	0m2.993s
sys	0m0.048s

13 righe di codice, 3 minuti per finire tutto

[Vincenzo1968]

Originariamente inviato da VICIUS

Questi sono i tempi per il primo file, togliendo i vari output.

Macintosh:Desktop mirco$ time ruby contest6.rb 

real	0m3.078s
user	0m2.993s
sys	0m0.048s

13 righe di codice, 3 minuti per finire tutto

E il codice? postalo

[Vincenzo1968]

Originariamente inviato da wizard1993

nemmeno il jdk di lamenta; era solo un dettaglio che mi sembrava giusto chiarire

Giustissimo

[VICIUS]

Originariamente inviato da Vincenzo1968

E il codice? postalo

Appena faccio andare anche il secondo file. Sto avendo problemi con alcuni caratteri utf8 che sembrano essere in mezzo alle espressioni.

[Vincenzo1968]

Originariamente inviato da VICIUS

Appena faccio andare anche il secondo file. Sto avendo problemi con alcuni caratteri utf8 che sembrano essere in mezzo alle espressioni.

Strano

Questo è il codice che ho usato per creare i due file:

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

#define BUFFER_SIZE 4096

char *expr[] = {
	"n + (n - n)/n^(1/2)",
	"n / n^0.5",
	"(n - n) + (n * 2)/(n - n)",
	"(n + n/(n+n)) - n * n/2",
	"n + (n^4^0.5 - n)",
	"(n * n/(1 + n) - 5) / (-4.3 + n^(1/2))",
	"-8.5 + n/(3 + n/2)",
	"-5.21 * n*(-8 + n*(n/(2+n^0.5)))",
	"((n * n/(1 + n) - 8.3) / (-4.3 + n^(1/2)))/(-21.8 * n*(-5 + n*(n/(2+n^0.5))))",
	"((n + n/(n+n)) - n * n/2)*(n / n^0.5)",
	"(n + (n^4^0.5 - n)) - ((n * n/(1 + n) - 5) / (-4.3 + n^(1/2))))"
};

int RangedRand(int range_min, int range_max)
{
	// Generate random numbers in the half-closed interval
	// [range_min, range_max). In other words:
	// range_min <= random number < range_max
	return ((double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min);
	//printf( "  %6d\n", u);
}

void CreaFile()
{
	FILE *fp;
	int i, j, k, x;
	int n;
	char szNum[256];
	int p1, p2;
	float f;
	int len1, len2;
	char szExpr[256];
	int numlines = 200000;

	fp = fopen("espressioni2.txt", "w+");
	
	sprintf(szExpr, "%d\n", numlines);
	fwrite(szExpr, strlen(szExpr), 1, fp);

	for ( i = 0; i < numlines; i++ )
	{
		j = RangedRand(0, 11);
		len1 = strlen(expr[j]);
		k = 0;
		for(n = 0; n < len1; n++)
		{
			if ( expr[j][n] != 'n' )
			{
				szExpr[k++] = expr[j][n];
			}
			else
			{
				p1 = RangedRand(-100, 100);
				p2 = RangedRand(0, 100);
				if ( p2 < 10 )
					f = p1 + (float)p2/10;
				else
					f = p1 + (float)p2/100;
				sprintf(szNum, "%3.2f", f);
				len2 = strlen(szNum);
				if ( szNum[len2 - 1] == '0' )
					szNum[len2 - 1] = '1';
				for(x = 0; x < len2; x++)
					szExpr[k++] = szNum[x];
			}
			szExpr[k] = '\0';
		}
		fwrite(szExpr, strlen(szExpr), 1, fp);
		fwrite("\n", 1, 1, fp);
		//printf("record n. %d\n", i);
	}

	fclose(fp);
}

int main()
{
	srand((unsigned)time(NULL));

	CreaFile();

	return 0;
}

[Vincenzo1968]

Ho aperto il file con Notepad++ e mi dice che il file è in formato Windows/Ansi:

[VICIUS]

La riga che dava fastidio era la 6. Più precisamente quello strano carattere a doppia S che ruby sembrava non capire essere utf8.

(-49.63 + (39.21^4^0.5 § 87.29)) - ((-93.21 * 84.57/(1 + -85.75) - 5) / (-4.3 + -64.86^(1/2))))

Ho dovuto paciugare un po' con iconv per sistemare la codifica ed ora funziona tutto.

I tempi per il secondo file sono:

Macintosh:Desktop mirco$ time ruby contest6.rb 

real	0m6.174s
user	0m6.008s
sys	0m0.102s

Il codice è:

File.open('prova.txt', 'r') do |file|
  file.gets # ignora la prima riga
  while expression = file.gets
    begin
      result = eval(expression.chop!.gsub('^', '**'))
      puts "#{expression} = #{result}"
    rescue ZeroDivisionError
      puts "#{expression} : Divisione per zero"
    rescue SyntaxError
      puts "#{expression} : Errore di sintassi nella espressione"
    end
  end
end

[Vincenzo1968]

Originariamente inviato da VICIUS

La riga che dava fastidio era la 6. Più precisamente quello strano carattere a doppia S che ruby sembrava non capire essere utf8.

(-49.63 + (39.21^4^0.5 § 87.29)) - ((-93.21 * 84.57/(1 + -85.75) - 5) / (-4.3 + -64.86^(1/2))))

Ho dovuto paciugare un po' con iconv per sistemare la codifica ed ora funziona tutto.

I tempi per il secondo file sono:

Macintosh:Desktop mirco$ time ruby contest6.rb 

real	0m6.174s
user	0m6.008s
sys	0m0.102s

Il codice è:

File.open('prova.txt', 'r') do |file|
  file.gets # ignora la prima riga
  while expression = file.gets
    begin
      result = eval(expression.chop!.gsub('^', '**'))
      puts "#{expression} = #{result}"
    rescue ZeroDivisionError
      puts "#{expression} : Divisione per zero"
    rescue SyntaxError
      puts "#{expression} : Errore di sintassi nella espressione"
    end
  end
end

Ok,

in questi casi il risultato dell'espressione dev'essere: Errore: operatore non riconosciuto(l'ho inserito a mano dopo aver creato il codice con il sorgente che ho postato sopra )

Posta i dati relativi alla tua macchina

[Vincenzo1968]

Vicius scusa,

ma l'output viene scritto su file o a video? (sai che non me ne intendo di ruby )

Per il calcolo dei tempi devono essere esclusi i tempi di caricamento dell'array di stringhe dal file, ma debbono essere inclusi i tempi di scrittura sul file di output.

[VICIUS]

Sto su un core2 2.4ghz, 2gb di ram.