[C] Problemi notazione postfissa (polacca inversa) con stack
#ifndef LIST_H
#define LIST_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef BIG_STRING /* Allow "cc -D" to override definition */
#define STRING_SIZE 10
#else
#define STRING_SIZE 5
#endif
typedef enum { ERROR = -1, OK = 0 } status;
typedef struct _node {
struct _node *next;
char *el;
} node;
node *push(node *head, char *el) {
if (head == NULL) {
node *first = (node *)malloc(sizeof(struct _node));
first->el = (char *)malloc(STRING_SIZE * sizeof(char));
strcpy(first->el, el);
first->next = NULL;
#ifdef DEBUG
printf("Element [%s] added as head\n", el);
#endif
return first;
}
node *curr = head;
while ((curr->next != NULL) && (curr != NULL)) {
curr = curr->next;
}
node *tmp = (node *)malloc(sizeof(struct _node));
tmp->el = (char *)malloc(STRING_SIZE * sizeof(char));
strcpy(tmp->el, el);
tmp->next = NULL;
curr->next = tmp;
#ifdef DEBUG
printf("Element [%s] pushed\n", el);
#endif
return curr;
}
char *pop(node **head) {
if ((*head) == NULL) {
return NULL;
}
node *curr = (*head);
char *ret = (char *)malloc(STRING_SIZE * sizeof(char));
strcpy(ret, curr->el);
(*head) = (*head)->next;
#ifdef DEBUG
printf("Element [%s] popped\n", curr->el);
#endif
free(curr->el);
free(curr);
return ret;
}
int printList(node *head) {
if (head == NULL) {
return ERROR;
}
node *curr = head;
while (curr->next != NULL) {
printf("[%s]\t", curr->el);
curr = curr->next;
}
printf("[%s]\n", curr->el);
return OK;
}
void freeList(node *head) {
node *curr = head;
node *tmp = NULL;
while (curr != NULL) {
tmp = curr;
#ifdef DEBUG
printf("Freeing element [%s] \n", curr->el);
#endif
curr = curr->next;
free(tmp->el);
free(tmp);
}
}
#endif
#include <string.h>
#include <stdio.h>
#include "list.h"
int main() {
char str[80] = "5 1 * 100 4 +";
const char sep[2] = " ";
char *token;
unsigned int first_is_used = 0;
/* get the first token */
token = strtok(str, sep);
node *head = push(NULL, "");
int i = 0;
/* pushing the input string */
while (token != NULL) {
i++;
#ifdef DEBUG
printf("We are at step %d with %s\n", i, token);
#endif
push(head, token);
token = strtok(NULL, sep);
}
pop(&head); // remove useless head
#ifdef DEBUG
printList(head);
#endif
char *el = (char *)malloc(STRING_SIZE * sizeof(char));
char *res = (char *)malloc(STRING_SIZE * sizeof(char));
int f = 0;
int s = 0;
int tot = 0;
int finale = 0;
while ((el = pop(&head)) != NULL) {
if (strcmp(el, "+") == 0) {
tot = f + s;
#ifdef DEBUG
printf(" %d + %d = %d\n", f, s, tot);
#endif
sprintf(res, "%d", tot);
push(head, res);
finale += tot;
first_is_used = 0;
} else if (strcmp(el, "-") == 0) {
tot = f - s;
#ifdef DEBUG
printf(" %d - %d = %d\n", f, s, tot);
#endif
sprintf(res, "%d", tot);
push(head, res);
finale += tot;
first_is_used = 0;
} else if (strcmp(el, "*") == 0) {
tot = f * s;
#ifdef DEBUG
printf(" %d * %d = %d\n", f, s, tot);
#endif
sprintf(res, "%d", tot);
push(head, res);
finale += tot;
first_is_used = 0;
} else if (strcmp(el, "/") == 0) {
tot = f / s;
#ifdef DEBUG
printf(" %d / %d = %d\n", f, s, tot);
#endif
sprintf(res, "%d", tot);
push(head, res);
finale += tot;
first_is_used = 0;
} else /* default: */
{
if (first_is_used == 0) {
f = atoi(el);
first_is_used = 1;
} else if (first_is_used == 1) {
s = atoi(el);
}
}
}
printf("Grand total: %d\n", finale);
freeList(head);
free(el);
free(res);
return OK;
}
HEADERS = list.h all: nrp.o nrp_debug.o nrp.o: main.c $(HEADERS) gcc -std=c11 main.c -o nrp.o nrp_debug.o: main.c $(HEADERS) gcc -DDEBUG -std=c11 main.c -o nrp_debug.o clean: -rm -f nrp.o
Ma non appena provo cosette come [size=150]100 2 * 400 5 * -[/size] il divertimento comincia
P.s: il python travia se non si usa C per un po'
Risposte
Ho dato una occhiata solo veloce al tuo codice, ma mi sembra tu stia confondendo la lista FIFO dei token in input con lo stack LIFO che viene usata per memorizzare gli operandi. Il metodo corretto è quello di leggere un valore per volta da input (e per questo è sufficiente continuare ad usare strtok invece di fare ricorso ad una lista) e usare la seguente logica:
1. Se numero, aggiungere allo stack
2. Se operatore, prendere due valori dallo stack ed eseguire l'operazione tra di loro
3. Se l'input è terminato, estrai il valore dallo stack e lo restituisci.
1. Se numero, aggiungere allo stack
2. Se operatore, prendere due valori dallo stack ed eseguire l'operazione tra di loro
3. Se l'input è terminato, estrai il valore dallo stack e lo restituisci.
Ti ho scritto un esempio di quello che intendo come algoritmo corretto per il calcolo in notazione postfissa. Nota l'uso di una struttura dati diversa (le liste come vengono insegnate a scuola/università sono difficili da gestire e incredibilmente lente rispetto alla soluzione alternativa qui presentata). Nota che le liste in python sono implementate in modo analogo. L'ho scritto sul momento quindi potrebbe avere qualche errore, ma dovrebbe essere abbastanza corretto.
Un esempio di input e output:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef struct Stack Stack;
struct Stack {
uint32_t capacity;
uint32_t size;
int values[];
};
static inline Stack *grow(Stack *s)
{
uint32_t new_capacity = !s ? 32 : 2 * s->capacity;
Stack *snew = realloc(s, sizeof(Stack) + sizeof(int) * new_capacity);
if (!snew) {
fprintf(stderr, "Not enough memory.\n\n");
exit(EXIT_FAILURE);
}
return snew;
}
static inline Stack *push(Stack *s, int v)
{
if (!s || s->size >= s->capacity) {
s = grow(s);
}
s->values[s->size++] = v;
return s;
}
static inline int pop(Stack *s)
{
if (!s || s->size <= 0) {
fprintf(stderr, "Pop from empty stack.\n\n");
exit(EXIT_FAILURE);
}
int ret = s->values[--s->size];
return ret;
}
int main(int argc, char **argv)
{
for (int i = 1; i < argc; ++i) {
printf("Computing expression: \"%s\".\n\n", argv[i]);
Stack *s = NULL;
char *token = strtok(argv[i], " ");
while (token) {
if (strcmp("+", token) == 0) {
if (!s || s->size < 2) {
fprintf(stderr, "Invalid expression: not balanced expression.\n\n");
free(s);
break;
}
int b = pop(s);
int a = pop(s);
printf("OP: %d + %d\n", a, b);
s = push(s, a + b);
} else if (strcmp("-", token) == 0) {
if (!s || s->size < 2) {
fprintf(stderr, "Invalid expression: not balanced expression.\n\n");
free(s);
break;
}
int b = pop(s);
int a = pop(s);
printf("OP: %d - %d\n", a, b);
s = push(s, a - b);
} else if (strcmp("*", token) == 0) {
if (!s || s->size < 2) {
fprintf(stderr, "Invalid expression: not balanced expression.\n\n");
free(s);
break;
}
int b = pop(s);
int a = pop(s);
printf("OP: %d * %d\n", a, b);
s = push(s, a * b);
} else if (strcmp("/", token) == 0) {
if (!s || s->size < 2) {
fprintf(stderr, "Invalid expression: not balanced expression.\n\n");
free(s);
break;
}
int b = pop(s);
int a = pop(s);
printf("OP: %d / %d\n", a, b);
s = push(s, a / b);
} else {
printf("V: %s\n", token);
s = push(s, atoi(token));
}
if (s) {
printf("Stack: ");
for (int j = 0; j < s->size; ++j) {
printf("%d ", s->values[j]);
}
printf("\n");
}
token = strtok(NULL, " ");
}
if (s && s->size == 1) {
printf("Result: %d.\n\n", pop(s));
free(s);
} else if (s) {
fprintf(stderr, "Invalid expression: not balanced expression.\n\n");
}
}
return EXIT_SUCCESS;
}
Un esempio di input e output:
$ ./main.exe "10 20 +" "100 2 * 400 5 * -" Computing expression: "10 20 +". V: 10 Stack: 10 V: 20 Stack: 10 20 OP: 10 + 20 Stack: 30 Result: 30. Computing expression: "100 2 * 400 5 * -". V: 100 Stack: 100 V: 2 Stack: 100 2 OP: 100 * 2 Stack: 200 V: 400 Stack: 200 400 V: 5 Stack: 200 400 5 OP: 400 * 5 Stack: 200 2000 OP: 200 - 2000 Stack: -1800 Result: -1800.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo