- Stato
Esatto, io ho una stringa che contiene un'espressione aritmetica e mi interessa elaborarla per poter ottenere il risultato.
Si tratta di individuare nella stringa gli ascii dal 48 al 57, convertirli in interi, individuare nella stringa gli operatori (*, +, -, /) e fare il calcolo... giusto? Non è per nulla facile. Soprattutto se il codice deve contemplare espressioni di lunghezza arbitraria... Io provo, in ogni caso mi interessa sapere come va a finire.
- - - Updated - - -
Rettifico, questo problema di parsing è fuori dalla mia portata e se c'è qualcuno in questo forum in grado di risolverlo con un codice intelligente, ottimizzato ed efficace... ecco, se c'è può diventare il maestro di tutti!
Penso che si possa risolvere in qualche modo con le Regex.
Il problema sta che in ASM non ho idea di come si possano implementare, in ogni caso si potrebbe fare un ragionamento del genere:
Non so se sia un ragionamento che fila ma potresti fare una MatchCollection delle parentesi EG: "\((.+)\)" e scorri la collection al contrario.
Per i calcoli puoi fare un ciclo per dare la precedenza (si è molto greed ma non mi è venuto in mente altro).
Senza le Regex il discorso è lo stesso, solo che diventa più complicato trovare le parentesi manualmente.
Il problema sta che in ASM non ho idea di come si possano implementare, in ogni caso si potrebbe fare un ragionamento del genere:
Non so se sia un ragionamento che fila ma potresti fare una MatchCollection delle parentesi EG: "\((.+)\)" e scorri la collection al contrario.
Per i calcoli puoi fare un ciclo per dare la precedenza (si è molto greed ma non mi è venuto in mente altro).
Senza le Regex il discorso è lo stesso, solo che diventa più complicato trovare le parentesi manualmente.
In python potresti utilizzare il ciclo for per ogni carattere e trasformarlo in un integer. Se ti dà errore, non è un numero (e poi vai a verificare cosa sia), mentre se non da errore il numero viene trasformato in integer e poi fai le operazioni. (ho fatto una cosa simile non molto tempo fa)
Se l'errore in è in fase di compilazione (come penso che sia) allora non credo che questa soluzione sia applicabile...
- - - Updated - - -
Come si convertono i char di operazione in operatori veri e propri?
Ultima modifica:
Le parentesi pensavo di gestirle in modo ricorsivo: quando trovo una parentesi aperta inizio a contarle (+1 per quelle aperte e -1 per quelle chiuse) e quando torno a 0 riapplico l'algoritmo di risoluzione sulla sottostringa che parte dopo la prima parentesi e termina prima dell'ultima parentesi trovata, che sarebbe quella che effettivamente chiude la prima parentesi aperta.
Ovviamente per semplificare sto dando per scontato che la stringa in input sia corretta.
La parte più difficile è tutto il resto. Il tuo ragionamento non mi è chiarissimo.
Trasformare da caratteri a numeri e capire se ho a che fare con un simbolo non è difficile nemmeno in assembly.
Sostanzialmente si tratta di scorrere carattere per carattere e verificare se il carattere attuale è compreso tra '0' e '9', se è così si avvia una routine di riconoscimento numerico altrimenti si da per scontato che è un simbolo.
Il problema è trovare un modo semplice per gestire la precedenza degli operatori e per effettuare i calcoli.
La sostanza è questa:
Codice:
if(carattere == '+')
ris = num_left + num_right;Questo l'avevo visto, ma non l'ho capito più di tanto. Tu l'hai capito?
Comunque ieri ho cercato un algoritmo di parsing in giro per internet (se ritrovo il nome lo posto) e ho provato ad applicarlo in C. Con ~300 linee di codice ho qualcosa di abbastanza funzionante (mi da ancora problemi il - inteso come segno di negazione, come sottrazione funziona).
Se trovate qualche algoritmo semplice o se vi viene in mente qualcosa fatemi sapere, prima di scriverlo in assembly provo a scriverlo in C e vedo quanto è effettivamente semplice.
EDIT:
Ok, la prova che ho fatto io mi da ben più di un problema XD
Fatico a gestire le istruzioni a pari priorità.
[MENTION=156155]St3ve[/MENTION]
Credo che i casi da contemplare siano talmente tanti... se poi pensi di tradurlo in ASM... è sconfortante![:\](/forum/data/assets/smilies/mhhae.gif "Mhhae :\")
In ogni caso credo che sia sufficiente l'analisi delle parentesi, nel senso che da sinistra a destra si scorre fino a trovare la parentesi, quando essa viene chiusa si esegue l'algoritmo solo su quella, si sostituisce nell'espressione il risultato e così via...
In base alla posizione in cui si trovano, cioè partendo dalla sinistra quando si verifica la condizione: "trovata parentesi aperta e trovata parentesi chiusa" si salvano le posizioni e si riempie con ciò che ci sta in mezzo, si risolve quello e si va a sostituire nella stringa... Più che altro è una domanda eh! Non voglio assolutamente insegnare niente a nessuno, solo, che te ne pare?
Credo che i casi da contemplare siano talmente tanti... se poi pensi di tradurlo in ASM... è sconfortante
In ogni caso credo che sia sufficiente l'analisi delle parentesi, nel senso che da sinistra a destra si scorre fino a trovare la parentesi, quando essa viene chiusa si esegue l'algoritmo solo su quella, si sostituisce nell'espressione il risultato e così via...
PHP:
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
string exp;
vector<char> cast;
int i=0;
cout<<"inserisci espressione: "; cin>>exp;
while(i<exp.size())
{
if(exp[i]=='(' || exp[i]==')')
cast.push_back(exp[i]);
i++;
}
cout<<exp<<endl<<endl;
for(i=0; i<cast.size(); i++)
cout<<cast[i]<<" ";
cout<<endl;
return 0;
}In base alla posizione in cui si trovano, cioè partendo dalla sinistra quando si verifica la condizione: "trovata parentesi aperta e trovata parentesi chiusa" si salvano le posizioni e si riempie con ciò che ci sta in mezzo, si risolve quello e si va a sostituire nella stringa... Più che altro è una domanda eh!
Non voglio assolutamente insegnare niente a nessuno, solo, che te ne pare?
Ultima modifica:
@Simur Birkoff
Da quanto ho capito è un po' il concetto che ho cercato di esprimere qui:
Che codato diventa una roba di questo tipo:
Se intendevi qualcos'altro prova a rispiegarti.
Comunque ogni tentativo d'aiuto, per stupido che sia, è ben accetto.
Non fatevi scrupoli a scrivere boiate, magari in un modo o nell'altro tornano utili!
Se è proprio troppo difficile passo ad altro, ma non mollo senza averci manco provato.
What?!
Comunque mi interessa anche solo un ragionamento per risolvere un problema simile, poi ad implementarlo ci penso io. Lo farei prima in C (che rimane comunque molto low-level) per vedere se fila liscio, se è tutto ok poi passo all'assembly.
Da quanto ho capito è un po' il concetto che ho cercato di esprimere qui:
Che codato diventa una roba di questo tipo:
Codice:
if(expression[it] == '(')
{
++brackets; // inizialmente brackets = 0, trovo una parentesi e diventa 1
for(it2 = it+1; it < strlen(expression); ++it2) // it indica la posizione della stringa in cui ho incontrato il carattere '('
{
if(expression[it2] == '(') // se si apre un'altra parentesi, me lo segno
++brackets;
else if(expression[it2] == ')') // se si chiude una parentesi, me lo segno
--brackets;
if(brackets == 0) // se la parentesi che si è chiusa era la corrispondente alla prima
{
sub_expr = malloc(it2 - it); // creo una sottostringa (sotto-espressione)
sub_expr = memcpy(sub_expr, expression+it+1, it2-it-1); // e gli ficco dentro il contenuto delle parentesi
sub_expr[it2-it-1] = '\0';
float_stack_push(&stack_num, evaluate(sub_expr)); // calcolo ricorsivamente (in realtà sono già dentro a evaluate) il risultato della sotto espressione
it = it2; // mi trovavo alla posizione contenente '(', ora salto alla posizione dove c'è ')'
break; // ho trovato la parentesi che mi chiude la '(' che avevo incontrato, stoppo il for
}
}
}Se intendevi qualcos'altro prova a rispiegarti.
Comunque ogni tentativo d'aiuto, per stupido che sia, è ben accetto.
Non fatevi scrupoli a scrivere boiate, magari in un modo o nell'altro tornano utili!
Credo che i casi da contemplare siano talmente tanti... se poi pensi di tradurlo in ASM... è sconfortante
Se è proprio troppo difficile passo ad altro, ma non mollo senza averci manco provato.
What?!
Comunque mi interessa anche solo un ragionamento per risolvere un problema simile, poi ad implementarlo ci penso io. Lo farei prima in C (che rimane comunque molto low-level) per vedere se fila liscio, se è tutto ok poi passo all'assembly.
[MENTION=156155]St3ve[/MENTION]
Ok steve l'algoritmo generale mi sebra chiaro, ciò che è difficile è tradurlo...
Eppure manca qualcosa
Ok steve l'algoritmo generale mi sebra chiaro, ciò che è difficile è tradurlo...
- trovare tutte le parentesi e le loro posizioni nella stringa
- verificare il contenuto della parentesi più interna
- risolvere
- 1) tradurre la stringa in intero dove ci sono numeri cercando ascii eccetera eccetera
- 2) il rimanente sono sicuramente operazioni dato che non sono né parentesi né numeri
- sostituire il risultato al posto della parentesi nella stringa... -> nuova stringa
- loop
Eppure manca qualcosa
Ah ok, chiaro. Immaginavo fosse un errore di battitura.
Se il C# ha qualche magheggio che te lo fa risolvere in 5 secondi (tipo il python) lascia perdere, sarebbe inutile, se invece hai in mente un algoritmo per la risoluzine provaci pure.
Mi basterebbe capire bene cosa devo fare, poi a tradurlo in codice ci penso io. L'importante è che si riesca a trovare un algoritmo semplice, se è troppo contorto diventa troppo difficile tradurlo in assembly.
@St3ve
Ok steve l'algoritmo generale mi sebra chiaro, ciò che è difficile è tradurlo...
- trovare tutte le parentesi e le loro posizioni nella stringa
- verificare il contenuto della parentesi più interna
- risolvere
- 1) tradurre la stringa in intero dove ci sono numeri cercando ascii eccetera eccetera
- 2) il rimanente sono sicuramente operazioni dato che non sono né parentesi né numeri
- sostituire il risultato al posto della parentesi nella stringa... -> nuova stringa
- loop
Eppure manca qualcosa
A me invece sfugge ancora l'algoritmo generale. Non ho ancora capito cosa fare, quel "risolvere" è troppo astratto.
Per ora sto usando una variante di questo:
Che però non funziona come dovrebbe, sospetto che sia proprio un problema dell'algoritmo. Non ho problemi con roba tipo 100/5*2/3+(90/2*3-10)+10^2+5! ma se provo con 1-5*3+2*3+4*21-100/5*2+2 non funziona (il problema capita per colpa di quel +2 finale).
Sono abbastanza fiducioso di avere un algoritmo in testa... In serata te lo mostro! Ovviamente so qual é il livello che ci separa ma io la mia te la do comunque
[MENTION=156155]St3ve[/MENTION]
PHP:
/* questo è per il "risolvere" le singole parentesi... l'ho fatto col più e col meno ma si più facilmente riscrivere
* col * e il /
* per la potenza è un'altra storia... vedi se è adeguato...
* non è neanche completo ma è la linea generale, almeno quella a cui pensavo io*/
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int conv_str(string);
int main()
{
/*diamo per scontato che nella parentesi da analizzare le operazioni abbiano tutte la medesima priorità, e
* che le priorità siano invece definite tramite le parentesi stesse in modo più rigido.
* anzi che 2+5*3-3/1 l'utente dovrà 2+(5*3)-(3/1)
* un piccolo sforzo per l'utente, un grandissimo vantaggio per noi! Nonchè la maggiore facilità di gestione
* degli errori.
* sacrificio accettabile... per me almeno! :P */
string esp, tmp;
vector<char> op;
vector<int> vals;
int ris, i;
cout<<"espressione = "; cin>>esp;
tmp=esp; //lavoro prima sui numeri con tmp senza rovinare esp e poi con esp sugli operatori
for(i=0; i<tmp.size(); i++)
{
if(tmp[i]=='+' || tmp[i]=='-')
{
vals.push_back(conv_str(tmp.substr(0, i)));
tmp=tmp.substr(i+1, (tmp.size()-1));
i=0; //questa riga mi è costata venti minuti di duro ragionamento! :|
}
}
vals.push_back(conv_str(tmp)); // perchè l'ultimo valore resta escluso... poco male :)
//ora abbiamo un vector con i numeri, inseriamo gli operatori nell'ordine giusto e il gioco è fatto!
for(i=0; i<esp.size(); i++)
{
if(esp[i]=='+')
op.push_back('+');
else if(esp[i]=='-')
op.push_back('-');
} //ora abbiamo un vettore con le operazioni
i=0;
/*do
{
if(op[op.size()-i]=='+')
ris=vals[vals.size()-1]+vals[vals.size()-2];
else if(op[op.size()-i]=='-')
ris=vals[vals.size()-1]-vals[vals.size()-2];
vals.erase(vals.end()-1);
vals.push_back(ris);
vals.erase(vals.end()-2);
i++;
} while(vals.size()>1);
* qui mi sono bloccato... non so se ti può essere utile ma se riesci a combinare i due vector per risolvere
* parentesi di pari priorità e riesci a estrarre di volta il volta le parentesi più esterne dall'espressione iniziale
* e a sostituire per ogni parentesi il suo risultato hai fatto... no?
* questo è quello che per ora ho scritto... domani mi ci metto di nuovo.*/
cout<<ris<<endl;
return 0;
}
int conv_str(string s)
{
int num;
if(s.size()==1)
num=s[0]-48;
else if(s.size()==2)
num=((s[0]-48)*10)+(s[1]-48);
else if(s.size()==3)
num=((s[0]-48)*100)+((s[1]-48)*10)+(s[2]-48);
else if(s.size()==4)
num=((s[0]-48)*1000)+((s[1]-48)*100)+((s[2]-48)*10)+(s[3]-48);
return num;
}In ogni caso per tradurlo in codice ASM puoi fermare il compilatore prima che generi l'eseguibile...
Per il g++ credo che sia
g++ -S nomefile.cpp -o nomefile
No?
Per il g++ credo che sia
g++ -S nomefile.cpp -o nomefile
No?
Ultima modifica:
Grazie mille per l'aiuto! Ti do un paio di consigli visto che ci stai provando pure tu.
Il ragionamento sul push_back alla linea 41 ("perchè l'ultimo valore resta escluso") si può fare e non si può fare: in teoria 1*(2+3) dovrebbe essere una stringa valida e con quel sistema si leggerebbe 3) come un numero unico (amenochè lo step di *rimuovere* le parentesi non si faccia prima) e la tua funzione conv_str lo interpreta effettivamente come tale.
Tralasciando il fatto che per ora il tuo codice non legge le parentesi, secondo me la funzione per separare i numeri dalle operazioni dovrebbe essere più indipendente. Il tuo ragionamento è quello di scansare le operazioni, il numero è la parte che rimane, ma secondo me è più semplice cercare i numeri.
Quello che intendo io è qualcosa di simile:
Codice:
int len = 0;
for(i = 0; i <= tmp.size(); i++)
{
if(tmp[i] >= '0' && tmp[i] <= '9')
len++;
else if(len > 0)
{
vals.push_back(conv_str(tmp.substr(i-len, len))); // di fatto non modifico tmp
len = 0;
}
}La funzione conv_str funziona meglio così:
Codice:
int conv_str(string s)
{
int num = 0;
for(size_t it = 0; it < s.length(); it++) // rimane completamente indipendente dalla lunghezza della stringa
{
num *= 10; // inizialmente non fa niente (0*10=0), agli step successivi shifta a sinistra il numero in base 10 e fa posto
num += s[it] - '0'; // al numero successivo. s[it] - '0' serve per convertire da ASCII a int un numero formato da una cifra.
} // esempio: s="123" -> 0*0=0 0+1=1 -> 1*10=10 10+2=12 -> 12*10=120 120+3=123
return num;
}Comunque ci siamo gente, ora il mio programmino riesce a mangiarsi mostri come questo:
Codice:
>> (3+(5.412*2.123-5.12^4+(5!-7!))+10-2*44*(12+3!^2))/3^3!
expression: (3+(5.412*2.123-5.12^4+(5!-7!))+10-2*44*(12+3!^2))/3^3!
sub_expr = 3+(5.412*2.123-5.12^4+(5!-7!))+10-2*44*(12+3!^2)
sub_expr = 5.412*2.123-5.12^4+(5!-7!)
sub_expr = 5!-7!
sub_expr = 12+3!^2
result: -13.452270
Sarebbe per un progetto scolastico, se gli porto lì il codice generato da un compilatore se ne accorgono (senza contare che glielo dovrei commentare oralmente). Comunque non mi serve nemmeno in assembly x86, mi serve in assembly MIPS.
Molto bene! Se hai tutto il sorgente potresti postaro? Se vuoi eh!Grazie mille per l'aiuto! Ti do un paio di consigli visto che ci stai provando pure tu.
Il ragionamento sul push_back alla linea 41 ("perchè l'ultimo valore resta escluso") si può fare e non si può fare: in teoria 1*(2+3) dovrebbe essere una stringa valida e con quel sistema si leggerebbe 3) come un numero unico (amenochè lo step di *rimuovere* le parentesi non si faccia prima) e la tua funzione conv_str lo interpreta effettivamente come tale.
Tralasciando il fatto che per ora il tuo codice non legge le parentesi, secondo me la funzione per separare i numeri dalle operazioni dovrebbe essere più indipendente. Il tuo ragionamento è quello di scansare le operazioni, il numero è la parte che rimane, ma secondo me è più semplice cercare i numeri.
Quello che intendo io è qualcosa di simile:
Codice:int len = 0; for(i = 0; i <= tmp.size(); i++) { if(tmp[i] >= '0' && tmp[i] <= '9') len++; else if(len > 0) { vals.push_back(conv_str(tmp.substr(i-len, len))); // di fatto non modifico tmp len = 0; } }
La funzione conv_str funziona meglio così:
Codice:int conv_str(string s) { int num = 0; for(size_t it = 0; it < s.length(); it++) // rimane completamente indipendente dalla lunghezza della stringa { num *= 10; // inizialmente non fa niente (0*10=0), agli step successivi shifta a sinistra il numero in base 10 e fa posto num += s[it] - '0'; // al numero successivo. s[it] - '0' serve per convertire da ASCII a int un numero formato da una cifra. } // esempio: s="123" -> 0*0=0 0+1=1 -> 1*10=10 10+2=12 -> 12*10=120 120+3=123 return num; }
Comunque ci siamo gente, ora il mio programmino riesce a mangiarsi mostri come questo:
La prima riga è l'input, copiarla su google per credere al risultatoCodice:>> (3+(5.412*2.123-5.12^4+(5!-7!))+10-2*44*(12+3!^2))/3^3! expression: (3+(5.412*2.123-5.12^4+(5!-7!))+10-2*44*(12+3!^2))/3^3! sub_expr = 3+(5.412*2.123-5.12^4+(5!-7!))+10-2*44*(12+3!^2) sub_expr = 5.412*2.123-5.12^4+(5!-7!) sub_expr = 5!-7! sub_expr = 12+3!^2 result: -13.452270
Sarebbe per un progetto scolastico, se gli porto lì il codice generato da un compilatore se ne accorgono (senza contare che glielo dovrei commentare oralmente). Comunque non mi serve nemmeno in assembly x86, mi serve in assembly MIPS.
- - - Updated - - -
E il codice che ho postato doveva essere una parte del codice completo, e lavorare solo su stringhe epurate da parentesi in precedenza!
Ultima modifica:
No, non è in fase di compilazione.
Siccome io e l'assembly non andiamo d'accordo ti spiego come farlo in python poi vedi te.
Codice:
espressione=input("Scrivi l'espressione: ")
for elem in espressione:
try:
int(elem)
print(elem + " è un numero!")
except:
print(elem + " non è un numero!")Come puoi vedere dallo screen funziona:
No, non è in fase di compilazione.
Siccome io e l'assembly non andiamo d'accordo ti spiego come farlo in python poi vedi te.
Codice:espressione=input("Scrivi l'espressione: ") for elem in espressione: try: int(elem) print(elem + " è un numero!") except: print(elem + " non è un numero!")
Come puoi vedere dallo screen funziona:
Ok, non sapevo di questa cosa in python! In effetti funziona, in C++ il discorso è differente! Non credo che un'operazione del genere sia fattibile... Ovviamente potrei sbagliare. [MENTION=156155]St3ve[/MENTION]
Certo che si può fare, un po' meno pulito rispetto al python, ma il senso è lo stesso:
Codice:
string esp;
cout<<"espressione = ";
cin>>esp;
size_t pos = 0;
int i;
while(esp.length())
{
try
{
i = stoi(esp, &pos);
cout << "e' il numero = " << i << endl;
esp = esp.substr(pos);
}
catch(...)
{
cout << "non e' un numero" << endl;
esp = esp.substr(pos-1);
}
}
Codice:
espressione = 12pippo34ciccio56
e' il numero = 12
non e' un numero
non e' un numero
non e' un numero
non e' un numero
non e' un numero
e' il numero = 34
non e' un numero
non e' un numero
non e' un numero
non e' un numero
non e' un numero
non e' un numero
e' il numero = 56Visto che è un progetto scolastico, anche se in realtà mi servirebbe solo l'assembly, preferisco non postarlo per adesso. Quando lo consegno rifinisco un po' il sorgente (magari potrei aggiungerci anche le variabili tipo: 7+(i=12*8)+i^2 oppure in un'espressione calcoli una variabile che poi riusi nell'espressione dopo) e lo posto a scopo didattico.Molto bene! Se hai tutto il sorgente potresti postaro? Se vuoi eh!
Devo dire che sto progettino, almeno finché sono sul C, mi sta appassionando.
Bene! E' un ottimo progetto, postalo pure in un secondo momento non c'è nessun problema, basta che prima o poi mi mostrerai questa roba
E' qualcosa di davvero complesso, molto più di quello che sembra a primo impatto... provai a scrivere un solver per lo studio di funzione che implementava più o meno lo stesso algoritmo ma senza successo... quindi se potessi prendere spunto dal tuo lavoro sarebbe magnifico!
Bel lavoro St3ve! Non che sia una sorpresa! E grazie di aver condiviso con noi! 
- Stato