[vari] Contest 6 - Parsing

[Vincenzo1968]

Goldorack e Daniele,

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

[Vincenzo1968]

Originariamente inviato da VICIUS

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]

Originariamente inviato da goldorak

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:


file grosso:


Il codice in C può essere scaricato da QUI

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


file grosso:

[||ElChE||88]

Sbaglio o ci sono delle divisioni per zero?

Per ora i miei tempi sono:


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

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

Originariamente inviato da ||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?

Ciao Elche,

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

[||ElChE||88]

Originariamente inviato da Vincenzo1968

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)



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]

Originariamente inviato da ||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?

Ho controllato il file di output:



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]

Originariamente inviato da Vincenzo1968

Ho controllato il file di output:



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

Originariamente inviato da ||ElChE||88

GCC.
Ora provo con Visual Studio.

Edit: Provato con VS e funziona bene. Azzo fa GCC?
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 per scaricare i file di output del mio programma per il secondo problema.

[Vincenzo1968]

Ok,

ho aggiornato il link al sorgente. 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]

Originariamente inviato da Vincenzo1968

So che ti sto scassando i cabasisi

Veramente mi diverto.

Originariamente inviato da Vincenzo1968

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

Originariamente inviato da ||ElChE||88

Ma che azzo fa?
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.

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]

Originariamente inviato da Vincenzo1968

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

[Vincenzo1968]

Originariamente inviato da ||ElChE||88

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!

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