[c] calcolatrice in notazione polacca inversa

[Bart10]

Salve, qualcuno saprebbe aiutarmi per compilare un codice in linguaggio c:
Una calcolatrice che riceve da input e stampa in notazione polacca inversa un'espressione e ne calcola il risultato
P.s le operazione da eseguire sono esclusivamente +- / *, il proggramma termina digitando ctrl z

[VICIUS]

Se non ci dici di più è difficile aiutarti. Cosa hai provato a fare?

[Bart10]

Scusatemi, questo programma converte un'espressione infissa in una in notazione polacca. Il sistema rimane quello di leggere carattere per carattere l'espressione Ed eseguire le operazioni rispettando alcune regole come ad esempio svolgere prima moltiplicazione e divisione e poi addizzione e sottrazione


#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define MAX_STRINGA 30
#define NON_PRESENTE -1
int matr_regole[6][7]={{4,1,1,1,1,1,5},
* * * * * *{2,2,2,1,1,1,2},
* * * * * *{2,2,2,1,1,1,2},
* * * * * *{2,2,2,2,2,1,2},
* * * * * *{2,2,2,2,2,1,2},
* * * * * *{5,1,1,1,1,1,3}};
char vett_car[7+1]="%+-*/()";

typedef struct dato_s
{
* *char carat;
* *struct dato_s *prossimo;
}dato;
typedef enum {FALSE,TRUE} boolean;

dato *stack_pointer,*punt_insert,*punt_extract;
char str[MAX_STRINGA];
int indice,colonna,riga,regola;
boolean finito,corretto;
char carat_stack;

int leggi_str(char stringa[]);
void push(dato **p_stack_pointer, char carattere);
void pop(dato **p_stack_pointer, char *carattere);
void queue(dato **p_insert, dato **p_extract, char carattere);
int cerca_posizione(char carattere);
void guarda_cima_stack(dato *p_stack_pointer, char *carattere);
void stampa(dato *punt);
void inizializza (dato **p_stack_pointer, dato **p_punt_insert, dato **p_punt_extract);

main()
{
* *clrscr();
* *while(leggi_str(str)!=EOF)
* *{
* * * *inizializza (&stack_pointer,&punt_insert,&punt_extract);
* * * *push(&stack_pointer,str[0]);
* * * *indice=1;
* * * *finito=FALSE;
* * * *while(!finito)
* * * *{
* * * * * *if((colonna=cerca_posizione(str[indice]))==NON_PRESENTE)
* * * * * *{
* * * * * * * *queue(&punt_insert,&punt_extract,str[indice]);
* * * * * * * *indice++;
* * * * * *}
* * * * * *else
* * * * * *{
* * * * * * * *guarda_cima_stack(stack_pointer,&carat_stack);
* * * * * * * *riga=cerca_posizione(carat_stack);
* * * * * * * *regola=matr_regole[riga][colonna];
* * * * * * * *switch(regola)
* * * * * * * *{
* * * * * * * * * *case 1:
* * * * * * * * * *{
* * * * * * * * * * * *push(&stack_pointer,str[indice]);
* * * * * * * * * * * *indice++;
* * * * * * * * * *}
* * * * * * * * * *break;
* * * * * * * * * *case 2:
* * * * * * * * * *{
* * * * * * * * * * * *pop(&stack_pointer,&carat_stack);
* * * * * * * * * * * *queue(&punt_insert,&punt_extract,carat_stack);
* * * * * * * * * *}
* * * * * * * * * *break;
* * * * * * * * * *case 3:
* * * * * * * * * *{
* * * * * * * * * * * *pop(&stack_pointer,&carat_stack);
* * * * * * * * * * * *indice++;
* * * * * * * * * *}
* * * * * * * * * *break;
* * * * * * * * * *case 4:
* * * * * * * * * *{
* * * * * * * * * * * *corretto=TRUE;
* * * * * * * * * * * *finito=TRUE;
* * * * * * * * * *}
* * * * * * * * * *break;
* * * * * * * * * *case 5:
* * * * * * * * * *{
* * * * * * * * * * * *corretto=FALSE;
* * * * * * * * * * * *finito=TRUE;
* * * * * * * * * *}
* * * * * * * *}
* * * * * *}
* * * *}
* * * *if(corretto)
* * * * * *stampa(punt_extract);
* * * *else
* * * * * *printf("Espressione non correttamente bilanciata\n");
* *}
}


void inizializza (dato **p_stack_pointer, dato **p_punt_insert, dato **p_punt_extract)
{
dato *p_aux, *p_prec;

p_aux = *p_stack_pointer;
while (p_aux!=NULL)
* *{
* *p_prec = p_aux;
* *p_aux = (*p_prec).prossimo;
* *free (p_prec);
* *}
*p_stack_pointer=NULL;
*p_punt_insert=*p_punt_extract=NULL;
}




int leggi_str(char stringa[])
{
* *int indice;
* *char carat;
* *stringa[0]='%';
* *indice=1;
*******printf("Introduci l'espressione infissa (CTRL+Z per terminare): ");
* *while(((carat=getchar())!='\n')&&(carat!=EOF))
* *{
* * * *stringa[indice]=carat;
* * * *indice++;
* *}
* *stringa[indice]='%';
* *stringa[indice+1]='\0';
* *return(carat);
}

void push(dato **p_stack_pointer, char carattere)
{
* *dato *p_corr;
* *p_corr=(dato *)malloc(sizeof(dato));
* *(*p_corr).carat=carattere;
* *(*p_corr).prossimo=*p_stack_pointer;
* **p_stack_pointer=p_corr;
}

void pop(dato **p_stack_pointer, char *carattere)
{
* **carattere=(**p_stack_pointer).carat;
* **p_stack_pointer=(**p_stack_pointer).prossimo;
}

void queue(dato **p_insert, dato **p_extract, char carattere)
{
* *dato *p_corr;
* *p_corr=(dato *)malloc(sizeof(dato));
* *(*p_corr).carat=carattere;
* *(*p_corr).prossimo=NULL;
* *if(*p_insert==NULL)
* *{
* * * **p_insert=p_corr;
* * * **p_extract=p_corr;
* *}
* *else
* *{
* * * *(**p_insert).prossimo=p_corr;
* * * **p_insert=p_corr;
* *}
}

int cerca_posizione(char carattere)
{
* *int indice=0;
* *while((vett_car[indice]!=carattere)&&(indice<strlen(vett_car)))
* * * *indice++;
* *if (indice==strlen(vett_car))
* * * *indice = NON_PRESENTE;
* *return(indice);
}

void guarda_cima_stack(dato *p_stack_pointer, char *carattere)
{
* **carattere=(*p_stack_pointer).carat;
}

void stampa(dato *punt)
{
* *dato *p_temp;
* *p_temp=punt;
* *while(p_temp!=NULL)
* *{
* * * *putchar((*p_temp).carat);
* * * *p_temp=(*p_temp).prossimo;
* *}
* *putchar('\n');
}

[sottovento]

Scusa l'osservazione banale, ma il software da te pubblicato e' pieno di asterischi, i quali non hanno motivo di esistere. Beh, alcuni devono rimanere, altri no.
Prima di tutto occorrerebbe avere il codice ripulito dai caratteri estranei: posso aiutarti a farlo ma immagino che esista da qualche parte una versione gia' pronta per l'uso. Infatti, la sensazione e' che gli asterischi siano stato inseriti da un programma di conversione di testo da un formato (per esempio, Unix) ad un altro (per esempio, Windows) ed abbia rimpiazzato i tab con detto asterisco. Succede.

Se cosi' fosse, si potrebbe provare una nuova conversione e si risparmierebbe tempo. Se non e' possibile, si deve fare, ovviamente, a mano.

Una volta ripulito il codice, riuscirai QUASI a compilarlo: il codice e' quasi tutto C standard, a parte clrscr() e qualcos'altro che sicuramente mi e' scappato

[Bart10]

Si gli asterischi sostituiscono i tab, ma il codice che ho postato e' solo un esempio di traformazione da notazione Infissa a notazione polacca inversa. A me servirebbe un codice che dato da tastiera un'espressione in notazione polacca inversa, con le sole 4 operazioni fomdamentali, ne calcola il risultato

[sottovento]

E' un classico problema che richiede uno stack per la risoluzione.
Il problema e' piuttosto semplice, e puoi trovare una buona traccia per risolverlo qui:
http://stackoverflow.com/questions/2722889/help-understanding-reverse-polish-notation-for-homework-assignment
(ovviamente se googli un po' potresti trovare gia' tutto fatto, ma permettimi di consigliarti di provare a risolverlo, se si tratta di un esercizio)

Ti riporto la traccia:


while (there's a token available) {
token = get_the_token
if (token is known operator) {
get the number of values from stack this operation requires (usually two); fail if stack doesn't have enough
perform operation on values
push result on the stack
}
else if (token is valid value) {
push it on the stack
}
else {
show error: invalid input
}
}
show result remaining on stack



Si gli asterischi sostituiscono i tab, ma il codice che ho postato e' solo un esempio di traformazione da notazione Infissa a notazione polacca inversa. A me servirebbe un codice che dato da tastiera un'espressione in notazione polacca inversa, con le sole 4 operazioni fomdamentali, ne calcola il risultato

[:.Blizzard.:]

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

[sottovento]

Avendo un po' di tempo libero, ho fatto una piccola implementazione, spero che ti possa servire.

Alcune osservazioni:
- i commenti sono inglese (deformazione professionale);
- lo stack ha dimensione fissa (hey! E' solo un esempio!) quindi ogni volta che inserisco qualcosa devo controllare che ci sia sufficiente spazio;
- ho provato solo un paio di espressioni, quelle che sono indicate nel main;
- ho usato un compilatore C++ (i.e. Visual Studio sotto Windows), quindi potrebbero essere necessari degli aggiustamenti nel caso non abbia usato solo il C puro. Poca roba.

Ovviamente la funzione di interesse e'
bool evaluate(char *expression, double *result)

a cui devi passare l'espressione in formato rpn e restituisce il valore in result, nel caso non si verifichino errori.
Il valore di ritorno della funzione e' un booleano: se true, allora tutto e' andato per il meglio; altrimenti c'e' un errore (per esempio, lessicale o di sintassi nell'espressione, oppure lo stack e' pieno)


#include "stdafx.h"
#include <ctype.h>

#define TOKEN_NUMBER 1
#define TOKEN_OPERATION 2

#define STACK_SIZE 100

typedef struct
{
int tokenType; // i.e. TOKEN_NUMBER or TOKEN_OPERATION
double val; // current read number
char operation; // Operation to be performed
}Token;

char *getNextToken(char *expr, Token *token, bool &err)
{
char ch;
double val = 0.0;
bool found = false;

// skip blanks
while ((*expr != '\0') && isspace(*expr))
expr++;
err = false;
while ((ch=*expr++) != '\0')
{
switch (ch)
{
case '+':
case '-':
case '*':
case '/':
token->tokenType = TOKEN_OPERATION;
token->operation = ch;
return expr;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
val *= 10.0;
val += ch - '0';
found = true;
break;
default:
if (!isspace(ch) || !found) // characters other than operations/digits/blanks are not accepted; moreover, we should find at least one digit!
{
err = true;
return NULL;
}
token->tokenType = TOKEN_NUMBER;
token->val = val;
return expr;
}
}
/* We reach here in case last character before termination was a number */
if (ch == '\0' && !found)
return NULL;
token->tokenType = TOKEN_NUMBER;
token->val = val;
return expr;
}

/* Implementation of fixed-size stack */
Token stack[STACK_SIZE];
int currentStackSize = 0;

bool push(Token token)
{
if (currentStackSize < STACK_SIZE)
memcpy(&stack[currentStackSize++], &token, sizeof(Token));
return (currentStackSize <= STACK_SIZE);
}

bool pop(Token *token)
{
if (currentStackSize > 0)
memcpy(token, &stack[--currentStackSize], sizeof(Token));
return (currentStackSize >= 0);
}

/* Core function */
bool evaluate(char *expression, double *result)
{
Token token;
Token op1;
Token op2;
bool err;
double res;

while (((expression = getNextToken(expression, &token, err)) != NULL) && !err)
{
if (token.tokenType == TOKEN_NUMBER)
err = !push(token);
else
{
err = !pop(&op1);
err = err || !pop(&op2);
if (err) break;
switch (token.operation)
{
case '+': res= op1.val + op2.val; break;
case '-': res= op2.val - op1.val; break;
case '*': res= op1.val * op2.val; break;
case '/': res= op2.val / op1.val; break;
default:
err = true;
break;
}
token.val = res;
token.operation = TOKEN_NUMBER;
err = !push(token);
}
}
if (!err) err = (currentStackSize != 1);
if (!err) err = !pop(&token);
if (!err)
*result = token.val; // current read number

return !err;
}

int _tmain(int argc, _TCHAR* argv[])
{
//char *expression = "5 10 2 * +";
char *expression = "10 2 * 4 5 - + 2 /";
double result;

bool res = evaluate(expression, &result);
if (!res)
{
printf ("Errore valutazione espressione!\n");
}
else
{
printf ("Risultato: %f\n", result);
}

return 0;
}

[Bart10]

Grazie mill siete stati esaustivi, grazie soprattutto a sottovento appena posso visiono il tuo codice pero' cosi a primo acchitto le variabili globali non mi piacciono proprio!!!
P.s. Un altra dritta che mi servirebbe e far ciclare il programma finche non viene digitato ctrl z

[sottovento]

Grazie mill siete stati esaustivi, grazie soprattutto a sottovento appena posso visiono il tuo codice pero' cosi a primo acchitto le variabili globali non mi piacciono proprio!!!
P.s. Un altra dritta che mi servirebbe e far ciclare il programma finche non viene digitato ctrl z

Hai perfettamente ragione per le variabili globali. Considera che le due variabili globali (lo stack) non sono funzionali all'algoritmo. Basta un taglia e incolla per metterle locali.

Riguardo ctrl-z... beh, quella e' proprio programmazione spicciola, no?

[Bart10]

Ho provato il tuo programma ma mi da parecchi errori!!!

Riguardo ctrl z bhe avrai capito che non sono un drago e riesco a terminare un ciclo solo tramite un simbolo!!!

Per quanto riguarda il programma l'algoritmo grazie al vostro aiuto lo stracapito ma il problema e' che non riesco a tradurlo in codice c!!

[sottovento]

Ho provato il tuo programma ma mi da parecchi errori!!!

Riguardo ctrl z bhe avrai capito che non sono un drago e riesco a terminare un ciclo solo tramite un simbolo!!!

Per quanto riguarda il programma l'algoritmo grazie al vostro aiuto lo stracapito ma il problema e' che non riesco a tradurlo in codice c!!

Ovviamente l'ho provato prima di postarlo; quindi eventuali errori immagino siano dovuto a differenze nella piattaforma e nel linguaggio (si, lo ammetto, ho usato un compilatore c++ ed e' evidente quale ho usato :D ).

L'algoritmo di per se e' ok, quindi se sei interessato ad utilizzare il codice che ti ho passato sono disponibilissimo ad aiutarti a farlo girare sulla tua macchina.
Naturalmente mi serve la lista degli errori... puoi contattarmi in privato, se preferisci