[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 (http://www.guidealgoritmi.it/public/espressioni.zip).

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 (http://it.wikipedia.org/wiki/Reverse_Polish_notation).
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 (http://www.guidealgoritmi.it/public/espressioni2.zip)

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 (http://www.hwupgrade.it/forum/showthread.php?t=1784948)

Contest 2 (http://www.hwupgrade.it/forum/showthread.php?t=1785752)

Contest 3 (http://www.hwupgrade.it/forum/showthread.php?t=1787500)

Contest 4 (http://www.hwupgrade.it/forum/showthread.php?t=1791293)

Contest 5 (http://www.hwupgrade.it/forum/showthread.php?t=1799059)

Contest 7 (http://www.hwupgrade.it/forum/showthread.php?t=1839674)

;)

[DanieleC88]

Bello, proviamo a lavorarci un po'.

[DanieleC88]

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

[Vincenzo1968]

Bello, proviamo a lavorarci un po'.

Grazie ;)

Questi sono i miei tempi:

sul file piccolo:
http://www.guidealgoritmi.it/images/ImgForums/Contest06Tempi1.jpg

sul file grosso:
http://www.guidealgoritmi.it/images/ImgForums/Contest06Tempi2.jpg

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:
http://www.guidealgoritmi.it/images/ImgForums/Contest06Output1.jpg

file grosso:
http://www.guidealgoritmi.it/images/ImgForums/Contest06Output2.jpg


Il sorgente in C può essere scaricato da qui (http://www.guidealgoritmi.it/public/EvalExpression.zip)

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]

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]

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]

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]

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 :p

[Vincenzo1968]

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 :p

E il codice? postalo ;)

[Vincenzo1968]

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

Giustissimo ;)

[VICIUS]

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]

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

Strano :confused:

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:

http://www.guidealgoritmi.it/images/ImgForums/Contest06FormatoFile.jpg

:confused:

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

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.

[VICIUS]

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.
Per ora sputa tutto su video ma basta ridirigere l'output se vuoi mandarlo su file. I tempi li presi senza output, semplicemente commentando i puts.

[Vincenzo1968]

Vicius,

c'è un errore di calcolo in qualche riga. Per esempio, all'ottava riga del file piccolo, l'espressione:

45.26 + (5.83 - 79.35)/51.68^(1/2)

dà come risultato -28.26

Il risultato è, invece, 35.033094

Puoi verificarlo con il seguente codice C:

//double dbl = 45.26 + (5.83 - 79.35)/pow(51.68, (1/2)); // = -28.26
double dbl = 45.26 + (5.83 - 79.35)/pow(51.68, (double)1/2); // = 35.033094
//double dbl = 45.26 + (5.83 - 79.35)/pow(51.68, 0.5); // = 35.033094
printf("valore -> %lf\n", dbl);

[||ElChE||88]

Ciao,
potresti postare i risultati del primo file che vorrei confrontarli coi miei?

Grazie! :D

[Vincenzo1968]

Ciao,
potresti postare i risultati del primo file che vorrei confrontarli coi miei?

Grazie! :D

Ciao Elche,

i due file di output li puoi scaricare da qui (http://www.guidealgoritmi.it/public/Contest06Output.zip).

output1.txt è quello del file piccolo; output2.txt, quello del file grosso.

[||ElChE||88]

Ciao Elche,

i due file di output li puoi scaricare da qui (http://www.guidealgoritmi.it/public/Contest06Output.zip).

output1.txt è quello del file piccolo; output2.txt, quello del file grosso.
Grazie mille!
Ad occhio e croce sembrano uguali, ora lo aggiusto un po' e poi lo posto.
Ovviamente è moolto più lento del tuo. :asd:

[Vincenzo1968]

Ricordo che agiamo nel campo dei numeri reali e, dunque, il risultato di un'espressione(e di ogni sottoespressione) deve essere un numero reale.

Per esempio, la seguente espressione:

1 / 2

deve restituire 0.5 come risultato e NON 0.
Non bisogna cioè seguire la convenzione dei compilatori che, se i due operandi sono di tipo intero, arrotondano il risultato.

[||ElChE||88]

Io ho usato direttamente double per tutto. :fagiano:

[VICIUS]

Vicius,

c'è un errore di calcolo in qualche riga. Per esempio, all'ottava riga del file piccolo, l'espressione:

45.26 + (5.83 - 79.35)/51.68^(1/2)

dà come risultato -28.26

1/2 è una divisione intera in ruby quindi da 0 resto 1. 51.68 elevato alla 0 da 1 e da questo si ottiene lo strano risultato. Forse con una regex riesco ad aggiungere un .0 ai numeri giusti per portarla in R.

[VICIUS]

1/2 è una divisione intera in ruby quindi da 0 resto 1. 51.68 elevato alla 0 da 1 e da questo si ottiene lo strano risultato. Forse con una regex riesco ad aggiungere un .0 ai numeri giusti per portarla in R.
Mi sono scorso un po' il file è questo 1/2 sembra l'unica divisione intera così ho imbrogliato un pochino. :)

Questa versione da risultati corretti
File.open('espressioni1.txt', 'r') do |file|
file.gets # ignora la prima riga
while expression = file.gets
begin
result = eval(expression.chop!.gsub('(1/2)','(1.0/2.0)').gsub('^', '**'))
puts "#{expression} = #{result}"
rescue ZeroDivisionError
puts "#{expression} : Divisione per zero"
rescue SyntaxError
puts "#{expression} : Errore di sintassi nella espressione"
end
end
end

[||ElChE||88]

http://img29.picoodle.com/img/img29/3/10/26/f_Untitled1m_e1525b0.jpg

Ecco il codice (è ancora da ottimizzare un pochino / rendere più leggibile):

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Contest._06
{
class Program
{
static Dictionary<char, int> operators = new Dictionary<char, int>() { { '+', 0 }, { '-', 0 }, { '*', 1 }, { '/', 1 }, { '^', 2 }, { '(', 3 }, { ')', 3 } };

static void Main(string[] args)
{
DateTime start, end;
string file = args.Length == 0 ? @"C:\Users\FX.Net\Desktop\c6\espressioni1.txt" : args[0];
List<string> lines = new List<string>();

start = DateTime.Now;

using (StreamReader sr = new StreamReader(file))
{
int count = int.Parse(sr.ReadLine());

for (int i = 0; i < count; i++)
{
lines.Add(sr.ReadLine());
}
}

end = DateTime.Now;
Console.WriteLine("Read time: " + (end - start).TotalMilliseconds + "ms.");

start = DateTime.Now;

using (StreamWriter sw = new StreamWriter(file + "-output.txt"))
{
foreach (string line in lines)
{
sw.Write(line + " = ");

try
{
sw.WriteLine(Eval(line));
}
catch (Exception e)
{
sw.WriteLine("ERROR: " + e.Message);
}
}
}

end = DateTime.Now;
Console.WriteLine("Parse time: " + (end - start).TotalMilliseconds + "ms.");
}

static double Eval(string line)
{
char c;
bool op = true;
bool negate = false;
Stack<double> valStack = new Stack<double>();
Stack<char> opStack = new Stack<char>();

for (int i = 0; i < line.Length; i++)
{
c = line[i];

if (c == ' ' || c == '\t')
{
continue;
}
else if (negate && (c < 48 || c > 57))
{
throw new Exception("Malformed expression");
}
else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^')
{
if (c == '+' && op)
{
continue;
}
else if (c == '-' && op)
{
negate = true;
continue;
}

while (opStack.Count != 0 && opStack.Peek() != '(' && operators[opStack.Peek()] >= operators[c])
{
if (valStack.Count <= 1)
throw new Exception("Malformed expression");

valStack.Push(Calc(opStack.Pop(), valStack.Pop(), valStack.Pop()));
}

opStack.Push(c);
op = true;
}
else if ((c >= 48 && c <= 57) || c == '.')
{
string num = "";

while (i < line.Length && ((line[i] >= 48 && line[i] <= 57) || line[i] == '.'))
{
num += line[i];
i++;
}

i--;

if (negate)
{
num = '-' + num;
negate = false;
}

valStack.Push(double.Parse(num));
op = false;
}
else if (c == '(')
{
opStack.Push(c);
op = true;
}
else if (c == ')')
{
while (opStack.Count != 0 && opStack.Peek() != '(')
{
if (valStack.Count <= 1)
throw new Exception("Malformed expression");

valStack.Push(Calc(opStack.Pop(), valStack.Pop(), valStack.Pop()));
}

if (opStack.Count == 0)
{
throw new Exception("Unbalanced parentheses");
}

opStack.Pop();
op = false;
}
else
{
throw new Exception("Unknown symbol: " + c);
}
}

while (opStack.Count != 0)
valStack.Push(Calc(opStack.Pop(), valStack.Pop(), valStack.Pop()));

if (valStack.Count != 1)
throw new Exception("Malformed expression");

return valStack.Pop();
}

static double Calc(char op, double val1, double val2)
{
switch (op)
{
case '+':
{
return val2 + val1;
}
case '-':
{
return val2 - val1;
}
case '*':
{
return val2 * val1;
}
case '/':
{
if (val1 == 0)
throw new Exception("Divide by 0");

return val2 / val1;
}
case '^':
{
if (val2 < 0)
return -Math.Pow(-val2, val1);
else
return Math.Pow(val2, val1);
}
}

throw new Exception("Malformed expression");
}
}
}

[magix2003]

Si può togliere la prima riga del file?

Perché così si potrebbe fare un bel parser...

[shinya]

Si può togliere la prima riga del file?

Perché così si potrebbe fare un bel parser...

Perchè non lo puoi fare con la prima riga?
La soluzione del contest è un parser a discesa ricorsiva bello e buono. E semplice per di più, perchè non ci sono variabili.

Sinceramente non capisco cosa ci sia da misurare. La soluzione è standard.

[shinya]

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

Eval!! Ma questo è barare! :P

Vincenzo, nei file di input ogni tanto metti anche qualcosa tipo 'rm -rf /'... :P

(sto scherzando...)

[VICIUS]

Eval!! Ma questo è barare! :P
È il risultato che conta. :fiufiu:

[gugoXX]

Perchè non lo puoi fare con la prima riga?
La soluzione del contest è un parser a discesa ricorsiva bello e buono. E semplice per di più, perchè non ci sono variabili.

Sinceramente non capisco cosa ci sia da misurare. La soluzione è standard.

Eh no :D
Io ho saltato direttamente la soluzione classica, ovvero il parser vecchio stile con la costruzione dell'albero di comandi, perche' e' ilclassico esempio che facevano per insegnare il C++ e non ne avevo piu' voglia.
Quindi ho scritto la versione che compila direttamente una stringa in C#, usando il compilatore on-the-fly. Ci sono riuscito con il compilatore C#, ma
non ancora con quello Javascript (che sembrerebbe essere piu' otimizzato), a causa dell'elevamento a potenza.
Ma tanto ho lasciato perdere per noia, anche questa e' una soluzione abbastanza classica e non mi soddisfaceva.

Quindi ho intrapreso le strade simpatiche, per le quali voglio almeno il premio originalita' (non sicuramente velocita')

1. La prima e' istanziare un WebClient e passare la stringa a google. Google calcola il risultato, me lo sputa indietro e parso il risultato con un paio di RegEx.
Testato, funziona.
Putroppo dopo 30 richieste viene bannato temporaneamente l'IP.
e le performance ovviamente sono pietose, ma e' divertente e veloce da scrivere.

2. La seconda e' quella di fare pesante uso della messaggistica del SO.
Parte aprendo una calcolatrice di Windows, prende il processo.
Spedisco i caratteri simulando la pressione dei tasti della tastiera (KeySend)
E leggo i risultato sempre simulando la combinazione CTRL+C
A questo punto mi trovo il risultato nella clipboard, e di nuovo con C# me lo prendo e lo uso.
Mediante le Interop agisco portando quando mi serve la calcolatrice in front.

Ho ancora un problemino con l'elevamento a potenza
All'inizio la rendo "Scientfica" con ALT+V+S, cosi' mi appare.
Resta pero' che la funzione elevamento non ho trovato come farla, dato che non sembra essere legata ad un tasto particolare.
Stasera quindi aggiungo la simulazione di click sinistro del mouse... cosa che alla peggio faccio di nuovo con le Interop.
(Performance attese, pietose, ma almeno e' divertente)


Stasera posto tutti i codici se siete interessati.
Aloha..

[DanieleC88]

È il risultato che conta. :fiufiu:
Vabbe' ma così so' buoni tutti... :Prrr:

[shinya]

Quindi ho intrapreso le strade simpatiche, per le quali voglio almeno il premio originalita' (non sicuramente velocita')

1. La prima e' istanziare un WebClient e passare la stringa a google. [...]
2. La seconda e' quella di fare pesante uso della messaggistica del SO.
Parte aprendo una calcolatrice di Windows, prende il processo. [...]

Oggesù! Benvenuti a Twin Peaks!

[VICIUS]

1. La prima e' istanziare un WebClient e passare la stringa a google. Google calcola il risultato, me lo sputa indietro e parso il risultato con un paio di RegEx.
Testato, funziona.
Putroppo dopo 30 richieste viene bannato temporaneamente l'IP.
e le performance ovviamente sono pietose, ma e' divertente e veloce da scrivere.

Questa di google è geniale! Voglio il codice per provarlo a casa. :O

[VICIUS]

Vabbe' ma così so' buoni tutti... :Prrr:
Dov'è il tu codice? Ancora in vim che litighi con qualche puntatore? :asd:

[DanieleC88]

Poco lo spiritoso, ho Code::Blocks che lavora e i puntatori li sto gestendo bene, finora. Però effettivamente ho deciso di farmi male provandolo a fare in C da zero... :asd:

[Vincenzo1968]

Eccomi.

Questa mattina mi sono perso. Capita, in Sicilia, che si imbocchi una strada e si finisca in... aperta campagna. Dovevo andare da un cliente in un paesino dell'entroterra. A un bivio, ho scelto a caso una delle due vie e, dopo circa tre km, mi sono ritrovato tra gli alberi di ulivo. La strada si interrompeva così, bruscamente, senza un cartello di avviso, senza dire né ai ne bai, né scù né passiddà.

x Vicius: no, così è davvero troppo facile. Sto preparando degli altri file e, sempre nell'ambito del parsing di espressioni aritmetiche, un secondo problema da risolvere; problema che non consentirà l'uso di funzioni 'preconfezionate' :Perfido:

x Gugo: Soluzioni interessanti: posta senz'altro il codice. Ma vedi quanto già detto a Vicius.

x Magix: Se ti è comodo togli pure la prima riga. L'importante è che venga prodotto in output un file così come specificato nel post iniziale.

x tutti: Fra un po' posto la spiegazione dell'algoritmo che ho utilizzato. Invito Elche e tutti gli altri a fare lo stesso. Sto provando anche a implementare la tecnica del parsing a discesa ricorsiva, prendendo spunto dall'esempio in C++ del sesto capitolo del libro di Stroustrup.

[Vincenzo1968]

Eval!! Ma questo è barare! :P

Vincenzo, nei file di input ogni tanto metti anche qualcosa tipo 'rm -rf /'... :P

(sto scherzando...)

Ciao Shinya,

io invece non scherzo affatto :Perfido: Sto preparando qualcosa di più complicato ;)

[Vincenzo1968]

La spiegazione dell'algoritmo(praticamente ho fatto copia e incolla da un articolo sul mio sito (http://www.guidealgoritmi.it/ShowArticle.aspx?ID=3)):


Nel calcolare il risultato di un'espressione, dobbiamo tenere conto della precedenza e dell'associatività degli operatori. Vediamo qualche esempio. Nella seguente espressione:

3 + 5 * 8

l'operatore di moltiplicazione ha la precedenza rispetto all'operatore di addizione. Dunque, calcoliamo prima 5 * 8 e al risultato aggiungiamo 3. Possiamo modificare la precedenza grazie all'uso delle parentesi:

(3 + 5) * 8

in questo caso, il risultato corretto si ottiene calcolando 3 + 5 e moltiplicando il valore ottenuto per 8.

Consideriamo l'associatività:

21 + 8 + 5 = 34

nell'espressione precedente possiamo indifferentemente:
1) calcolare prima 21 + 8 e al risultato aggiungere 5;
2) calcolare prima 8 + 5 e al risultato aggiungere 21.

Consideriamo quest'altra espressione:

21 - 8 - 5 = 8

il risultato corretto si ottiene calcolando prima 21 - 8 e sottraendo dal risultato 5. Non possiamo calcolare prima 8 - 5 = 3 e poi 21 - 3 = 18. L'operatore "-" associa da sinistra e dunque prima si calcola l'espressione più a sinistra e poi quella più a destra.

Un esempio di associatività a destra è dato dall'operatore di elevamento a potenza(che indichiamo col simbolo "^":

2^3^3 = 134.217.728 (calcoliamo prima 3^3 = 27 e poi 2^27 = 134.217.728).

Anche in questo caso possiamo cambiare la precedenza delle operazioni con l'uso delle parentesi:

(2^3)^3 = 512.

Le regole che abbiamo esaminato sono facili da applicare per un essere umano perchè si ha la visione completa dell'intera espressione. Considerando la cosa dal punto di vista di un parser, la faccenda si complica. Effettuando il parsing di uno stream di caratteri, leggiamo quest'ultimo un carattere alla volta, da sinistra verso destra.

Per esempio, consideriamo l'espressione:

3 + 2 * 8.

Quando un parser legge la sottoespressione 3 + 2, non può sapere se deve calcolare subito il risultato o se, andando avanti, incontrerà un operatore che ha maggiore precedenza.


L'algoritmo

Il problema può essere risolto utilizzando due stack, uno per gli operatori e uno per gli operandi, e una tabella di precedenza degli operatori.
Si procede come segue:

Passo 1) Si legge la stringa di input da sinistra verso destra.

Passo 2) Ogni operando incontrato si inserisce nello stack degli operandi (facciamo un'operazione di shift).

Passo 3) Se, nella stringa di input, incontriamo un operatore, usiamo lo stack degli operatori nel seguente modo:
- 3.A Se l'operatore in cima allo stack ha una precedenza minore rispetto a quello corrente(quello, cioè, che abbiamo appena letto dalla stringa di input), inseriamo l'operatore corrente in cima allo stack.
- 3.B Se, invece, l'operatore in cima allo stack ha una precedenza maggiore o uguale, eseguiamo un'azione di reduce, e cioè:
Estraiamo l'operatore dallo stack degli operatori; estraiamo due operandi(o uno solo, a seconda se l'operatore è binario o unario) dallo stack degli operandi; calcoliamo il risultato e lo inseriamo in cima allo stack. Inseriamo l'operatore corrente in cima allo stack degli operatori. Se l'operatore è binario, il primo operando prelevato dallo stack è l'operando destro; il secondo è l'operando sinistro. Per l'addizione e la moltiplicazione, l'ordine non è importante: 2 * 3 = 3 * 2. Per la sottrazione e la divisione, invece si: 2 / 3 è diverso da 3 / 2.

Passo 4) Se, nella stringa di input, incontriamo una parentesi di apertura, la inseriamo in cima allo stack degli operatori. Se incontriamo una parentesi di chiusura, estraiamo tutti gli operatori dallo stack fino a quando non incontriamo una parentesi di apertura. Per ogni operatore estratto, estraiamo due operandi, calcoliamo il risultato e lo inseriamo in cima allo stack degli operandi. Le due parentesi vengono scartate.

Passo 5) Infine, quando raggiungiamo la fine della stringa di input, estraiamo tutti gli operatori e, per ogni operatore estratto, effettuiamo le seguenti operazioni: estraiamo uno o due operandi(a seconda se l'operatore è unario o binario), calcoliamo il risultato e lo inseriamo in cima allo stack degli operandi. Quando lo stack degli operatori è vuoto(la cima contiene il simbolo EOL), nello stack degli operandi dovrebbe trovarsi un solo valore che costituisce il risultato dell'espressione.

Esempio 1

Consideriamo l'espressione 5 + 3 * 8.

Inizialmente i due stack sono vuoti:

OPERATOR STACK : EOL
OPERAND STACK : EOL

Leggendo il primo token dalla stringa di input, vediamo che si tratta di un operando e lo inseriamo, dunque, nello stack degli operandi:

OPERATOR STACK : EOL
OPERAND STACK : EOL 5

Il secondo token letto è un operatore, "+". Poichè la cima dello stack degli operatori contiene il marcatore di fine input (EOL = END OF LINE) inseriamo l'operatore in cima allo stack:

OPERATOR STACK : EOL +
OPERAND STACK : EOL 5

Il terzo token è un operando; lo inseriamo in cima allo stack:

OPERATOR STACK : EOL +
OPERAND STACK : EOL 5 3

Il token successivo, nella stringa di input, è un operatore, "*". L'operatore in cima allo stack degli operatori, "+", ha precedenza minore rispetto a quello corrente, "*". E, dunque, inseriamo l'operatore corrente in cima allo stack:

OPERATOR STACK : EOL + *
OPERAND STACK : EOL 5 3

Il quinto token è un operando. Lo inseriamo in cima allo stack:

OPERATOR STACK : EOL + *
OPERAND STACK : EOL 5 3 8

A questo punto abbiamo raggiunto la fine della stringa di input e dunque, eseguiamo il passo 5:

Preleviamo il primo operatore dalla cima dello stack, "*"; poichè si tratta di un operatore binario, preleviamo due operandi dallo stack, i valori 8 e 3. Il primo valore prelevato, 8, è l'operando destro, il secondo, 3, è l'operando sinistro. Eseguiamo l'operazione, 3 * 8 e il risultato, 24, lo inseriamo in cima allo stack:

OPERATOR STACK : EOL +
OPERAND STACK : EOL 5 24

proseguiamo prelevando un altro operatore dalla cima dello stack, "+"; preleviamo due operandi, 24 e 5, calcoliamo il risultato, 5 + 24 e lo piazziamo in cima allo stack:

OPERATOR STACK : EOL
OPERAND STACK : EOL 29

Lo stack degli operatori è adesso vuoto(la sua cima contiene il simbolo EOL) e l'unico operando in cima allo stack degli operandi, 29, è il risultato dell'espressione 5 + 3 * 8.

Esempio 2

Consideriamo l'espressione -4 + 10/(2 + 3).

All'inizio i due stack sono vuoti:

OPERATOR STACK : EOL
OPERAND STACK : EOL

Il primo token che incontriamo è un operatore, il meno unario. Lo inseriamo in cima allo stack:

OPERATOR STACK : EOL -
OPERAND STACK : EOL

Il secondo token, un operando, va in cima allo stack relativo:

OPERATOR STACK : EOL -
OPERAND STACK : EOL 4

Il terzo token è l'operatore "+". Poiché l'operatore in cima allo stack ha precedenza maggiore rispetto a quello corrente, preleviamo l'operatore dallo stack, preleviamo un solo operando dallo stack degli operandi(perchè si tratta di un operatore unario), calcoliamo il risultato e lo inseriamo in cima allo stack degli operandi. L'operatore corrente va inserito in cima allo stack degli operatori:

OPERATOR STACK : EOL +
OPERAND STACK : EOL -4

I due token successivi, l'operando 10 e l'operatore "/", vanno entrambi inseriti in cima ai relativi stack:

OPERATOR STACK : EOL +
OPERAND STACK : EOL -4 10

OPERATOR STACK : EOL + /
OPERAND STACK : EOL -4 10

La parentesi di apertura va in cima allo stack degli operatori:

OPERATOR STACK : EOL + / (
OPERAND STACK : EOL -4 10

Anche i token 2, "+" e 3 vanno inseriti in cima allo stack:

OPERATOR STACK : EOL + / (
OPERAND STACK : EOL -4 10 2

OPERATOR STACK : EOL + / ( +
OPERAND STACK : EOL -4 10 2

OPERATOR STACK : EOL + / ( +
OPERAND STACK : EOL -4 10 2 3

Incontrando la parentesi di chiusura, preleviamo tutti gli operatori dallo stack e i relativi operandi, finchè non incontriamo la parentesi di apertura.
Il primo operatore in cima allo stack è binario, "+"; quindi preleviamo due operandi, 3 e 2, eseguiamo l'operazione, 2+3, e il risultato, 5, lo inseriamo in cima allo stack degli operandi:

OPERATOR STACK : EOL + / (
OPERAND STACK : EOL -4 10 5

La cima dello stack degli operatori, contiene adesso la parentasi di apertura. La preleviamo dallo stack e la scartiamo insieme a quella di chiusura:

OPERATOR STACK : EOL + /
OPERAND STACK : EOL -4 10 5

Avendo raggiunto la fine della stringa di input, applichiamo il passo 5. Preleviamo l'operatore in cima allo stack e gli operandi necessari. Calcoliamo il risultato (10/5 = 2) e lo inseriamo in cima allo stack degli operandi:

OPERATOR STACK : EOL +
OPERAND STACK : EOL -4 2

Passo finale: -4 + 2 = -2

OPERATOR STACK : EOL
OPERAND STACK : EOL -2

Adesso lo stack degli operatori è vuoto e lo stack degli operandi contiene il risultato dell'espressione, -2.

[Vincenzo1968]

Anticipo quello che sarà il secondo problema da risolvere. Si tratterà di leggere un file di espressioni in notazione polacca inversa (http://it.wikipedia.org/wiki/Reverse_Polish_notation), convertirle in forma infissa e calcolarne il risultato.

Il tempo di preparare i file... :)

[gugoXX]

Anticipo quello che sarà il secondo problema da risolvere. Si tratterà di leggere un file di espressioni in notazione polacca inversa (http://it.wikipedia.org/wiki/Reverse_Polish_notation), convertirle in forma infissa e calcolarne il risultato.

Il tempo di preparare i file... :)

Ma come... se ce l'ho polacca inversa e' ancora piu' semplice calcolare il risultato no?

[Vincenzo1968]

Ma come... se ce l'ho polacca inversa e' ancora piu' semplice calcolare il risultato no?

Si, è più semplice. La parte difficile è trasformarla nella 'normale' notazione infissa(la notazione, cioè, a cui siamo abituati). Bisognerà inserire le parentesi al posto giusto per rispettare la precedenza degli operatori.

Se si preferisce, ed è, anzi, consigliabile(è più semplice e anche più veloce ;)), si può calcolare il risultato a partire dalla notazione polacca inversa. Ma il file di output dovrà contenere le espressioni in forma infissa:

InfixExpr = Result

Per esempio, se in input abbiamo:

5 3 2 * +

l'output dovrà essere il seguente:

5 + 3 * 2 = 11


Altro esempio:

input : 3 5 8 + *
output : 3 * (5 + 8) = 39

;)

[gugoXX]

Si, è più semplice. La parte difficile è trasformarla nella 'normale' notazione infissa(la notazione cioè a cui siamo abituati). Bisognerà inserire le parentesi al posto giusto per rispettare la precedenza degli operatori.

Il file di output dovrà contenere le espressioni in forma infissa ;)

OK. si ammettono piu' soluzioni, corrette anche se ridondanti?
Mi spiego, e' ammesso
3 * 5 + 4
ma anche
(3 * 5) + 4
anche se ridondante?

[Vincenzo1968]

OK. si ammettono piu' soluzioni, corrette anche se ridondanti?
Mi spiego, e' ammesso
3 * 5 + 4
ma anche
(3 * 5) + 4
anche se ridondante?

Si. Volendo, va bene anche questa:

input: 3 5 * 4 +

output : ((3*5) + 4) = 19

[Vincenzo1968]

OK. si ammettono piu' soluzioni, corrette anche se ridondanti?
Mi spiego, e' ammesso
3 * 5 + 4
ma anche
(3 * 5) + 4
anche se ridondante?

Ora che ci penso, potrebbe essere il terzo problema da risolvere: dato in input un file contenente espressioni fully parenthesized, si produca, in output, un file contenente le espressioni con il numero minimo di parentesi ;)

Il tempo di preparare i file :)

[goldorak]

Vabbe' ma così so' buoni tutti... :Prrr:

Ok, risolvi il problema scrivendo direttamente codice macchina.
Cosi vediamo quanti sei bravo. :O

[DanieleC88]

Ok, risolvi il problema scrivendo direttamente codice macchina.
Cosi vediamo quanti sei bravo. :O
Bella, 'sta provocazione totalmente inutile. :)

Il mio intento non è certo quello di dimostrare di "essere bravo", ma ammetterai che eval() rende la vita troppo facile ai fini del contest...

[goldorak]

Bella, 'sta provocazione totalmente inutile. :)

Il mio intento non è certo quello di dimostrare di "essere bravo", ma ammetterai che eval() rende la vita troppo facile ai fini del contest...

Dipende, le specifiche del contest non stabiliscono che uno debba per forza usare C/C++. :)
Se per esempio si facesse un contest per sviluppare un piccolo programma di calcolo simbolico, lo implementeresti in C o in un linguaggio piu' adatto allo scopo ?
La bravura non sta solo nel "scrivere codice" ma anche sapere quale linguaggio e' piu' adatto allo scopo.

[DanieleC88]

E ti pare infatti che questo sia un contesto in cui è essenziale il tempo che impieghi a sviluppare il tutto? Qui lo si fa più che altro per gioco, per divertimento, per il solo gusto di farlo, niente più.

E, possibilmente, tirare fuori un'idea che sia efficiente più delle altre: non ho certo questa pretesa, quindi mi limito al divertimento. C'è qualcosa che ti infastidisce in questo?

[DanieleC88]

P.S.: qui volevo anche un po' utilizzare il contest come "sfida con me stesso", le precedenti volte ho prima scritto il tutto in Python... e alla fine in C.

[goldorak]

E ti pare infatti che questo sia un contesto in cui è essenziale il tempo che impieghi a sviluppare il tutto? Qui lo si fa più che altro per gioco, per divertimento, per il solo gusto di farlo, niente più.

E, possibilmente, tirare fuori un'idea che sia efficiente più delle altre: non ho certo questa pretesa, quindi mi limito al divertimento. C'è qualcosa che ti infastidisce in questo?


Io continuo a non capire cosa intendi per efficienza.
Il tempo di esecuzione del programma ?
La scrittura dell'algoritmo in un linguaggio di basso livello ?
Se io trovassi un algoritmo per risolvere questo problema e lo implementassi in Haskell o Common Lisp secondo la tua visione sarebbe meno efficiente ? :boh:

[DanieleC88]

No, potrebbe benissimo essere più efficiente, se la sua complessità computazionale (http://it.wikipedia.org/wiki/Teoria_della_complessità_computazionale) è minore, è quello che ne determina l'efficienza su input di grandezza rilevante.

In ogni caso, non ho capito dove vuoi arrivare: se vuoi partecipare al contest fallo, altrimenti sei pregato almeno di non turbare. Se poi hai qualcosa da ridire su di me per qualche motivo, fallo chiaramente (e magari in forma privata).

[goldorak]

No, potrebbe benissimo essere più efficiente, se la sua complessità computazionale (http://it.wikipedia.org/wiki/Teoria_della_complessità_computazionale) è minore, è quello che ne determina l'efficienza su input di grandezza rilevante.


In assoluto e' cosi, ma come ben saprai ci sono algoritmi con complessita (nel caso peggiore) esponenziale che nonstante questo sono ben efficiente sui problemi che devono risolvere.
L'algoritmo del simplesso ne' e' un esempio lampante. ;)


In ogni caso, non ho capito dove vuoi arrivare: se vuoi partecipare al contest fallo, altrimenti sei pregato almeno di non turbare. Se poi hai qualcosa da ridire su di me per qualche motivo, fallo chiaramente (e magari in forma privata).


Non ho niente contro di te e non voglio arrivare da nessuna parte.
Se il contest lascia libera la scelta del linguaggio di programmazione (usando solo i costrutti primitivi del linguaggio) allora l'efficienza va valutata sul tempo di esecuzione. Indipendentemente che uno usi C#, C, C++, Java, etc...

[DanieleC88]

Ok. E quindi? Misurare il tempo di esecuzione è ciò che già stiamo facendo. :D

Infine, il mio messaggio di prima voleva solo "stuzzicare" un po' VICIUS a fare qualcosa di "meno automatico", mica dimostrargli che sono più bravo io o qualcosa del genere (sono l'ultimo che può farlo). Quindi, se era questo il problema, possiamo anche chiudere qui. ;)

[Vincenzo1968]

Problema 2:
Sia dato, in input, un array di stringhe contenenti espressioni in formato RPN (http://it.wikipedia.org/wiki/Reverse_Polish_notation).
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 (http://www.guidealgoritmi.it/public/espressioni2.zip)

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: -

x Vicius o Cionci: è possibile inserire il testo del problema alla fine del primo post? ;)

[VICIUS]

x Vicius o Cionci: è possibile inserire il testo del problema alla fine del primo post? ;)
Non ti basta cliccare su modifica? In fondo è un tuo messaggio.

[Vincenzo1968]

Goldorack e Daniele,

occhio che lo facciamo si per divertimento ma, alla fine, chi perde dovrà indossare il sambenito per un mese intero :Perfido:

[Vincenzo1968]

Non ti basta cliccare su modifica? In fondo è un tuo messaggio.


Pensavo che dopo un certo tempo non si potesse più modificare un post. Ok, lo faccio subito, grazie ;)

[Vincenzo1968]

Ok, risolvi il problema scrivendo direttamente codice macchina.
...

Modificato leggermente, non sarebbe male come quarto problema da risolvere: per ogni espressione si costruisca l'albero di parsing e si fornisca, in output, il codice assembly.
Sarebbe un minicompilatore(io so come si costruisce l'albero di parsing ma non ne capisco un tubo di assembly ;))

[gugoXX]

Vabbe'.
Io proseguo a postare il primo quesito.
Voglio almeno il premio originalita'
Ovviamente non metto i tempi perche' in fondo con questa soluzione non ci sono mai arrivato.(E mai ci arrivero'... prima di essere bannato da google)
Ho addirittura messo uno sleep, per non sovraccaricare troppo e risultare un brutto Worm.
Comunque ecco

(Occorre la System.Net)

class Program
{
static void Main(string[] args)
{
string[] strs = File.ReadAllLines(@"C:\temp\espressioni1.txt");

foreach (string clc in strs.Skip(2))
{
string res = Eva3.Calc(clc);
Thread.Sleep(1000);
Console.WriteLine("{0} = {1}", clc, res);
}
Console.ReadKey();
}
}

public static class Eva3
{
public static string Calc(string inp)
{
string enc = GoogleEnc(inp);
//string enc = System.Web.HttpUtility.UrlEncode(inp);

string ret;
string req = string.Format("http://www.google.it/search?hl=it&q={0}&meta=",enc);
using (WebClient wdc = new WebClient())
{
// Cosi' lo frego un pochino in piu'
wdc.Headers.Add("user-agent", "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.2; .NET CLR 1.0.3705;)");

// GetHttpResponse
string str = wdc.DownloadString(req);
// Result
string sqp = Regex.Match(str, "<h2 class=r>.*</h2>").Value;
if (string.IsNullOrEmpty(sqp)) return "Generic Error";
// Detag
string topr = Regex.Replace(sqp, "<[^>]+>", "");
// Destra dell'uguale
string res = topr.Substring(topr.IndexOf('=') + 1);
// Nospazi in risultato
ret = res.Replace(" ", "");
// Se c'e' altro rispetto a - . 0-9 allora Error2
if (Regex.Replace(ret, @"[\.\-0-9]+", "").Length != 0) return "Generic Error2";
}
return ret;
}
private static string GoogleEnc(string inp)
{
StringWriter sw=new StringWriter();
foreach (char ch in inp)
{
switch (ch)
{
case '(':
sw.Write("%28");
break;
case ')':
sw.Write("%29");
break;
case '+':
sw.Write("%2B");
break;
case '^':
sw.Write("%5E");
break;
case ' ':
break;
default:
sw.Write(ch);
break;
}
}
return sw.ToString();
}
}



Ecco un pezzo di risultato.


5 / (3 - (2+1)) = Generic Error
(-57.41 - -34.48) + (-63.04 * 2)/(-50.81 - -17.06) = -19.1942963
(-93.49 - -45.33) + (-81.46 * 2)/(46.01 - 25.26) = -56.0115663
(-43.81 * (-96.73^4^0.5 - 7.65)) - ((75.11 * -50.68/(1 + -52.19) - 5) / (-4.3 +
-11.82^(1/2)))) = Generic Error2
(5.46 + -36.91/(-32.31+-33.03)) - 43.14 * -55.51/2 = 1203.37559
-30.78 + (58.74 # 1.12)/78.35^(1/2) = Generic Error2

[Vincenzo1968]

Questi sono i miei tempi per il problema 2:

file piccolo:
http://www.guidealgoritmi.it/images/ImgForums/Contest06BTempi1.jpg

file grosso:
http://www.guidealgoritmi.it/images/ImgForums/Contest06BTempi2.jpg

Il codice in C può essere scaricato da QUI (http://www.guidealgoritmi.it/public/Contest06B.zip)

La mia macchina è questa:

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


Righe iniziali dei file di output:

file piccolo
http://www.guidealgoritmi.it/images/ImgForums/Contest06BOutput1.jpg

file grosso:
http://www.guidealgoritmi.it/images/ImgForums/Contest06BOutput2.jpg

[||ElChE||88]

Sbaglio o ci sono delle divisioni per zero?

Per ora i miei tempi sono:
http://img01.picoodle.com/img/img01/3/10/27/f_Untitled2m_087fd91.jpg

Prima di postare il programma voglio migliorare qualcosina e ridurre l'immenso numero di parentesi nel file di output. :asd:

[||ElChE||88]

Vincenzo...
il tuo programma mi da il seguente risultato:
((-65.78 * 52.31) / (1 + 66.31) - 5) / (-4.3 + 18.49^(1 / 2)) = 12940612268343702000.000000

Solo che:
18.49^(1 / 2) = 4.3
quindi:
(-4.3 + 18.49^(1 / 2)) = (-4.3 + 4.3) = 0

Sbaglio o il programma dovrebbe lamentarsi della divisione per zero?

[Vincenzo1968]

Vincenzo...
il tuo programma mi da il seguente risultato:
((-65.78 * 52.31) / (1 + 66.31) - 5) / (-4.3 + 18.49^(1 / 2)) = 12940612268343702000.000000

Solo che:
18.49^(1 / 2) = 4.3
quindi:
(-4.3 + 18.49^(1 / 2)) = (-4.3 + 4.3) = 0

Sbaglio o il programma dovrebbe lamentarsi della divisione per zero?

Ciao Elche,

dammi il tempo di controllare e correggere l'errore.
Mi dai i tempi dei miei programmi sulla tua macchina?

[||ElChE||88]

Ciao Elche,

dammi il tempo di controllare e correggere l'errore.
Mi dai i tempi dei miei programmi sulla tua macchina?
Ecco i tempi:
(xxx-1 = primo esercizio, xxx-2 = secondo esercizio)

http://img29.picoodle.com/img/img29/3/10/27/f_Untitled1m_97027dd.jpg

Gli output del primo esercizio sono identici (a parte la precisione dei risultati).
Gli output del secondo esercizio invece sono quasi identici, ma il tuo ha un solo errore di divisione per zero, il mio ne ha di più.

[Vincenzo1968]

Vincenzo...
il tuo programma mi da il seguente risultato:
((-65.78 * 52.31) / (1 + 66.31) - 5) / (-4.3 + 18.49^(1 / 2)) = 12940612268343702000.000000

Solo che:
18.49^(1 / 2) = 4.3
quindi:
(-4.3 + 18.49^(1 / 2)) = (-4.3 + 4.3) = 0

Sbaglio o il programma dovrebbe lamentarsi della divisione per zero?

Ho controllato il file di output:

http://www.guidealgoritmi.it/images/ImgForums/Contest06BOutput3.jpg

Il messaggio di errore c'è anche se manca il segno di uguale tra l'espressione e il messaggio.
Quale compilatore hai utilizzato? (io Visual C++ 2008)

Dammi due minuti e posto il link per scaricare i file di output.

[||ElChE||88]

Ho controllato il file di output:

http://www.guidealgoritmi.it/images/ImgForums/Contest06BOutput3.jpg

Il messaggio di errore c'è anche se manca il segno di uguale tra l'espressione e il messaggio.
Quale compilatore hai utilizzato? (io Visual C++ 2008)
GCC.
Ora provo con Visual Studio.

Edit: Provato con VS e funziona bene. Azzo fa GCC? :wtf:
In che modo gestisci le divisioni per zero?
Ri-Edit:
if ( dblRight == 0 )
Mi sa che c'entra col modo in cui vengono rappresentate le cifre a virgola mobile.

[Vincenzo1968]

GCC.
Ora provo con Visual Studio.

Edit: Provato con VS e funziona bene. Azzo fa GCC? :wtf:
In che modo gestisci le divisioni per zero?
Ri-Edit:
if ( dblRight == 0 )
Mi sa che c'entra col modo in cui vengono rappresentate le cifre a virgola mobile.

E si, dovrebbe essere quello.
Aggiusto il codice in modo da farlo funzionare anche con GCC.

Intanto questo è il link (http://www.guidealgoritmi.it/public/Contest06BOutput.zip) per scaricare i file di output del mio programma per il secondo problema.

[Vincenzo1968]

Ok,

ho aggiornato il link al sorgente (http://www.guidealgoritmi.it/public/Contest06B.zip). Ho messo anche il segno di uguale tra il messaggio di errore e l'espressione.


if ( dblRight == 0.0 )
{
sprintf(szError, "Errore: divisione per zero!");
return 0.0;
}
else
{
return dblLeft / dblRight;
}


So che ti sto scassando i cabasisi, ma potresti provarlo con GCC? :)
;)

[||ElChE||88]

So che ti sto scassando i cabasisi
Veramente mi diverto. :D
ma potresti provarlo con GCC? :)
;)
Fatto... e non funziona
VS: ((-65.78 * 52.31) / (1 + 66.31) - 5) / (-4.3 + 18.49^(1 / 2)) = Errore: divisione per zero!
GCC: ((-65.78 * 52.31) / (1 + 66.31) - 5) / (-4.3 + 18.49^(1 / 2)) = 12940612268343702000.000000

Adesso provo a mettere dei messaggi di debug nel codice per vedere i valori delle variabili...

[||ElChE||88]

Ma che azzo fa? :wtf:
Se assegno EvalTree(pTree->left, szError) a dblLeft ed EvalTree(pTree->right, szError) a dblRight per ogni operazione(PLUS,MINUS,MULT,ecc) e poi uso le due variabili, funziona tutto perfettamente.
Se invece uso direttamente EvalTree(pTree->left, szError) ed EvalTree(pTree->right, szError) il risultato è sballato.

[Vincenzo1968]

Ma che azzo fa? :wtf:
Se assegno EvalTree(pTree->left, szError) a dblLeft ed EvalTree(pTree->right, szError) a dblRight per ogni operazione(PLUS,MINUS,MULT,ecc) e poi uso le due variabili, funziona tutto perfettamente.
Se invece uso direttamente EvalTree(pTree->left, szError) ed EvalTree(pTree->right, szError) il risultato è sballato.

:confused:

prova a mettere il suffisso L:


case DIV:
dblLeft = EvalTree(pTree->left, szError);
dblRight = EvalTree(pTree->right, szError);
if ( dblRight == 0.0L )
{
sprintf(szError, "Errore: divisione per zero!");
return 0.0;
}
else
{
return dblLeft / dblRight;
}

[||ElChE||88]

:confused:
VS divide per 0, GCC divide per -0
Che diavolo è -0?

[Vincenzo1968]

Non credo il problema sia in quella parte... sto cercando di capirci qualcosa ora. Potrebbe essere un bug della mia versione di GCC comunque.

Edit: Il problema invece è proprio nel dblRight == 0.0L
Edit: VS divide per 0, GCC divide per -0
Che diavolo è -0?

Boh! :confused:

[gugoXX]

Propongo di stampare anche, alla fine, la somma di tutti i risultati che non sono infinito (o comunque che non sono valori tipo NaN, etc., nel caso in cui ci fossero)
Cosi' possiamo controllare la correttezza anche quando non si stampa tutto.
Il problema e' che ci sono risultati che sono molto grandi, e quelli piccoli, se sbagliati, annegano.

[||ElChE||88]

Ho usato printf per mostrare le operazioni fatte dal programma (espressione 65.78 ~ 52.31 * 1 66.31 + / 5 - 4.3 ~ 18.49 1 2 / ^ + / )
VS:

UMINUS 65.780000
MULT -65.780000 52.310000
UMINUS 65.780000
PLUS 1.000000 66.310000
DIV -3440.951800 67.310000
MINUS -51.120960 5.000000
UMINUS 65.780000
MULT -65.780000 52.310000
UMINUS 65.780000
PLUS 1.000000 66.310000
DIV -3440.951800 67.310000
DIV 1.000000 2.000000
POW 18.490000 0.500000
DIV 1.000000 2.000000
UMINUS 4.300000
PLUS -4.300000 4.300000
DIV 1.000000 2.000000
POW 18.490000 0.500000
DIV 1.000000 2.000000
UMINUS 4.300000
DIV -56.120960 0.000000
ERROR#DIVBY0!
RESULT 0.000000

GCC:

UMINUS 65.780000
MULT -65.780000 52.310000
UMINUS 65.780000
PLUS 1.000000 66.310000
DIV -3440.951800 67.310000
MINUS -51.120960 5.000000
UMINUS 65.780000
MULT -65.780000 52.310000
UMINUS 65.780000
PLUS 1.000000 66.310000
DIV -3440.951800 67.310000
DIV 1.000000 2.000000
POW 18.490000 0.500000
DIV 1.000000 2.000000
UMINUS 4.300000
PLUS -4.300000 4.300000
UMINUS 4.300000
DIV 1.000000 2.000000
POW 18.490000 0.500000
DIV 1.000000 2.000000
DIV -56.120960 -0.000000
RESULT 12940612268343702000.000000


Per quale ragione le operazioni vengono eseguite in ordine diverso?

[gugoXX]

Eccomi.

Tempi File Piccolo

Read Time: 50ms
Calc Time: 655ms
Write Time: 59ms
----------
Tot Time: 764ms


Tempi File Grosso

Read Time: 117ms
Calc Time: 1148ms
Write Time: 93ms
----------
Tot Time: 1358ms


Primi risultati del file grosso

(((-67.61+(34.14/(-15.21+57.74)))-((4.56*78.41)/2))*(-51.68/(29.65^0.5))) = 2330
.80969717493
(-81.31+((89.41-0.11)/-(66.21^(1/2)))) = -92.2846243810478
((43.48+(-88.06/(-33.08+6.31)))-((3.76*-19.41)/2)) = 83.2603031751961
((((47.51*79.71)/(1+17.62))-5)/(-4.3+-(62.08^(1/2)))) = -16.2889597470345
((((35.54*94.98)/(1+-31.23))-5)/(-4.3+(3.15^(1/2)))) = 46.200165753162
(-54.81+((8.64-4.38)/(41.34^(1/2)))) = -54.1474412970664
(61.78/(83.47^0.5)) = 6.76211725594548
(-94.12+((65.29-50.11)/(6.42^(1/2)))) = -88.1289318818543
((-5.21*-56.23)*(-8+(89.67*(41.54/(2+(90.45^0.5)))))) = 92459.863146181


Codice

class Program
{
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
string toread = @"C:\temp\espressioni3.txt";
string[] vals = File.ReadAllLines(toread);
long p1 = sw.ElapsedMilliseconds;

Exec xx=new Exec();
int ln = vals.Length;

var calcs = vals.AsParallel().Skip(1).Select(t => xx.Executor(t));
var toprint = calcs.Select(t => string.Format("{0} = {1}", t.pars, t.res)).ToArray();
long p2 = sw.ElapsedMilliseconds;
File.WriteAllLines(toread + ".output", toprint);

sw.Stop();
long p3 = sw.ElapsedMilliseconds;

Console.WriteLine("Read Time: {0}ms", p1);
Console.WriteLine("Calc Time: {0}ms", p2 - p1);
Console.WriteLine("Write Time: {0}ms", p3 - p2);
Console.WriteLine("----------");
Console.WriteLine("Tot Time: {0}ms", p3);

Console.ReadKey();
}

public class Exec
{
char[] splitter;

public Exec()
{
splitter = new char[] { ' ' };
}

public Result Executor(string str)
{
Stack<string> stamp = new Stack<string>();
Stack<double> ds = new Stack<double>();
string[] spls = str.Split(splitter, StringSplitOptions.RemoveEmptyEntries);

int len = spls.Length;
for(int t=0;t<len;t++)
{
string sing = spls[t];
bool ex = false;
if (sing.Length == 1)
{
char ch = sing[0];
double d1, d2, d3;
string el1, el2, el3;
switch (ch)
{
case '+':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = d1 + d2;
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}+{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '-':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = d1 - d2;
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}-{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '/':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = d1 / d2;
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}/{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '*':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = d1 * d2;
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}*{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '^':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = Math.Pow(d1, d2);
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}^{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '~':
d1 = ds.Pop();
ds.Push(-d1);
el1 = stamp.Pop();
el3 = string.Format("-{0}", el1);
stamp.Push(el3);
ex = true;
break;
default:
break;
}
}
if (!ex)
{
double pars = double.Parse(sing);
ds.Push(pars);
stamp.Push(sing);
}
}
double res = ds.Pop();
string notaz = stamp.Pop();
return new Result() { inp = str, pars = notaz, res = res };
}
}

public struct Result
{
public string inp;
public string pars;
public double res;
}

}

[Vincenzo1968]

Elche,

ho provato il tuo codice(Problema 1) e mi dà dei risultati sbagliati. Per esempio, sul file piccolo, per la seconda e la terza espressione:

(-57.41 - -34.48) + (-63.04 * 2)/(-50.81 - -17.06) = -2289,2642962963
(-93.49 - -45.33) + (-81.46 * 2)/(46.01 - 25.26) = -4823,85156626506

mentre dovrebbe essere:

(-57.41 - -34.48) + (-63.04 * 2)/(-50.81 - -17.06) = -19.194296
(-93.49 - -45.33) + (-81.46 * 2)/(46.01 - 25.26) = -56.011566

[||ElChE||88]

Elche,

ho provato il tuo codice(Problema 1) e mi dà dei risultati sbagliati. Per esempio, sul file piccolo, per la seconda e la terza espressione:

(-57.41 - -34.48) + (-63.04 * 2)/(-50.81 - -17.06) = -2289,2642962963
(-93.49 - -45.33) + (-81.46 * 2)/(46.01 - 25.26) = -4823,85156626506

mentre dovrebbe essere:

(-57.41 - -34.48) + (-63.04 * 2)/(-50.81 - -17.06) = -19.194296
(-93.49 - -45.33) + (-81.46 * 2)/(46.01 - 25.26) = -56.011566
L'ho eseguito ora e:

(-57.41 - -34.48) + (-63.04 * 2)/(-50.81 - -17.06) = -19.1942962962963
(-93.49 - -45.33) + (-81.46 * 2)/(46.01 - 25.26) = -56.0115662650602

Perché te li da sbagliati? :wtf:

Boh, nel caso abbia cambiato qualcosa prova con questo:
http://pastebin.com/m224b5648

[||ElChE||88]

Primi risultati del file grosso
Sono completamente diversi dai nostri (miei e di Vincenzo).

[gugoXX]

Cosi'?
Sempre file grosso (Ma sono al punto 2...)


(((-67.61+(34.14/(-15.21+57.74)))-((4.56*78.41)/2))*(-51.68/(29.65^0.5))) = 2330
.80969717493
(-81.31+((89.41-0.11)/-(66.21^(1/2)))) = -92.2846243810478
((43.48+(-88.06/(-33.08+6.31)))-((3.76*-19.41)/2)) = 83.2603031751961
((((47.51*79.71)/(1+17.62))-5)/(-4.3+-(62.08^(1/2)))) = -16.2889597470345
((((35.54*94.98)/(1+-31.23))-5)/(-4.3+(3.15^(1/2)))) = 46.200165753162
(-54.81+((8.64-4.38)/(41.34^(1/2)))) = -54.1474412970664
(61.78/(83.47^0.5)) = 6.76211725594548
(-94.12+((65.29-50.11)/(6.42^(1/2)))) = -88.1289318818543
((-5.21*-56.23)*(-8+(89.67*(41.54/(2+(90.45^0.5)))))) = 92459.863146181

[Vincenzo1968]

L'ho eseguito ora e:

(-57.41 - -34.48) + (-63.04 * 2)/(-50.81 - -17.06) = -19.1942962962963
(-93.49 - -45.33) + (-81.46 * 2)/(46.01 - 25.26) = -56.0115662650602

Perché te li da sbagliati? :wtf:

Boh, nel caso abbia cambiato qualcosa prova con questo:
http://pastebin.com/m224b5648

Boh :confused:
Anche con il codice al link che mi hai indicato mi dà quel risultato.

[||ElChE||88]

Boh :confused:
Anche con il codice al link che mi hai indicato mi dà quel risultato.
Prova: http://pastebin.com/m39a2684b
Dovrebbe essere indipendente dalla lingua dell'OS.

[Vincenzo1968]

Cosi'?
Sempre file grosso


(((-67.61+(34.14/(-15.21+57.74)))-((4.56*78.41)/2))*(-51.68/(29.65^0.5))) = 2330
.80969717493
(-81.31+((89.41-0.11)/-(66.21^(1/2)))) = -92.2846243810478
((43.48+(-88.06/(-33.08+6.31)))-((3.76*-19.41)/2)) = 83.2603031751961
((((47.51*79.71)/(1+17.62))-5)/(-4.3+-(62.08^(1/2)))) = -16.2889597470345
((((35.54*94.98)/(1+-31.23))-5)/(-4.3+(3.15^(1/2)))) = 46.200165753162
(-54.81+((8.64-4.38)/(41.34^(1/2)))) = -54.1474412970664
(61.78/(83.47^0.5)) = 6.76211725594548
(-94.12+((65.29-50.11)/(6.42^(1/2)))) = -88.1289318818543
((-5.21*-56.23)*(-8+(89.67*(41.54/(2+(90.45^0.5)))))) = 92459.863146181


Il file di output dove lo piazzi? Sarà la stanchezza per l'ora tarda, ma non riesco a trovarlo nel codice. Eseguendo il programma mi stampa a video i tempi e la somma ma non ho il file di output :confused:

[||ElChE||88]

Cosi'?
Sempre file grosso (Ma sono al punto 2...)
Questi sono giusti.
Quelli che hai postato prima che punto erano?

Edit: Perché il tuo programma funzioni è necessario che i caratteri siano separati da spazi, vero?

[Vincenzo1968]

Prova: http://pastebin.com/m39a2684b
Dovrebbe essere indipendente dalla lingua dell'OS.

Perfetto!
Adesso ci siamo ;)

[gugoXX]

Questi sono giusti.
Quelli che hai postato prima che punto erano?

Edit: Perché il tuo programma funzioni è necessario che i caratteri siano separati da spazi, vero?

Erano sempre il punto 2, ma avevo invertito l'ordine di estrazione dallo stack.
Si', separati da spazio, come sono i file.
Se devo cambiarli lo faccio, ma con la polacca inversa i numeri devono essere separati tra loro in qualche modo, dato che possono essere consecutivi.

[||ElChE||88]

Se devo cambiarli lo faccio, ma con la polacca inversa i numeri devono essere separati tra loro in qualche modo, dato che possono essere consecutivi.
Hai perfettamente ragione.

PS: Anch'io avevo sbagliato ordine all'inizio, usavo l'inorder traversal iniziando a sinistra invece che a destra (ero convinto che il prof avesse detto di iniziare a sinistra :wtf:... la mia memoria perde colpi :asd:).

[Vincenzo1968]

Gugo,

il file di output?

[gugoXX]

Gugo,

il file di output?

ma tutto? E' lunghissimo...
Ah ho capito. BAsta che metti a true la variabile spoolout
Ma quella versione e' sbagliata. Ho invertito le POP dagli stack
Lo riscrivo sopra.

Edit: Riscritto.

[Vincenzo1968]

ma tutto? E' lunghissimo...
Ah ho capito. BAsta che metti a true la variabile spoolout
Ma quella versione e' sbagliata. Ho invertito le POP dagli stack
Lo riscrivo sopra.

No dico, nel codice. Il programma deve produrre il file con i risultati(mi dà soltanto la somma e i tempi a video).

[||ElChE||88]

ma tutto? E' lunghissimo...
In effetti 14MB sarebbe lunghetto da uploadare (quando non si ha una connessione da svariati mbit in upload - come il sottoscritto :asd:)
Comunque se leggi le istruzioni è richiesto l'output su file (credo Vincenzo intendesse questo).

[Vincenzo1968]

In effetti 14MB sarebbe lunghetto da uploadare (quando non si ha una connessione da svariati mbit in upload - come il sottoscritto :asd:)
Comunque se leggi le istruzioni è richiesto l'output su file (credo Vincenzo intendesse questo).

Esatto. Mettendo a true la variabile spoolout stampa tutte cose a video e ci mette 23 secondi :mad:

[gugoXX]

Esatto. Mettendo a true la variabile spoolout stampa tutte cose a video e ci mette 23 secondi :mad:

Ma qual e' il problema?
Se ci mette 1 secondo e mezzo a calcolare e 23 secondi a stampare.
non e' che posso ottimizzare il calcolo piu' di tanto.
E neppure la stampa. Stampa e basta.
Facciamo il contest per chi stampa piu' in fretta a video un testo letto da file...

Se e' sufficiente lo spool su file allora cambio.

[||ElChE||88]

Esatto. Mettendo a true la variabile spoolout stampa tutte cose a video e ci mette 23 secondi :mad:
In teoria potresti redirigere l'output su file (nomefile > xxx.txt), però ci mette comunque di più che scrivere direttamente su file (provato da me).

[Vincenzo1968]

Ma qual e' il problema?
Se ci mette 1 secondo e mezzo a calcolare e 23 secondi a stampare.
non e' che posso ottimizzare il calcolo piu' di tanto.
E neppure la stampa. Stampa e basta.
Facciamo il contest per chi stampa piu' in fretta a video un testo letto da file...

Se e' sufficiente lo spool su file allora cambio.

Nessun problema,

ma, come dice Elche, ci perdi nel calcolo dei tempi di esecuzione. ;)

[gugoXX]

Ok, ricambiato.
Tempi aggiornati.
Nei tempi I/O non e' inclusa la scrittura pero' ora... se devo includerla devo cappottare un po'

[||ElChE||88]

Vincenzo, come vanno misurati i tempi?

Tempo di lettura: caricamento delle espressioni da file di testo
Tempo di calcolo: calcolo e scrittura dei risultati su file di testo

o

Tempo di lettura: caricamento delle espressioni da file di testo
Tempo di calcolo: calcolo dei risultati (scrittura esclusa, da eseguirsi dopo)

[gugoXX]

Per ora mi fermo qui.
Aggiornato di nuovo.
Messo il parallelismo e separato i tempi di lettura, calcolo e scrittura.

'Notte.

[Vincenzo1968]

Vincenzo, come vanno misurati i tempi?

Tempo di lettura: caricamento delle espressioni da file di testo
Tempo di calcolo: calcolo e scrittura dei risultati su file di testo

o

Tempo di lettura: caricamento delle espressioni da file di testo
Tempo di calcolo: calcolo dei risultati (scrittura esclusa, da eseguirsi dopo)

Io il tempo di scrittura sul file di output l'ho incluso:


int main()
{
Stati stato;
Array myArray;
char *szFileName = "espressioni4.txt";
char *szFileNameOutput = "output4.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;
}


Il tempo impiegato per il calcolo delle espressioni include calcolo e scrittura su file(e deallocazione della memoria allocata in precedenza).

[Vincenzo1968]

Gugo,

mi dà questi risultati(le prime cinque righe del file grosso):

(((-67.61+(34.14/(-15.21+57.74)))-((4.56*78.41)/2))*(-51.68/(29.65^0.5))) = 4,04710491546159E-08
(-81.31+((89.41-0.11)/-(66.21^(1/2)))) = -8240,74624381048
((43.48+(-88.06/(-33.08+6.31)))-((3.76*-19.41)/2)) = 369259,289503175
((((47.51*79.71)/(1+17.62))-5)/(-4.3+-(62.08^(1/2)))) = -176,331425955617
((((35.54*94.98)/(1+-31.23))-5)/(-4.3+(3.15^(1/2)))) = 428,376672986787


dovrebbe essere:

((-67.61 + 34.14 / (-15.21 + 57.74)) - (4.56 * 78.41) / 2) * (-51.68 / 29.65^0.5) = 2330.809697
-81.31 + (89.41 - 0.11) / -(66.21^(1 / 2)) = -92.284624
(43.48 + -88.06 / (-33.08 + 6.31)) - (3.76 * -19.41) / 2 = 83.260303
((47.51 * 79.71) / (1 + 17.62) - 5) / (-4.3 + -(62.08^(1 / 2))) = -16.288960
((35.54 * 94.98) / (1 + -31.23) - 5) / (-4.3 + 3.15^(1 / 2)) = 46.200166

[gugoXX]

Forse hai una versione non aggiornata, era il primo errore che avevo fatto.
Posto la versione nuova... sono quasi al secondo (sulla mia macchina)


Read Time: 115ms
Calc Time: 937ms
----------
Tot Time: 1052ms



class Program
{
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
string toread = @"C:\temp\espressioni4.txt";
string[] vals = File.ReadAllLines(toread);
long p1 = sw.ElapsedMilliseconds;

Exec xx=new Exec();
int ln = vals.Length;

StreamWriter swr = new StreamWriter(toread + ".output");
Parallel.For(1, ln, t =>
{
string str = vals[t];
var rs = xx.Executor(str);
string towrite=string.Format("{0} = {1}", rs.pars, rs.res);
lock (swr)
{
swr.WriteLine(towrite);
}
});
swr.Close();

//var calcs = vals.AsParallel().Skip(1).Select(t => xx.Executor(t));
//var toprint = calcs.Select(t => string.Format("{0} = {1}", t.pars, t.res)).ToArray();
//long p2 = sw.ElapsedMilliseconds;
//File.WriteAllLines(toread + ".output", toprint);

sw.Stop();
long p2 = sw.ElapsedMilliseconds;

Console.WriteLine("Read Time: {0}ms", p1);
Console.WriteLine("Calc Time: {0}ms", p2 - p1);
Console.WriteLine("----------");
Console.WriteLine("Tot Time: {0}ms", p2);

Console.ReadKey();
}

public class Exec
{
NumberFormatInfo nfi;
char[] splitter;

public Exec()
{
nfi = new NumberFormatInfo();
nfi.NumberDecimalSeparator = ".";
splitter = new char[] { ' ' };
}

public Result Executor(string str)
{
Stack<string> stamp = new Stack<string>();
Stack<double> ds = new Stack<double>();
string[] spls = str.Split(splitter, StringSplitOptions.RemoveEmptyEntries);

int len = spls.Length;
for (int t = 0; t < len; t++)
{
string sing = spls[t];
bool ex = false;
if (sing.Length == 1)
{
char ch = sing[0];
double d1, d2, d3;
string el1, el2, el3;
switch (ch)
{
case '+':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = d1 + d2;
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}+{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '-':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = d1 - d2;
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}-{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '/':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = d1 / d2;
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}/{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '*':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = d1 * d2;
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}*{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '^':
d2 = ds.Pop();
d1 = ds.Pop();
d3 = Math.Pow(d1, d2);
ds.Push(d3);
el2 = stamp.Pop();
el1 = stamp.Pop();
el3 = string.Format("({0}^{1})", el1, el2);
stamp.Push(el3);
ex = true;
break;
case '~':
d1 = ds.Pop();
ds.Push(-d1);
el1 = stamp.Pop();
el3 = string.Format("-{0}", el1);
stamp.Push(el3);
ex = true;
break;
default:
break;
}
}
if (!ex)
{
double pars = double.Parse(sing,nfi);
ds.Push(pars);
stamp.Push(sing);
}
}
double res = ds.Pop();
string notaz = stamp.Pop();
return new Result() { pars = notaz, res = res };
}
}

public struct Result
{
public string pars;
public double res;
}
}

[||ElChE||88]

Gugo,

mi dà questi risultati(le prime cinque righe del file grosso)
Immagino sia lo stesso errore che davano i miei file;
double.Parse(string) funziona secondo il linguaggio del sistema operativo... su un sistema italiano si aspetta 1,1, non 1.1.

[gugoXX]

Immagino sia lo stesso errore che davano i miei file;
double.Parse(string) funziona secondo il linguaggio del sistema operativo... su un sistema italiano si aspetta 1,1, non 1.1.

Che wallas...
Arrangiato

[||ElChE||88]

Gugo, perché i tuoi risultati sono in ordine sparso?

Edit: ho visto ora che usi le Parallel Extensions.

[Vincenzo1968]

Non ne sto capendo più un... tubo :)

http://www.guidealgoritmi.it/images/ImgForums/Contest06BOutputGugo.jpg

[Vincenzo1968]

Gugo,

ci siamo quasi. I risultati sono corretti ma l'ordine delle espressioni deve essere uguale a quello del file di input:

http://www.guidealgoritmi.it/images/ImgForums/Contest06BOutputGugo2.jpg

[cdimauro]

1/2 è una divisione intera in ruby quindi da 0 resto 1. 51.68 elevato alla 0 da 1 e da questo si ottiene lo strano risultato. Forse con una regex riesco ad aggiungere un .0 ai numeri giusti per portarla in R.
Perché non ridefinisci l'operatore di divisione in modo da convertire sempre in float? Con Ruby puoi. :)

[shinya]

Cheppalle con 'sti tempi... ma si può andare avanti per SEI pagine misurando i tempi di questo e quello?!

Si può parlare di algoritmi invece che di tempi? Io aspetto ancora la spiegazione di repne per quanto riguarda il suo algoritmo al contest precedente ad esempio, dato che sembra non l'abbia capito nessuno... (anche li ci si è persi nel misurare tempi, rapporti tra file-piccolo-file-grosso, ecc... sinceramente la cosa comincia un pò ad annoiarmi)

[cdimauro]

Io non mi annoio. Ho apprezzato moltissimo le soluzioni di gugo. :p

[gugoXX]

Cheppalle con 'sti tempi... ma si può andare avanti per SEI pagine misurando i tempi di questo e quello?!

Si può parlare di algoritmi invece che di tempi? Io aspetto ancora la spiegazione di repne per quanto riguarda il suo algoritmo al contest precedente ad esempio, dato che sembra non l'abbia capito nessuno... (anche li ci si è persi nel misurare tempi, rapporti tra file-piccolo-file-grosso, ecc... sinceramente la cosa comincia un pò ad annoiarmi)

Giusto.
Ma io faccio in fretta stavolta (seconda parte)
Leggo le righe poi ciclo su ciascuna riga.
La spacco negli elementi, splittando sullo spazio.
Ciclo sugli elementi considerandoli in ordine.
Quando trovo un numero lo inserisco in uno stack di numeri.
Quando trovo un operatore, a seconda che sia binario o unario, scodo dallo stack 1 o 2 valori, eseguo l'operazione e riinserisco nello stack.
Al termine della riga dovrebbe esserci un solo valore nello stack, lo scodo e lo restuisco.
Un altro stack di stringhe si occupera' di tenere la rappresentazione delle operazioni come la conosciamo noi. Al termine di ogni operazione, al posto di inserire il risultato inserisco l'operazione come la leggiamo noi.
Processo le righe in parallelo su multithread, e scrivo nel file in regione critica (necessario), cosi' mentre un thread e' occupato con l'I/O, l'altro puo' continuare a calcolare.

[Vincenzo1968]

Giusto.
Ma io faccio in fretta stavolta (seconda parte)
Leggo le righe poi ciclo su ciascuna riga.
La spacco negli elementi, splittando sullo spazio.
Ciclo sugli elementi considerandoli in ordine.
Quando trovo un numero lo inserisco in uno stack di numeri.
Quando trovo un operatore, a seconda che sia binario o unario, scodo dallo stack 1 o 2 valori, eseguo l'operazione e riinserisco nello stack.
Al termine della riga dovrebbe esserci un solo valore nello stack, lo scodo e lo restuisco.
Un altro stack di stringhe si occupera' di tenere la rappresentazione delle operazioni come la conosciamo noi. Al termine di ogni operazione, al posto di inserire il risultato inserisco l'operazione come la leggiamo noi.
Processo le righe in parallelo su multithread, e scrivo nel file in regione critica (necessario), cosi' mentre un thread e' occupato con l'I/O, l'altro puo' continuare a calcolare.

L'ordine delle espressioni in output dev'essere quello del file di input. Dovresti cercare di coordinare i risultati ottenuti dai vari thread.

[Vincenzo1968]

Cheppalle con 'sti tempi... ma si può andare avanti per SEI pagine misurando i tempi di questo e quello?!

Si può parlare di algoritmi invece che di tempi? Io aspetto ancora la spiegazione di repne per quanto riguarda il suo algoritmo al contest precedente ad esempio, dato che sembra non l'abbia capito nessuno... (anche li ci si è persi nel misurare tempi, rapporti tra file-piccolo-file-grosso, ecc... sinceramente la cosa comincia un pò ad annoiarmi)

Io ho scritto un pvt a repne e me lo sono fatto spiegare. Credo che lei abbia deciso di non partecipare più a nessun contest.
Sarebbe interessante, piuttosto, se qualche guru decidesse di partecipare al contest dandoci un bell'esempio di come si deve programmare.

Dal contest 7:
Per chi si avvicina da poco alla programmazione e per chi programma gia' da tanto.
Leggete attentatemente questo codice. Poi rileggetelo. Poi chiudete il forum. Tornate fra qualche giorno e rileggetevelo. Poi stampatene una copia e appendetela al muro di fronte al letto: deve essere la prima cosa che guardate la mattina.

Perche' cosi' NON si programma.

Il codice a cui si riferisce il guru è appunto quello di repne.

Se il guru si degnasse di partecipare attivamente, potremmo avere degli esempi di codice da appendere al muro di fronte al letto e da guardare ogni mattina ripetendoci: così si programma(accanto a quelli di repne che, a detta del guru, costituiscono un esempio di come NON si programma).

:)

Spiego l'algoritmo che ho utilizzato per il secondo problema:

1) Costruisco, a partire dall'espressione in formato RPN, l'albero di parsing.
2) Per derivare la corrispondente espressione in notazione infissa, attraverso l'albero in modalità inorder:


void TraverseInOrderP(Tree *root, char *szResult) // Simmetrico (stampa il numero minimo di parentesi )
{
if(!root)
{
return;
}

if ( root->left != NULL )
{
if ( (PREC_TABLE[ root->left->tok->Type ].inputSymbol <= PREC_TABLE[ root->tok->Type ].inputSymbol)
&& root->left->tok->Type != VALUE )
{
strcat(szResult, "(");
TraverseInOrderP(root->left, szResult);
strcat(szResult, ")");
}
else
{
TraverseInOrderP(root->left, szResult);
}
}

if(root->tok)
{
if ( root->tok->Type == UMINUS )
{
strcat(szResult, "-");
}
else if ( root->tok->Type == UPLUS )
{
;
}
else
{
if ( root->tok->Type == MINUS ||
root->tok->Type == PLUS ||
root->tok->Type == MULT ||
root->tok->Type == DIV)
{
strcat(szResult, " ");
strcat(szResult, root->tok->str);
strcat(szResult, " ");
}
else
{
strcat(szResult, root->tok->str);
}
}
}

if ( root->right != NULL )
{
if ( (PREC_TABLE[ root->right->tok->Type ].inputSymbol <= PREC_TABLE[ root->tok->Type ].inputSymbol)
&& root->right->tok->Type != VALUE )
{
strcat(szResult, "(");
TraverseInOrderP(root->right, szResult);
strcat(szResult, ")");
}
else
{
TraverseInOrderP(root->right, szResult);
}
}
}


Come si vede, usando la tabella di precedenza degli operatori, che è uguale a quella che ho utilizzato per il problema 1, è possibile costruire l'espressione in notazione infissa con il numero minimo di parentesi.

3) Per calcolare il risultato, attraverso ricorsivamente l'albero:


double EvalTree(Tree *pTree, char *szError)
{
double dblLeft;
double dblRight;

if ( !pTree )
return 0.0;

switch ( pTree->tok->Type )
{
case VALUE:
return pTree->tok->Value;
case PLUS:
return EvalTree(pTree->left, szError) + EvalTree(pTree->right, szError);
case MINUS:
return EvalTree(pTree->left, szError) - EvalTree(pTree->right, szError);
case MULT:
return EvalTree(pTree->left, szError) * EvalTree(pTree->right, szError);
case DIV:
dblLeft = EvalTree(pTree->left, szError);
dblRight = EvalTree(pTree->right, szError);
if ( dblRight == 0.0L )
{
sprintf(szError, "Errore: divisione per zero!");
return 0.0;
}
else
{
return dblLeft / dblRight;
}
case EXP:
return pow(EvalTree(pTree->left, szError), EvalTree(pTree->right, szError));
case UPLUS:
return EvalTree(pTree->right, szError);
case UMINUS:
return -1 * EvalTree(pTree->right, szError);
default:
if ( pTree->tok->Type == OPAREN )
sprintf(szError, "Errore: parentesi non bilanciate.");
else
printf(szError, "Operatore non riconosciuto: %c\n", pTree->tok->str);
//printf("Operatore non riconosciuto: %s", pTree->tok->str);
return 0.0;
}
}

[Vincenzo1968]

Perchè non lo puoi fare con la prima riga?
La soluzione del contest è un parser a discesa ricorsiva bello e buono. E semplice per di più, perchè non ci sono variabili.

Sinceramente non capisco cosa ci sia da misurare. La soluzione è standard.

Sarebbe interessante vedere un'implementazione dell'algoritmo a discesa ricorsiva, visto che è uno dei più famosi e visto che finora nessuno l'ha utilizzato.
Vuoi farlo tu? ;)

[magix2003]

Implementarlo a mano è abbastanza stupido visto che ci sono dei tool che generano i parser (semi) automaticamente per questi linguaggi (vedi Yacc e Lex).

[VICIUS]

Perché non ridefinisci l'operatore di divisione in modo da convertire sempre in float? Con Ruby puoi. :)
Geniale come al solito :O

Quelle due gsub sono il vero collo di bottiglia del mio esempio. Togliendo quella che sostituisce 1/2 si guadagnano due secondi per il file piccolo e quattro in quello grande. Se poi imbroglio ed uso sed per sostituire ^ con ** posso togliere anche l'ultima gsub e risparmio un altro secondo per il file piccolo e due su quello grande.

[Vincenzo1968]

di Leonardo Sciascia:

Manzoni racconta di quel giudice che, sentite le parti contendenti,
diede ragione all'una e all'altra; e poi diede ragione anche a un
suo bambino, che obiettò non si poteva dare ragione a entrambe.


Faccio come quel giudice: do ragione a chi, come me, pensa che in un contest sia importante stilare una classifica in base ai tempi di esecuzione.
Ma do anche ragione a chi pensa sia più giusto concentrarsi sugli algoritmi.
Ho deciso quindi di modificare le modalità di calcolo dei tempi non includendo, nel conto, il tempo di scrittura su file.

Ho modificato i miei sorgenti in modo che la funzione che effettua i calcoli, e che scrive l'output su file, restituisca il tempo di esecuzione relativo, appunto, ai soli calcoli:


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

*dblTempi = 0;

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

for (k = 0; k < pArray->size; k++)
{
c_start = clock();

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);

c_end = clock();

*dblTempi += (double)(c_end - c_start) / CLOCKS_PER_SEC;

fwrite(szResult, strlen(szResult), 1, fp);
}

fclose(fp);
}

int main()
{
Stati stato;
Array myArray;
char *szFileName = "espressioni2.txt";
char *szFileNameOutput = "output2.txt";
int k;
clock_t c_start, c_end;
double dblTempiCalcolo;

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, &dblTempiCalcolo);

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);
printf("\nTempo impiegato per il calcolo delle espressioni -> %5.5f secondi\n", dblTempiCalcolo);

return 0;
}


Questi sono dunque i miei tempi:

Problema 1: file piccolo
http://www.guidealgoritmi.it/images/ImgForums/Contest06ATempi1Bis.jpg
Problema 1: file grosso
http://www.guidealgoritmi.it/images/ImgForums/Contest06ATempi2Bis.jpg




Problema 2: file piccolo
http://www.guidealgoritmi.it/images/ImgForums/Contest06BTempi1Bis.jpg
Problema 2: file grosso
http://www.guidealgoritmi.it/images/ImgForums/Contest06BTempi2Bis.jpg


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


e da QUI (http://www.guidealgoritmi.it/public/Vin68Contest06.zip) è possibile scaricare i sorgenti in C.

Invito quelli che hanno già postato il codice(e, ovviamente, anche tutti gli altri) a fare altrettanto.
Oltre al codice, ai tempi e alla macchina sulla quale sono stati misurati, invito inoltre a postare una spiegazione esauriente dell'algoritmo utilizzato ;)

P.S. Il file di output va comunque prodotto e, ricordo a tutti, che la posizione delle espressioni sul file di output deve coincidere con quella del file di input: la prima espressione in output deve essere la prima del file di input, etc. Occhio, dunque, quando si utilizzano algoritmi paralleli. ;)

[VICIUS]

Giusto.
Ma io faccio in fretta stavolta (seconda parte)
Leggo le righe poi ciclo su ciascuna riga.
La spacco negli elementi, splittando sullo spazio.
Ciclo sugli elementi considerandoli in ordine.
Quando trovo un numero lo inserisco in uno stack di numeri.
Quando trovo un operatore, a seconda che sia binario o unario, scodo dallo stack 1 o 2 valori, eseguo l'operazione e riinserisco nello stack.
Al termine della riga dovrebbe esserci un solo valore nello stack, lo scodo e lo restuisco.
Un altro stack di stringhe si occupera' di tenere la rappresentazione delle operazioni come la conosciamo noi. Al termine di ogni operazione, al posto di inserire il risultato inserisco l'operazione come la leggiamo noi.
Processo le righe in parallelo su multithread, e scrivo nel file in regione critica (necessario), cosi' mentre un thread e' occupato con l'I/O, l'altro puo' continuare a calcolare.
Abbiamo avuto la stessa idea anche se io non mi sono spinto così oltre e non ho implementato il parallelismo. Ho preferito una soluzione più semplice ed elegante. :)

class Fixnum
def /(operand)
self.to_f / operand.to_f
end
end

class String
def binary_operator?
true if self =~ /[+\-*\/^]/
end
def unary_operator?
true if self == '~'
end
end

start = Time.now
File.open('espressioni3.txt', 'r') do |file|
file.gets # ignora la prima riga
while rpn_expression = file.gets
stack = Array.new
tokens = rpn_expression.chop.split
tokens.each do |t|
if t.binary_operator?
b = stack.pop
a = stack.pop
stack.push "(#{a} #{t} #{b})"
elsif t.unary_operator?
stack.push "#{t}#{stack.pop}"
else
stack.push t
end
end
infix = stack.pop.gsub('~','-')
eval(infix.gsub('^', '**'))
#puts "#{infix} = #{eval(infix.gsub('^', '**'))}"
end
end
puts "Ci ho messo #{(Time.now - start).to_s} secondi"

[Vincenzo1968]

Implementarlo a mano è abbastanza stupido visto che ci sono dei tool che generano i parser (semi) automaticamente per questi linguaggi (vedi Yacc e Lex).

Ho in precedenza specificato che, chi desidera utilizzare un tool apposito, può tranquillamente farlo.

Qui:

http://www.hwupgrade.it/forum/showthread.php?t=1830226

si trovano un paio di esempi: uno in Bison(linguaggio C) e un altro in ANTLR(linguaggio Python) ;)

[Vincenzo1968]

Abbiamo avuto la stessa idea anche se io non mi sono spinto così oltre e non ho implementato il parallelismo. Ho preferito una soluzione più semplice ed elegante. :)
...


Vicius Ciao,

puoi modificare il codice in modo da stampare a video i tempi così come ho specificato nel mio post precedente?

[Vincenzo1968]

Ho in precedenza specificato che, chi desidera utilizzare un tool apposito, può tranquillamente farlo.

Qui:

http://www.hwupgrade.it/forum/showthread.php?t=1830226

si trovano un paio di esempi: uno in Bison(linguaggio C) e un altro in ANTLR(linguaggio Python) ;)

P.S. I tools menzionati sono potentissimi ma, quando si tratta di implementare un parser semplicissimo, come quello di questo contest, penso sia preferibile farlo a mano ;)

[VICIUS]

Vicius Ciao,

puoi modificare il codice in modo da stampare a video i tempi così come ho specificato nel mio post precedente?
Intendi separando tempi di lettura del file ed esecuzione? Il mio fa praticamente tutto insieme se vuoi posso mettere il tempo totale infondo e togliere l'output a video ma potresti ottenere la stessa cosa con time.

[Vincenzo1968]

Intendi separando tempi di lettura del file ed esecuzione? Il mio fa praticamente tutto insieme se vuoi posso mettere il tempo totale infondo e togliere l'output a video ma potresti ottenere la stessa cosa con time.

Si, ma ti chiedo(invito rivolto a tutti) la cortesia di stampare i tempi da codice :)

[cdimauro]

Io ho scritto un pvt a repne e me lo sono fatto spiegare. Credo che lei abbia deciso di non partecipare più a nessun contest.
Sarebbe interessante, piuttosto, se qualche guru decidesse di partecipare al contest dandoci un bell'esempio di come si deve programmare.

Dal contest 7:

Il codice a cui si riferisce il guru è appunto quello di repne.

Se il guru si degnasse di partecipare attivamente, potremmo avere degli esempi di codice da appendere al muro di fronte al letto e da guardare ogni mattina ripetendoci: così si programma(accanto a quelli di repne che, a detta del guru, costituiscono un esempio di come NON si programma).

:)
Il codice del guru in questione lo trovi qui (http://www.hwupgrade.it/forum/forumdisplay.php?f=112). :)

Per chi è ha tempo consiglio di leggere questa sottosezione, perché c'è veramente tanto da imparare.
Geniale come al solito :O

Quelle due gsub sono il vero collo di bottiglia del mio esempio. Togliendo quella che sostituisce 1/2 si guadagnano due secondi per il file piccolo e quattro in quello grande. Se poi imbroglio ed uso sed per sostituire ^ con ** posso togliere anche l'ultima gsub e risparmio un altro secondo per il file piccolo e due su quello grande.
:rotfl: Comunque ho visto la tua soluzione: semplice ed elegante. Complimenti. :)

[VICIUS]

Si, ma ti chiedo(invito rivolto a tutti) la cortesia di stampare i tempi da codice :)
Ok. Ho modificato il codice di prima. ;)

[Vincenzo1968]

Il codice del guru in questione lo trovi qui (http://www.hwupgrade.it/forum/forumdisplay.php?f=112). :)

Per chi è ha tempo consiglio di leggere questa sottosezione, perché c'è veramente tanto da imparare.

:rotfl: Comunque ho visto la tua soluzione: semplice ed elegante. Complimenti. :)

eh no! Poiché il guru ha sentenziato sul codice postato da repne, avrei gradito una sua soluzione a quel contest(non dico una soluzione che si avvicini a quei tempi; mi accontenterei anche se impiegasse il doppio del tempo) :)

[Vincenzo1968]

Ok. Ho modificato il codice di prima. ;)

Perfetto, grazie ;)

Vedi se puoi fare in modo di calcolare solo i tempi di esecuzione dell'algoritmo escludendo quelli di scrittura sul file di output. Dai un'occhiata al codice che ho postato io ;)

[Vincenzo1968]

Ok. Ho modificato il codice di prima. ;)

Vicius,

non viene prodotto nessun file di output. Il file va comunque prodotto anche se escludiamo i tempi di scrittura nel file dal calcolo.
Vedi come mi sono arrangiato io col mio codice e, se non ti è chiaro qualche passaggio, chiedi pure ;)

edit : ho tolto il commento da puts e ho rediretto l'output su file:


...
(9.81 + (-(63.31 ^ (4 ^ 0.5)) - -13.87)) = -3984.4761
(58.83 + (-(73.66 ^ (4 ^ 0.5)) - 62.21)) = -5429.1756
((((-41.71 * 93.33) / (1 + -68.75)) - 5) / (-4.3 + (72.61 ^ (1 / 2)))) = 12.4274703570629
Ci ho messo 25.641 secondi


Fai in modo di escludere i tempi di scrittura: il risultato finale dovrebbe migliorare di molto ;)

[cdimauro]

eh no! Poiché il guru ha sentenziato sul codice postato da repne, avrei gradito una sua soluzione a quel contest(non dico una soluzione che si avvicini a quei tempi; mi accontenterei anche se impiegasse il doppio del tempo) :)
Non era in discussione la partecipazione o meno al contest. Il codice di Fran lo trovi in quella sezione se il tuo interesse era vedere in che modo programma uno del suo spessore.

Se poi vuoi polemizzare è un altro discorso, ma non credo sia permesso dal regolamento.

Chiuso OT.

[Vincenzo1968]

Non era in discussione la partecipazione o meno al contest. Il codice di Fran lo trovi in quella sezione se il tuo interesse era vedere in che modo programma uno del suo spessore.

Se poi vuoi polemizzare è un altro discorso, ma non credo sia permesso dal regolamento.

Chiuso OT.

Giustamente, uno di quello spessore non s'abbassa a fornire codice d'esempio. Si limita a sentenziare sul codice altrui :)

Chiuso OT.

Spiego come mi sono arrangiato col mio codice per escludere i tempi di scrittura dal file.

La funzione Calcola ha tre parametri:
- pArray è l'array contenente le espressioni lette dal file di input.
- szFileName è il nome del file di output
- dblTempi è un puntatore a una variabile di tipo double; lo utilizzo per restituire il tempo impiegato per il calcolo.

La funzione è implementata come segue:

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

for (k = 0; k < pArray->size; k++)
{
c_start = clock();

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);

c_end = clock();

*dblTempi += (double)(c_end - c_start) / CLOCKS_PER_SEC;

fwrite(szResult, strlen(szResult), 1, fp);
}

fclose(fp);
...


Inizializzo, prima del ciclo for, la variabile dblTempo a 0.
All'inizio del ciclo for prendo il valore di c_start. Subito prima di chiamare fwrite(che scrive l'output sul file), prendo il valore di c_end e calcolo il tempo impiegato.
A ogni ciclo, la variabile dblTempi viene incrementata col tempo corrente.

Ho utilizzato una soluzione simile anche per calcolare i tempi del secondo problema.

[cdimauro]

Giustamente, uno di quello spessore non s'abbassa a fornire codice d'esempio. Si limita a sentenziare sul codice altrui :)

Chiuso OT.
Il codice sai dove trovarlo, e t'ho passato anche il link.

E' chiaro che, a questo punto, il tuo unico fine era la polemica.

[Vincenzo1968]

Il codice sai dove trovarlo, e t'ho passato anche il link.

E' chiaro che, a questo punto, il tuo unico fine era la polemica.

Coma al solito hai capito tutto. Il mio intento era la polemica fine a sè stessa. Bravo. Dov'è, nel link che hai indicato, la soluzione al contest 7?

[gugoXX]

Dai basta con le polemiche.
Se si programma da soli si puo' fare quello che si vuole.
Anche in un contest. Diciamo che la leggibilita' sarebbe almeno gradita, senno' e' inutile postare, ma mi sembra che Repne stesse cercando di rendere il tutto un po' piu' leggibile.

L'ordine delle espressioni in output dev'essere quello del file di input. Dovresti cercare di coordinare i risultati ottenuti dai vari thread.

Questo p.es. non era nelle specifiche.
E non e' neppure chiaro perche' ci dovrebbe essere l'ordine, per la natura stessa del problema.

Comunque vabbe'. Fatto

Read Time: 115ms
Calc Time: 965ms
----------
Tot Time: 1080ms




class Program
{
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
string toread = @"C:\temp\espressioni4.txt";
string[] vals = File.ReadAllLines(toread);
long p1 = sw.ElapsedMilliseconds;

Exec xx=new Exec();
int ln = vals.Length;

StreamWriter swr = new StreamWriter(toread + ".output");

var calcs = from c in vals.Skip(1).AsParallel(ParallelQueryOptions.PreserveOrdering)
let t = xx.Executor(c)
select string.Format("{0} = {1}", t.pars, t.res);

calcs.ForAll(t =>
{
lock (swr)
{
swr.WriteLine(t);
}
}
);
long p2 = sw.ElapsedMilliseconds;


//
//Parallel.For(1, ln, t =>
//{
// string str = vals[t];
// var rs = xx.Executor(str);
// string towrite=string.Format("{0} = {1}", rs.pars, rs.res);
// lock (swr)
// {
// swr.WriteLine(towrite);
// }
//});
//swr.Close();


sw.Stop();
long pr = sw.ElapsedMilliseconds;


Console.WriteLine("Read Time: {0}ms", p1);
Console.WriteLine("Calc Time: {0}ms", p2 - p1);
Console.WriteLine("----------");
Console.WriteLine("Tot Time: {0}ms", p2);

Console.ReadKey();
}

public class Exec
{
NumberFormatInfo nfi;
char[] splitter;

public Exec()
{
nfi = new NumberFormatInfo();
nfi.NumberDecimalSeparator = ".";
splitter = new char[] { ' ' };
}

public Result Executor(string str)
{
Stack<string> stamp = new Stack<string>();
Stack<double> ds = new Stack<double>();
string[] spls = str.Split(splitter, StringSplitOptions.RemoveEmptyEntries);

int len = spls.Length;
for (int t = 0; t < len; t++)
{
string sing = spls[t];
bool ex = false;
if (sing.Length == 1)
{
char ch = sing[0];
double d1, d2;
string el1, el2;
switch (ch)
{
case '+':
d2 = ds.Pop();
d1 = ds.Pop();
ds.Push(d1 + d2);
el2 = stamp.Pop();
el1 = stamp.Pop();
stamp.Push(string.Format("({0}+{1})", el1, el2));
ex = true;
break;
case '-':
d2 = ds.Pop();
d1 = ds.Pop();
ds.Push(d1 - d2);
el2 = stamp.Pop();
el1 = stamp.Pop();
stamp.Push(string.Format("({0}-{1})", el1, el2));
ex = true;
break;
case '/':
d2 = ds.Pop();
d1 = ds.Pop();
ds.Push(d1 / d2);
el2 = stamp.Pop();
el1 = stamp.Pop();
stamp.Push(string.Format("({0}/{1})", el1, el2));
ex = true;
break;
case '*':
d2 = ds.Pop();
d1 = ds.Pop();
ds.Push(d1 * d2);
el2 = stamp.Pop();
el1 = stamp.Pop();
stamp.Push(string.Format("({0}*{1})", el1, el2));
ex = true;
break;
case '^':
d2 = ds.Pop();
d1 = ds.Pop();
ds.Push(Math.Pow(d1, d2));
el2 = stamp.Pop();
el1 = stamp.Pop();
stamp.Push(string.Format("({0}^{1})", el1, el2));
ex = true;
break;
case '~':
d1 = ds.Pop();
ds.Push(-d1);
el1 = stamp.Pop();
stamp.Push(string.Format("-{0}", el1));
ex = true;
break;
}
}
if (!ex)
{
double pars = double.Parse(sing,nfi);
ds.Push(pars);
stamp.Push(sing);
}
}
double res = ds.Pop();
string notaz = stamp.Pop();
return new Result(notaz,res);
}
}

public struct Result
{
public string pars;
public double res;

public Result(string p_pars, double p_res)
{
pars = p_pars;
res = p_res;
}
}
}

[Vincenzo1968]

...
Questo p.es. non era nelle specifiche.
E non e' neppure chiaro perche' ci dovrebbe essere l'ordine, per la natura stessa del problema.
...


Perchè questo contest l'ho postato io e, dunque, qui comando io :Perfido:

No, a parte gli scherzi, anche se non l'ho specificato all'inizio, mi pare una buona idea; quantomeno per controllare i risultati senza andare a cercarsi le espressioni corrispondenti nei due file in posizioni diverse ;)

[Vincenzo1968]

Gugo,

questa linea di codice:


var calcs = from c in vals.Skip(1).AsParallel(ParallelQueryOptions.PreserveOrdering)


dà il seguente messaggio di errore:

error CS0103: The name 'ParallelQueryOptions' does not exist in the current context


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;
using System.Threading;
using System.Globalization;


:confused:

[gugoXX]

Gugo,

questa linea di codice:


var calcs = from c in vals.Skip(1).AsParallel(ParallelQueryOptions.PreserveOrdering)


dà il seguente messaggio di errore:

error CS0103: The name 'ParallelQueryOptions' does not exist in the current context
:confused:

Nuova libreria uscita a luglio.
E' ancora in Beta la PLinq :D
Si vede che mica solo tu spacchi i cabbasissi.

[Vincenzo1968]

Nuova libreria uscita a luglio.
E' ancora in Beta la PLinq :D
Si vede che mica solo tu spacchi i cabbasissi.


Passami il link per scaricarla.

P.S. meglio dire scassare, e non spaccare, i cabasisi. Mi meraviglio di te: non lo sai che per essere considerati dei buoni programmatori bisogna conoscere alla perfezione la lingua inglese e il dialetto siciliano? :O

[cdimauro]

Coma al solito hai capito tutto. Il mio intento era la polemica fine a sè stessa. Bravo. Dov'è, nel link che hai indicato, la soluzione al contest 7?
Rileggiti (http://www.hwupgrade.it/forum/showpost.php?p=24764071&postcount=117):
Io ho scritto un pvt a repne e me lo sono fatto spiegare. Credo che lei abbia deciso di non partecipare più a nessun contest.
Sarebbe interessante, piuttosto, se qualche guru decidesse di partecipare al contest dandoci un bell'esempio di come si deve programmare.

Dal contest 7:

Il codice a cui si riferisce il guru è appunto quello di repne.

Se il guru si degnasse di partecipare attivamente, potremmo avere degli esempi di codice da appendere al muro di fronte al letto e da guardare ogni mattina ripetendoci: così si programma(accanto a quelli di repne che, a detta del guru, costituiscono un esempio di come NON si programma).

:)
Da notare la parte in grassetto. Se vuoi degli esempi di codice su come programma un guru ti è sufficiente il link che ho postato prima.

Se vuoi altro, cerchi soltanto polemica. Sic et simpliciter.

C'è poco da capire: basta leggere e masticare un po' di italiano e di logica.

[Vincenzo1968]

Passami il link per scaricarla.

P.S. meglio dire scassare, e non spaccare, i cabasisi. Mi meraviglio di te: non lo sai che per essere considerati dei buoni programmatori bisogna conoscere alla perfezione la lingua inglese e il dialetto siciliano? :O

Ohé Gugo,

in alternativa possiamo fare così: compila la tua applicazione sia a 32 che a 64 bit e passami gli eseguibili via e-mail che metto un link per il download nel mio sito. Se sei d'accordo ti mando un pvt con l'indirizzo.

[Vincenzo1968]

Rileggiti (http://www.hwupgrade.it/forum/showpost.php?p=24764071&postcount=117):

Da notare la parte in grassetto. Se vuoi degli esempi di codice su come programma un guru ti è sufficiente il link che ho postato prima.

Se vuoi altro, cerchi soltanto polemica. Sic et simpliciter.

C'è poco da capire: basta leggere e masticare un po' di italiano e di logica.

cristo santo,

e dunque sto tizio, solo perché ha scritto quel giochino, si può permettere di additare il codice di un utente come qualcosa da appendere al muro, vicino al letto, a esempio di come NON si programma? Senza fornire una sua versione di come invece si dovrebbe programmare?
Ma andate a cagare, tu e lui pure :)

[cdimauro]

Mi sfugge il motivo per cui dovrebbe participare al contest per poterlo fare.

In buona sostanza, dovresti spiegare per quale motivo partecipare al contest debba essere condizione necessaria.

Logica alla mano, s'intende. Ma son curioso di vedere quale motivazione porterai a sostegno della tua tesi.

Per quanto riguarda Fran, non ha realizzato soltanto quel giochino (che è frutto della collaborazione di tanta gente; ho partecipato anch'io, ad esempio): http://www.appuntidigitali.it/2505/come-nasce-un-videogioco-bug-fixing-3/#comment-8741

[cionci]

Ma andate a cagare, tu e lui pure :)
Cerchiamo di mantenere i toni nei limiti di una discussione civile. Ora posso capire che la cosa messa così possa essere anche vista in tono scherzoso, ma è troppo facilmente fraintendibile, quindi sospensione di 2 gg.

Se posso dire la mia: sono d'accordo sul fatto che in un contest uno possa programmare più o meno come vuole. Poi chiaramente ognuno quando programma si mette i propri paletti, io stesso cerco di mantenere comunque una certa leggibilità del codice e uso ampiamente nomi autoesplicativi. Ma non è detto che sia una regola valida per tutti. Finché, appunto, si programma da soli, si può scrivere più o meno come si vuole, proprio perché chi dovrà mettere mano al codice sarò solo l'autore stesso.
Ricordiamoci anche le prestazioni: ottimizzare il codice comporta chiaramente una diminuzione della leggibilità (anche per il solo aumento della quantità di codice), sempre che si voglia andare oltre i limiti imposti dalle strutture preesistenti del linguaggio. Con l'ottimizzazione in teoria ci si può spingere anche all'assembly, la cui leggibilità è praticamente nulla.

Ora per carità, con questo non voglio dire che la leggibilità del codice di repne non fosse migliorabile: con qualche funzione e qualche nome di variabile esplicativo sarebbe sicuramente stato possibile ottenere codice più leggibile a, quasi, parità di prestazioni, ma se lei ci capisce ha sicuramente facoltà di scrivere codice come più la aggrada.

Sinceramente non credo nemmeno che sia questo il posto adatto per porre dubbi sulla leggibilità e sulla qualità del codice scritto da qualcuno dei partecipanti.

[cdimauro]

Concordo. Quando lavoravo quasi esclusivamente in assembly praticamente tutto il codice era disseminato di commenti, anche riga per riga.

Qui poi ho imparato a scrivere codice più leggibile, e tu ne sai qualcosa. :D

In un contest comunque, a parte la leggibilità, a mio avviso credo che ci siano un altro paio di requisiti da rispettare.

Il codice postato dovrebbe girare su qualunque macchina, altrimenti come lo si fa a testare sulla propria?

Altra cosa, non dovrebbe essere emesso nessuno warning (per i linguaggi i cui compilatori lo prevedono): codice "pulito", come si suol dire.

[gugoXX]

Concordo. Quando lavoravo quasi esclusivamente in assembly praticamente tutto il codice era disseminato di commenti, anche riga per riga.

Qui poi ho imparato a scrivere codice più leggibile, e tu ne sai qualcosa. :D

In un contest comunque, a parte la leggibilità, a mio avviso credo che ci siano un altro paio di requisiti da rispettare.

Il codice postato dovrebbe girare su qualunque macchina, altrimenti come lo si fa a testare sulla propria?

Altra cosa, non dovrebbe essere emesso nessuno warning (per i linguaggi i cui compilatori lo prevedono): codice "pulito", come si suol dire.

Io aderisco alla campagna 0 warning. :D

Qualunque macchina cosa vuol dire?
Se io sviluppo in C# non posso che chiedere che la macchina abbia il .NET Framework, che potrebbe anche non avere.

Oppure librerie esterne per il C++ per esempio? Tipo le ultime estensioni?

Oppure per ma la PLinq. E' una libreria, che fra poco entrera' nel .NET Framework... per ora la allego. Il programma non sara' solo l'eseguibile, ma anche la libreria a corredo (che alla fine e' una DLL che ti puoi portare a spasso fino a che non sara' integrata).

[cdimauro]

E' chiaro che il sistema dovrà avere tutte le librerie necessarie.

Nello specifico mi riferivo al fatto che se scrivo un'applicazione in C o C++, e utilizzo le librerie standard (tanto per fare un esempio, ma il concetto si estende anche ad altre librerie esterne), devo poterla compilare ed eseguire su qualunque macchina che metta a disposizione compilatore e librerie. ;)

[rеpne scasb]

■

[banryu79]

OT:
Repne, a me dispiace molto che tu sia "andata via"; anche io aspettavo la spiegazione del tuo algoritmo.
Ti esorto a non prendertela per le altrui opinioni sul tuo codice, e anche se la cosa ti ha offeso ti prego di non punire tutti gli altri interessati a causa di uno soltanto.
Ciao.

[DanieleC88]

Altra cosa, non dovrebbe essere emesso nessuno warning (per i linguaggi i cui compilatori lo prevedono): codice "pulito", come si suol dire.
Io aderisco alla campagna 0 warning. :D
Sono dei vostri! Ormai da anni, tra le flags di GCC, nelle mie compilazioni sono sempre presenti -W -Wall. :D
Ci manca solo -Werror... :p

[VICIUS]

Vicius,

non viene prodotto nessun file di output. Il file va comunque prodotto anche se escludiamo i tempi di scrittura nel file dal calcolo.
Vedi come mi sono arrangiato io col mio codice e, se non ti è chiaro qualche passaggio, chiedi pure ;)
Ho visto le immagini senza output nel tuo messaggio così ho pensato bene di approfittarne e togliere del tutto l'output ora correggo subito.

Fai in modo di escludere i tempi di scrittura: il risultato finale dovrebbe migliorare di molto ;)
Potrei di certo fattorizzare tutto in varie fasi: lettura del file, conversione in infix, valutazione e output ma il codice si allungherebbe molto e diventerebbe più contorto, la ram occupata sarebbe molta e secondo me sarebbe anche più lento.

Ultima versione:
class Fixnum
def /(operand)
self.to_f / operand.to_f
end
end

class String
def binary_operator?
true if self =~ /[+\-*\/^]/
end
def unary_operator?
true if self == '~'
end
end

start = Time.now
File.open('output.txt', 'w') do |output|
File.open('espressioni3.txt', 'r') do |file|
file.gets # ignora la prima riga
while rpn_expression = file.gets
stack = Array.new
tokens = rpn_expression.chop.split
tokens.each do |t|
if t.binary_operator?
b = stack.pop
a = stack.pop
stack.push "(#{a} #{t} #{b})"
elsif t.unary_operator?
stack.push "#{t}#{stack.pop}"
else
stack.push t
end
end
infix = stack.pop.gsub('~','-')
output.puts "#{infix} = #{eval(infix.gsub('^', '**'))}"
end
end
end
puts "Ci ho messo #{(Time.now - start).to_s} secondi"

[cdimauro]

Questa affermazione e' falsa.
http://it.wikipedia.org/wiki/Implicazione

[banryu79]

Posto i risultati di Vincenzo1968 (da parte sua):
----------------------------------------

Sono riuscito a ridurre i tempi da più di due secondi a 0.625 secondi(Problema 2, file grosso).

Questi sono i tempi per il problema 2 sul file grosso:
http://www.guidealgoritmi.it/images/ImgForums/Contest06BTempi2Tris.jpg

Il codice sorgente può essere scaricato da QUI (http://www.guidealgoritmi.it/public/Contest06BFinale.zip).

All'inizio avevo pensato di utilizzare il parallelismo con OpenMP che è una libreria multipiattaforma pienamente supportata dal visual studio(ma anche dalla maggior parte degli altri compilatori).

OpenMP:

http://openmp.org/wp/

http://en.wikipedia.org/wiki/OpenMP

http://msdn.microsoft.com/en-us/library/tt15eb9t.aspx

Alla fine, per evitare problemi di sincronizzazione dei thread, ho preferito utilizzare la semplicissima tecnica del loop unrolling

P.S. ho anche eliminato tutte le variabili globali che utilizzavo nella versione precedente. Adesso sono locali alle funzioni che le utilizzano.

[cionci]

Questa affermazione e' falsa.
In quali termini ? Mi sembra un'affermazione che, diciamo, ti sostiene :confused:

[banryu79]

Da parte di Vincenzo1968:
-------------------------

Credevo di avere risolto col loop unrolling e, invece, in output dà soltanto un quarto delle espressioni.:doh:
Dunque rimane valida la mia prima versione(coi relativi tempi).
Proverò a utilizzare OpenMP

[rеpne scasb]

■

[cionci]

1) Tizio chiede un timer ad alta precisione in DOS, io posto una possibile soluzione, e un post piu' in basso uno dei soliti commenta: "Si pero' non e' compatibile con Windows XP".
2) Tizio chiedeun aiuto precisando di programmare in C con Borland, io lo aiuto con un esempio in C in cui utilizzo la funzione getchar, e un post piu' in basso "qualcuno" commenta: "Il codice non e' portabile".

Ma queste sono situazioni che ci sono per tutti e non solo per te.
Non è un problema tuo, ma visto che siamo su un forum anche le altre persone sono libere di parlare. Magari possono anche dire cavolate oppure fraintendere le motivazioni per l'adozione di alcune soluzioni nel tuo codice: basta rispondere e chiarire.

Se il personaggio X dice al personaggio Y "guarda il tuo codice fa schifo" io non posso sospenderlo, non c'è alcuna infrazione del regolamento. In tutta la discussione precedente hai avuto un solo post "contro" di te ed io ho richiesto subito di tornare in topic dicendo che non era il posto adatto per parlare di qualità di codice. Cosa devo fare di più ?

[gugoXX]

Io ho sicuramente un pessimo carattere, ma quando frequento un forum "tento" di aiutare/consigliare, per quello che posso

Posso dare la mia critica, che vuole essere assolutamente costruttiva e sincera?

Se vuoi aiutare fallo, e fallo veramente, te ne saremmo grati davvero. Postare codice offuscato non serve ad aiutare nessuno.
Vuoi farlo per farti vedere? Per quanto MI riguarda passeresti non solo dalla parte dell'inutilita', ma anche dell'antipatia.
Detta questa, se nonostante tutto continuerai con il codice offuscato semplicemente non lo guardero', e avrai aiutato quindi "almeno" una persona in meno.
Il non sapere scrivere un codice leggibile e' una mancanza, non un pregio.
Tu potresti valutarla una mancanza da poco. Per quanto mi riguarda quando faccio colloqui e' una mancanza da molto.

Per continuare, sempre in modo costruttivo per anche altri,
Uno dei requisiti di maggiore importanza per il codice che mi viene passato al lavoro e' quello della leggibilita'.
C'e' addirittura una persona della QA (quality assurance) che fa solo questo. Legge il codice prima che venga approvato per essere spostato nel repository e se c'e' qualcosa che non capisce, puo' essere scritto meglio o addirittura e' anche solo male formattato, lo rifiuta al mittente.
E tutti i miei collaboratori lo sanno. Avere un pezzo di codice che quando si deve manutenere occorre spendere mezza giornata (se non di piu') a capire come funziona e' deleterio.
Costa poco scrivere un buon codice, e ce la si puo' fare con tutti i linguaggi, anche con il C e l'assembly.
Un buon codice inoltre non deve neppure essere commentato. Si commenta da solo. (A meno che l'initerlocutore a cui si voglia spiegare non sappia programmare o non conosca il linguaggio).
E ancora, se proprio occorre mettere un commento perche' un codice non e' chiaro, occorre scrivere PERCHE' si e' scritta una determinata parte, e non COSA sta facendo quella parte. Altrimenti significa semplicemente che e' di nuovo scritta male.
Il linguaggio di programmazione e' proprio cio' che serve ad un uomo per descrivere in modo quanto piu' naturale possibile cio' che intende far fare ad alla macchina. Ma se le parole che si usano sono comprensive solo per una macchina, tanto vale scrivere direttamente nel linguaggio che la macchina usa.

Queste sarebbero buone norme di gruppi di programmazione (e neanche tutte).
E mi piacerebbe pensare che anche noi qui siamo un gruppo.

[DanieleC88]

Tornando in tema di contest... qualcuno ha mica fatto un upload dei risultati interi del primo problema? Vorrei fare un confronto col mio programma (che, finalmente, sembra funzionare), ma mi insospettiscono i "nan" che ricevo; anche se quelli che ho visto finora sono in corrispondenza di esponenti frazionari con numeri negativi alla base, quindi radici di numeri negativi, il che sarebbe accettabile.

Per ora posto i tempi ottenuti sulla mia macchina.
Sul file piccolo:
[jmc@mordor Contest 6]$ time "./bin/Debug/Contest 6" espressioni/espressioni1.txt > output/output1.txt

real 0m4.593s
user 0m4.260s
sys 0m0.127s
E sul file grande:
[jmc@mordor Contest 6]$ time "./bin/Debug/Contest 6" espressioni/espressioni2.txt > output/output2.txt

real 0m12.386s
user 0m9.033s
sys 0m0.457s

Dopo magari inserisco le stampe dei tempi direttamente dal codice. Non posto ancora il codice perché è un mezzo casino, ho voglia di rifinirlo un po'. E poi voglio assicurarmi che sia corretto. :D

EDIT: come non detto! Ho visto ora che Vincenzo li aveva già caricati sul suo sito gli output... Magari li confronto un po', per il codice se ne riparlerà comunque domani. Notte a tutti. ;)

[Vincenzo1968]

Ohé,

nessun'altra soluzione da proporre?
Daniele, a che punto sei?
Gugo, manca la tua soluzione al punto 1.
Elche, manca la tua al punto 2.
Cionci, mancano le tue soluzioni a entrambi i punti(mi comunica il Mons. che tu, in quanto moderatore, ti aggiudichi automaticamente il sambenito con la semplice non partecipazione a un contest ;)).

http://www.hwupgrade.it/forum/customavatars/avatar246559_1.gif

[malocchio]

Concordo con il fatto che il non scrivere codice leggibile è una mancanza.

Secondo me non è vero che un buon codice non ha bisogno di commenti: dietro alle istruzioni ci sta un algoritmo che può non essere espresso efficacemente dal linguaggio.

Secondo me il C è un linguaggio oggettivamente meno leggibile degli altri, sarà che non conosco le funzioni standard.

E' un piacere poter vedere un programma così efficiente in un contest (anche se sono noob, qui), però la poca leggibilità e la complessità dell'algoritmo fanno sì che la maggior parte degli utenti non riesca a capire come funziona. Spesso anche a causa della pigrizia degli stessi utenti.

[Vincenzo1968]

Ehm, malocchio...

vuoi definitivamente affossarlo questo contest? Vogliamo scatenare un'altra azzuffatina?
Ho capito, anche da altri tuoi interventi, in altri thread, che il linguaggio C non ti piace. Opinione leggittima e sacrosanta, per carità.
Ora che, legittimamente, hai espresso la tua opinione, ti piacerebbe partecipare al contest, fornendo una tua soluzione, nel linguaggio che più ti aggrada?

Ciao :)

[DanieleC88]

Daniele, a che punto sei?
Io ho corretto il problema che avevo trovato prima, ma siccome sono stato praticamente fuori casa per oltre due giorni devo ancora finire il tutto. :stordita:
Ovvero, c'è un segmentation fault che non mi torna, devo indagare sulla causa e poi mando.

ciao ;)

[malocchio]

Ehm, malocchio...

vuoi definitivamente affossarlo questo contest? Vogliamo scatenare un'altra azzuffatina?
Ho capito, anche da altri tuoi interventi, in altri thread, che il linguaggio C non ti piace. Opinione leggittima e sacrosanta, per carità.
Ora che, legittimamente, hai espresso la tua opinione, ti piacerebbe partecipare al contest, fornendo una tua soluzione, nel linguaggio che più ti aggrada?

Ciao :)

HiHi, appena ho tempo e ispirazione. Ora sono in ballo con molte altre cose. Voi lo sapevate che fossero così ambigui i float in CSS? :stordita:
Cercherò di mordermi le dita appena mi viene in mente una tirata contro il C.

Vi seguo sempre con piacere, saluti :D

[rеpne scasb]

■

[Kralizek]

Sto tentando un approccio alla soluzione del problema di tipo non convenzionale. Ho escogitato la seguente congettura che ho quasi terminato di dimostrare, e trasformare in lemma (1):

"Sia data l'espressione aritmetica E=N(1)C(1)N(2)C(2)N(3)C(3)N(4)...C(n)N(n+1) con N(1...4...n+1) numeri e C(1...3...n) operatori. Indipendentemente dagli operatori C(1...3), E e' sempre trasformabile in M(1)D(1)M(2)D(2)M(3)C(4)(N(5)...C(n)N(n+1), con D(1...2) operatori aritmetici e M(1...3) numeri".

La dimostrazione si estrinseca in 27 casi particolari. Se riesco nella dimostrazione saro' in grado di risolvere il problema in modo assai spedito.

P.S. se qualcuno conosce la dimostrazione della congettura (1), mi farebbe cosa gradita se fosse in grado di riportarmela o nel caso di fornirmi un qualche riferimento.

scusate l'OT, posso chiederti che studi hai fatto? Ad occhio direi Informatica pura, ma non vorrei dire una cazzata! Comunque complimenti... è sempre un piacere leggere i tuoi post ed il tuo codice (se a mente fresca, altrimenti è una delle 7 piaghe d'egitto per quanto impegnativo!)

[Vincenzo1968]

HiHi, appena ho tempo e ispirazione. Ora sono in ballo con molte altre cose. Voi lo sapevate che fossero così ambigui i float in CSS? :stordita:
Cercherò di mordermi le dita appena mi viene in mente una tirata contro il C.

Vi seguo sempre con piacere, saluti :D

Ciao Malocchio,

non intendevo certo dire che non devi esprimere le tue opinioni. Ma, come faceva notare Vicius, in un altro contest, non appena si dà di tocco a una critica su un linguaggio, i thread diventano chilometrici(dai un'occhiata QUI (http://www.hwupgrade.it/forum/showthread.php?t=1796495), per esempio). Qui cerchiamo invece di concentrarci sulle soluzioni ai problemi proposti.

Ciao ;)

P.S. Ho scritto leGGittima, con due G. Indosserò il sambenito per un anno intero. :cry:

[Vincenzo1968]

Sto tentando un approccio alla soluzione del problema di tipo non convenzionale. Ho escogitato la seguente congettura che ho quasi terminato di dimostrare, e trasformare in lemma (1):

"Sia data l'espressione aritmetica E=N(1)C(1)N(2)C(2)N(3)C(3)N(4)...C(n)N(n+1) con N(1...4...n+1) numeri e C(1...3...n) operatori. Indipendentemente dagli operatori C(1...3), E e' sempre trasformabile in M(1)D(1)M(2)D(2)M(3)C(4)(N(5)...C(n)N(n+1), con D(1...2) operatori aritmetici e M(1...3) numeri".

La dimostrazione si estrinseca in 27 casi particolari. Se riesco nella dimostrazione saro' in grado di risolvere il problema in modo assai spedito.

P.S. se qualcuno conosce la dimostrazione della congettura (1), mi farebbe cosa gradita se fosse in grado di riportarmela o nel caso di fornirmi un qualche riferimento.

Bene! Un altro capitolo del libro Matematica: problemi e soluzioni in C
:D

[DanieleC88]

Rieccomi, non mi sono dimenticato del contest, ho solo dovuto lottare per un paio di giorni con una febbre che non voleva scendere dai 40°. Finalmente ho riacquistato un po' della lucidità necessaria a dare un'occhiata al mio codice e l'ho trovato più schifoso di quanto ricordassi. :D
Più che altro ho paura che per come l'ho impostato dall'inizio il parsing non possa venire corretto: faccio un ultimo paio di tentativi, e se non va vi mando lo stesso il codice, in questo contest ho fatto pena. :p

[DanieleC88]

Ok, totale fallimento, mi fermo qui e mi arrendo. :p
Alcune soluzioni sono esatte, altre un po' sballate, parecchie sono semplicemente "nan"... :eek:

Allego l'archivio e mi ritiro nella vergogna. :D
ciao ;)

[Vincenzo1968]

Ok, totale fallimento, mi fermo qui e mi arrendo. :p
Alcune soluzioni sono esatte, altre un po' sballate, parecchie sono semplicemente "nan"... :eek:

Allego l'archivio e mi ritiro nella vergogna. :D
ciao ;)

Ma no, ma quale vergogna? Potevi fare benissimo come gli altri: ritirarti senza dire né ai né bai, né scu né passiddà :fiufiu:

Ciao ;)

[DanieleC88]

Adesso che ho interrotto la mia soluzione, che era diventata incasinata e scorretta, faccio un rewind a pagina 3 e mi studio il tuo metodo. ;)

[Vincenzo1968]

Adesso che ho interrotto la mia soluzione, che era diventata incasinata e scorretta, faccio un rewind a pagina 3 e mi studio il tuo metodo. ;)

Puoi vedere anche qui:

http://epaperpress.com/oper/index.html

Ci sono esempi in C, C++, VB e... K :confused:

:D

[DanieleC88]

Forte! Mo me lo leggo. Che cacchio è K? :asd:

[Vincenzo1968]

up

:bimbo: