Structuri de date - Nan Mihai

#define SIZE 50
#include <stdio.h>
#include <malloc.h>
#include <memory.h>

/**
 * O structura de date reprezentand o stiva.
 * Pentru implementare se foloseste un tablou alocat dinamic si un contor
 * ce indica numarul de elemente din stiva
 * Se folosesc valori de tipul Stack (ce sunt pointeri la struct _stack)
 *
 */
typedef struct _stack {
    char* data;
    int capacity;
    int size;
}* Stack;


/** La initializare, capacitatea tabloului de date al stivei este dat de constanta STACK_INITIAL_SIZE*/
#define STACK_INITIAL_SIZE 10

/** 1. Creaza o stiva noua*/
Stack init()
{
    Stack nou;
    nou = (Stack) malloc(sizeof(struct _stack));
    nou->capacity = 10;
    nou->data = (char *) malloc(nou->capacity*sizeof(char));
    nou->size = 0;
    return nou;
}

/** 2. Elibereaza spatiul folosit de o stiva. Returneaza NULL*/
Stack delete(Stack s)
{
    free(s->data);
    free(s);
    return NULL;
}

/** 3. Se asigura ca zona de date are cel putin capacitatea minCapacity*/
void ensureCapacity(Stack s, int minCapacity)
{
    if(s->capacity < minCapacity)
    {
        s->data = (char *) realloc(s->data, minCapacity*sizeof(char));
        s->capacity = minCapacity;
    }
}

/** 4. Intoarce true (i.e. 1) daca stiva este goala*/
int isEmpty(Stack s)
{
    if(s->size == 0)
        return 1;
    else
        return 0;
}

/** 5. Adauga un element in varful stivei */
void push(Stack s, char value)
{
    if(s->size < s->capacity)
    {
        s->data[s->size] = value;
        s->size++;
    }
    else
    {
        ensureCapacity(s, 2*s->size);
        s->data[s->size] = value;
        s->size++;
    }
}

/** 6. Intoarce elementul din varful stivei sau 0 daca stiva e goala*/
char top1(Stack s)
{
    if(s->size == 0)
    {
        return 0;
    }
    else
    {
        return s->data[s->size-1];
    }
}

/** 7. Intoarce elementul din varful stivei si il elimina din stiva. Intoarce 0 daca stiva e goala */
char pop(Stack s)
{
    char c;
    if(s->size == 0)
    {
        return 0;
    }
    else
    {
        c = s->data[s->size-1];
        s->size--;
        return c;
    }

}

void checkValue(char expected, char actual);
void checkEmpty(Stack s, int expected);

#define START_TEST(desc) printf("Running#define SIZE 50  %s: %s\n",  __FUNCTION__, desc);

void test1234() {
    START_TEST("Init, ensureCapacity, isEmpty and delete");
    Stack s = init();
    checkEmpty(s, 1);
    s = delete(s);

    s = init();
    ensureCapacity(s, STACK_INITIAL_SIZE * 2);
    checkEmpty(s, 1);
    s = delete(s);


    s = init();
    ensureCapacity(s, 1);
    checkEmpty(s, 1);
    s = delete(s);

    s = init();
    ensureCapacity(s, 1);
    ensureCapacity(s, STACK_INITIAL_SIZE * 2);
    ensureCapacity(s, STACK_INITIAL_SIZE * 5);

    checkEmpty(s, 1);
    s = delete(s);
}


int prioritate(char c)
{
    switch(c){
        case '(':
            return 1;
        case ')':
            return 2;
        case '+':
        case '-':
            return 3;
        case '*':
        case '/':
            return 4;
        default:
            return 5;
    }
}

//Functie 1
/*char aux, ch, a1;
    int p, i;
    i = 0;
    char *text, *rezultat;
    Stack s = init();
    text = (char *) malloc(2000*sizeof(char));
    rezultat = (char *) malloc(2000*sizeof(char));
    fgets(text, 2000, stdin);
    printf("%s\n", text);
    while(text != NULL)
    {
        aux = *text;#define SIZE 50
        text++;
        p = prioritate(aux);
        if(p == 5)
        {
            rezultat[i] = aux;
            i++;
        }
        else
        if(p == 1)
        {
            push(s, aux);
        }
        else
        if(p == 2)
        {
            a1 = pop(s);
            while(a1 != '(')
            {
                rezultat[i] = a1;
                i++;
                a1 = pop(s);
            }
        }

    }
    while(s->size > 0)
    {
        a1 = pop(s);
        rezultat[i] = a1;
        i++;
    }
    printf("%s\n", rezultat);*/


char s[SIZE];
int top = -1;

push1(char elem) {
    s[++top] = elem;
}

char pop1() {
    return (s[top--]);
}

int pr(char elem) {
 switch (elem) {
 case '#':
  return 0;
 case '(':
  return 1;
 case '+':
 case '-':
  return 2;
 case '*':
 case '/':
  return 3;
 }
}





int main(int argc, char** argv) {
    char infx[50], pofx[50], ch, elem;
    int i = 0, k = 0;
    scanf("%s", infx);
    push1('#');
    while ((ch = infx[i++]) != '\0') {
        if (ch == '(')
            push1(ch);
        else if (isalnum(ch))
            pofx[k++] = ch;
        else if (ch == ')') {
            while (s[top] != '(')
                    pofx[k++] = pop1();
            elem = pop1();
        } else {
            while (pr(s[top]) >= pr(ch))
                    pofx[k++] = pop1();
        push1(ch);
        }
    }
    while (s[top] != '#')
        pofx[k++] = pop1();
    pofx[k] = '\0';
    printf("%s\n", pofx);
    return 0;
}

void checkEmpty(Stack s, int expected) {
    int actual = isEmpty(s);
    if(actual != expected) {
        printf("!!! ERROR2: expected %d, got %d\n", expected, actual);
    }
}

void checkValue(char expected, char actual) {
    if (expected != actual)
        printf("!!! ERROR3: expected %c, got %c\n", expected, actual);
}