Evaluator izraza

Napisati program koji evaluira aritmetički izraz predstavljen binarnim stablom. Svaki čvor stabla može biti ili operator (+, -, *, /) ili operand (celo broj). Listovi stabla su uvek operandi, dok su unutrašnji čvorovi uvek operatori. Program treba da učita izraz u binarno stablo i zatim da izračuna vrednost izraza.

Ulaz

Sa standardnog ulaza se učitava izraz u prefiksnoj notaciji. Svaki token (operator ili operand) je odvojen jednim razmakom. Na primer, izraz + 3 * 5 2 predstavlja izraz 3 + (5 * 2).

Izlaz

Na standardni izlaz treba ispisati vrednost evaluiranog izraza kao ceo broj.

U slučaju deljenja sa nulom, program treba da ispiše poruku Error: Division by zero i da se zaustavi.

Primer

stdin

+ 3 * 5 2

stdout

13

Primer

stdin

- / 10 + 1 1 * 1 2

stdout

3

Primer

stdin

/ 4 - 2 2

stderr

Error: Division by zero

Rešenje

stablo_genericko.h

#ifndef __STABLO_GENERICKO_H__
#define __STABLO_GENERICKO_H__

#include <stdio.h>
#include <stdlib.h>
#include "stablo_podatak.h"

typedef enum {
   OK,
   NEDOVOLJNO_MEMORIJE,
   NEMA_ELEMENATA
} status;

typedef struct cvor_stabla {
  Data podatak;
  struct cvor_stabla* levo;
  struct cvor_stabla* desno;
} cvor_stabla;

typedef cvor_stabla* Stablo;

status inicijalizuj_stablo(Stablo* s); 
status dodaj_u_stablo(Stablo* s, const Data* podatak, 
                      int (*poredi)(const Data*, const Data*));
status pronadji(Stablo s, const Data* trazeno, Data** nadjeno, 
                int (*poredi)(const Data*, const Data*));
int broj_elemenata(Stablo s);
void ispisi_stablo(Stablo s);
void obrisi_stablo(Stablo* s); 

#endif

stablo_podatak.h

#ifndef __STABLO_PODATAK_H
#define __STABLO_PODATAK_H

typedef enum {
    OPERATOR,
    OPERAND,
    INVALID
} DataType;

typedef struct {
    DataType type;
    union {
        char operator;
        int operand;
    };
} Data;

Data napravi_operator(char operator);
Data napravi_operand(int operand);
Data napravi_invalid();

Data evaluiraj_operaciju(const Data* operator, const Data* operand1, const Data* operand2);

void dodeli(Data* dest, const Data* src);
void ispisi_podatak(const Data* data);

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include "stablo_podatak.h"
#include "stablo_genericko.h"

#define MAX_TOKEN_SIZE 16

status ucitaj_izraz(Stablo* izraz)
{
	char token[MAX_TOKEN_SIZE];
	scanf("%s", token);

	if (token[0] == '+' || token[0] == '-' || 
	    token[0] == '*' || token[0] == '/') {
		Data op = napravi_operator(token[0]);
		status s = dodaj_u_stablo(izraz, &op, NULL);
		if (s != OK) {
			return s;
		}

		s = ucitaj_izraz(&((*izraz)->levo));
		if (s != OK) {
			return s;
		}

		s = ucitaj_izraz(&((*izraz)->desno));
		if (s != OK) {
			return s;
		}
	} else {
		int operand = atoi(token);
		Data opnd = napravi_operand(operand);
		status s = dodaj_u_stablo(izraz, &opnd, NULL);
		if (s != OK) {
			return s;
		}
	}

	return OK;
}

Data evaluiraj_izraz(Stablo izraz)
{
	if (izraz == NULL) {
		return napravi_invalid();
	}

	if (izraz->podatak.type == OPERAND) {
		return izraz->podatak;
	}

	Data levo = evaluiraj_izraz(izraz->levo);
	Data desno = evaluiraj_izraz(izraz->desno);

	return evaluiraj_operaciju(&(izraz->podatak), &levo, &desno);
}

int main(void)
{
	Stablo izraz;
	status s = inicijalizuj_stablo(&izraz);
	if (s != OK) {
		obrisi_stablo(&izraz);
		exit(EXIT_FAILURE);
	}

	s = ucitaj_izraz(&izraz);
	Data rezultat = evaluiraj_izraz(izraz);

	if (rezultat.type == OPERAND) {
		printf("%d\n", rezultat.operand);
	} else if (rezultat.type == INVALID) {
		obrisi_stablo(&izraz);
		exit(EXIT_FAILURE);
	}

	obrisi_stablo(&izraz);

	exit(EXIT_SUCCESS);
}

stablo_genericko.c

#include "stablo_genericko.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

cvor_stabla* novi_cvor_stabla(const Data* podatak) 
{
  cvor_stabla* novi = malloc(sizeof(cvor_stabla));
  if (novi == NULL)
    return NULL;
  dodeli(&(novi->podatak), podatak);
  novi->levo = NULL;
  novi->desno = NULL;
  return novi;
}

status inicijalizuj_stablo(Stablo* s) 
{
  *s = NULL;
  return OK;
}

status dodaj_u_stablo(Stablo* s, const Data* podatak, 
                      int (*poredi)(const Data*, const Data*))
{
  cvor_stabla* tmp;
  cvor_stabla* novi = novi_cvor_stabla(podatak);
  if (novi == NULL)
    return NEDOVOLJNO_MEMORIJE;
  novi->levo = NULL;
  novi->desno = NULL;

  if (*s == NULL) { 
    *s = novi;
    return OK;
  }
  tmp = *s;
  while (1) {
    if (poredi(podatak, &(tmp->podatak)) <= 0) {
      if (tmp->levo == NULL) {
          tmp->levo = novi;
        return OK;
      }
      else
        tmp = tmp->levo;
    }
    else {
      if (tmp->desno == NULL) {
          tmp->desno = novi;
        return OK;
      }
      else
        tmp = tmp->desno;
    }
  }
  return OK;
}

status pronadji(Stablo s, const Data* trazeno, Data** nadjeno, 
                int (*poredi)(const Data*, const Data*))
{
  if (s == NULL)
    return NEMA_ELEMENATA;
  if (poredi(trazeno, &(s->podatak)) == 0) {
    *nadjeno = &(s->podatak);
    return OK;
  }
  if (poredi(trazeno, &(s->podatak)) < 0) 
    return pronadji(s->levo, trazeno, nadjeno, poredi);
  return pronadji(s->desno, trazeno, nadjeno, poredi);
}

int broj_elemenata(Stablo s)
{
  return s == NULL ? 
           0 : 
           broj_elemenata(s->levo)+1+broj_elemenata(s->desno);
}

void ispisi_stablo(Stablo s) 
{
  if (s != NULL) {
     ispisi_stablo(s->levo);      
     ispisi_podatak(&(s->podatak)); 
     ispisi_stablo(s->desno);    
  }
}

void obrisi_stablo(Stablo* s) 
{
  if (*s != NULL) {
    obrisi_stablo(&((*s)->levo));
    obrisi_stablo(&((*s)->desno));
    free(*s);
    *s = NULL;
  }
}

stablo_podatak.c

#include <stdio.h>
#include "stablo_podatak.h"

Data napravi_operand(int operand) 
{
    Data data;
    data.type = OPERAND;
    data.operand = operand;
    return data;
}

Data napravi_operator(char operator) 
{
    Data data;
    data.type = OPERATOR;
    data.operator = operator;
    return data;
}

Data napravi_invalid() {
    Data data;
    data.type = INVALID;
    return data;
}

Data evaluiraj_operaciju(const Data* operator, const Data* operand1, const Data* operand2) 
{
    if (operator->type != OPERATOR || 
        operand1->type != OPERAND || 
        operand2->type != OPERAND) {
      return napravi_invalid();
    }

    int result = 0;
    switch (operator->operator) {
        case '+':
            result = operand1->operand + operand2->operand;
            break;
        case '-':
            result = operand1->operand - operand2->operand;
            break;
        case '*':
            result = operand1->operand * operand2->operand;
            break;
        case '/':
            if (operand2->operand == 0) {
                fprintf(stderr, "Error: Division by zero\n");
                return napravi_invalid();
            }
            result = operand1->operand / operand2->operand;
            break;
        default:
            return napravi_invalid();
    }

    return napravi_operand(result);
} 

void dodeli(Data* dest, const Data* src) 
{
    dest->type = src->type;
    if (src->type == OPERATOR) {
        dest->operator = src->operator;
    } else if (src->type == OPERAND) {
        dest->operand = src->operand;
    }
}

void ispisi_podatak(const Data* data) 
{
    if (data->type == OPERATOR) {
        printf("%c", data->operator);
    } else if (data->type == OPERAND) {
        printf("%d", data->operand);
    } else {
        printf("INVALID");
    }
}