MÁRTON Gyöngyvér

Labor 5

Verem, sor

Feladatok:

1. Készítsünk egy verem ( Stack, LIFO-last input first output, -az utolsóként bevitt elem elsőnek kerül ki ) programmodult, mely segítségével egy fordított lengyel formában megadott matematikai kifejezést kiértékelő számológépet tudunk működtetni. A veremet szimplán láncolt listaként implementáljuk. A verem elemei float típusú számjegyek (0-9) legyenek. Használjuk az alábbi függvény és típusdefiníciókat:

#ifndef STACK_H
#define STACK_H
#include <stdio.h>
#include <stdlib.h>

struct stack{
float key;
struct stack * next;
};

typedef struct stack * STACKPTR;
STACKPTR createItem( float key ); // egy elem helyfoglalása
STACKPTR push(STACKPTR , STACKPTR ); //adott elem hozzáadása
STACKPTR pop ( STACKPTR ); //adott elem törlése
float top ( STACKPTR ); //a verem tetején levo elem lekérdezése
void destroy( STACKPTR );//memória felszabadítás #endif

2. Készítsünk egy sor ( Queue, FIFO-first input first output, -az elsőnek bevitt elem elsőnek kerül ki ) programmodult. A sor elemei tetszőleges karakterláncok legyenek. A sort szimplán láncolt listaként implementáljuk.

3. Készítsünk programot, mely segítségével egy helyesen zárójelezett, 5 matematikai alapműveletet tartalmazó matematikai kifejezést kiértékelő számológépet tudunk működtetni. A matematikai kifejezés kiértékelésének algoritmusa a fent implementált verem és sor segítségével a következő:

átalakítjuk a kezdeti kifejezést fordított lengyel formába
elemenként feldolgozzuk a fordított lengyel formát:

Az alábbi kódrészlet a fordított lengyel forma elemenkénti feldolgozását mutatja, ahol a verem tetején levő elem a kiértékelt kifejezés értékét tartalmazza :

for (i=0; i<hossz(lengyel);++i)
    if (lengyel[i] == 'operandus')
       verembe(tomb[i]);
    if (lengyel[i] == 'operator'){
       tmp1 = verem_teteje;
       verembolki(tmp1);
       tmp2 = verem_teteje;
       verembolki(tmp2);
       res = tmp2 'operator' tmp1;
       verembe(res);
}

Az alábbi kódrészlet a tomb bemenet alapján előállítja a fordított lengyel formát a kimenet tömbe, egy verem adatszerkezet segítségével:
Példa:

kezdeti kifejezés: 8 - 1 - 3 / ( 9 * 7 - 4 * ( 2 - 9 + 1 ) )
fordított lengyel forma: 8 1 - 3 9 7 * 4 2 9 - 1 + * - / -

for (i=0; i<hossz(tomb);++i){
    if (tomb[i] == '('){
        verembe(tomb[i]);
        continue;
    }
    if (tomb[i] == 'operandus'){
        kimenet[k] = tomb[i];
        k++;
    continue;
    }
    if (tomb[i] == 'operator'){
        while (1){
            if ('ures_verem') break;
          tmp = verem_teteje;
            if (tmp == '(') break;
          if (prioritas(tmp) < prioritas(tomb[i]) break;
            verembolki(tmp);
            kimenet[k] = tmp;
            k++;
        }
        verembe(toomb[i]);
        continue;
    }
    if(tomb[i] == ')'){
       tmp = verem_teteje;
       verembolki(tmp);
       while(1){
          if(tmp == '(') break;
          kimenet[k] = tmp;
          k++;
          tmp = verem_teteje;
      verembolki(tmp);
       }
       continue;
    }
while ('nem ures a verem'){
    tmp = verem_teteje;
    verembolki(tmp);
    kimenet[k] = tmp;
    k++;
}