Zadanie 6 - konwersja z posaci infiksowej na ONP (matura probna 2002)
Kod był wyświetlany 3819 razy.
    /*
  Name: Zadanie 6 - konwersja z posaci infiksowej na ONP (matura probna 2002)
  Copyright: GPL GNU
  Author: Przemysław Sierocinski
  Date: 16-11-10 16:18
  Description: 
    Odwrotna Notacja Polska (ONP) jest to beznawiasowy zapis wyrażeń 
    (np. algebraicznych). W notacji tej symbole operandów poprzedzają 
    bezpośrednio symbol operatora. Przykład zamiany postaci matematycznej na
    zapis ONP:
    a+b to w ONP ab+
    (a+b)*c to w ONP ab+c*

    Algorytm:
      dane: wyrazenie w postaci infiksowej
      wynik: wyrazenie w postaci ONP
        
        k1: Pobierz kolejny znak z wyrazenia wejsciowego
         k2: W zaleznosci od rodzaju pobranego znaku:
            
             a) Jesli jest to stala lub zmienna, wypisz go na wyjscie.
         
             b) Jesli jest to znak lewego nawiasu '(', dopisz go na stos. 
             c) Jesli jest to prawy nawias ')', odczytuj ze stosu 
                elementy i przesylaj na wyjscie az do napotkania lewego nawiasu.
             
             d) Jesli jest to znak mnozenia lub dzielenia, a stos jest pusty lub
                na szczycie stosu znajduje sie operator dodawania, odejmowania,
                lub lewy nawias, dopisz biezacy znak na stos. W przeciwnym 
                wypadku zdejmuj ze stosu znaki mnozenia i dzielenia az do 
                napotkania innego znaku.
             
             e) Jesli jest to znak dodawania lub odejmowania, a stos jest pusty
                lub na jego szczycie znajduje sie lewy nawias, dopisz biezacy 
                znak na stos. W przeciwnym wypadku zdjemuj znaki mnozenia,
                dzielenia, dodawania i odejmowania az do oproznienia stosu lub
                napotkania lewego nawiasu.
        
        k3: Jesli wyrazenie wejsciowe sie skonczylo a na stosie zostaly jakies
            elementy, wypisz je kolejno na wyjscie. 
    
    Szczegółowy opis w pliku zad6_ONP.doc
*/

#include <stdio.h>
#include <stack.h>

int main()
{
int i;
char wejscie[80],a; // limit - 80 znakow
memset(wejscie,0,80); // wyzerowanie
stack<char> stos; // stos na operatory
FILE *dane,*wyniki; // uchwyty do plikow

printf("\n\n\tProgram zamienia wyrazenie w notacji infiksowej do postaci ONP.");

dane=fopen("wejscie.txt","r");
if(dane==NULL)
{
    printf("\n\n\tBlad odczytu pliku z danymi.");
    return -1;
    }

wyniki=fopen("wyjscie.txt","w");
if(wyniki==NULL)
{
    printf("\n\n\tBlad dostepu do pliku z wynikami.");
    return -1;
    }

printf("\n\n\n\tPobieram dane z pliku wejscie.txt ");
printf("(limit to 80 znakow na linie).");

while(fgets(wejscie,80,dane)!=NULL) // pobieramy dane z pliku dopuki istnieja   
{   
    /* Wlasciwy algorytm */
    // k1
    for(i=0;wejscie[i]!='\n';i++) // dla kazdego znaku z wyrazenia
    {   // k2 b)
        if(wejscie[i]=='(') // jesli jest lewym nawiasem
        {
            stos.push(wejscie[i]); // zapsujemy go na stosie
            continue;
            }
        // k2 c)
        if(wejscie[i]==')') // jesli jest prawym nawiasem
        {
            while(stos.top()!='(') // dopuki nie natrafi na lewy nawias
            {
                putc(stos.top(),wyniki); // zapisujemy znaki ze stosu na wyjscie
                stos.pop();
                }
            stos.pop(); // i wyrzucamy lewy nawias tez
            continue;
            }
        // k2 d)
        if(wejscie[i]=='*'||wejscie[i]==':') // jesli jest operatorem
        {                                    // z priorytetem 2 ('*',':')
            if(stos.empty())    // a stos jest pusty
            stos.push(wejscie[i]); // zapisujemy go na stosie
            else if(stos.top()=='('||stos.top()=='+'||stos.top()=='-')
             // albo jesli na stosie jest operator z nizszym priorytetem
            stos.push(wejscie[i]); // zapisujemy go na stosie
            else    // w przeciwnym wypadku
            {
                while(!stos.empty()) // dopuki na stosie sa operatory 
                {
                    a=stos.top();
                    if(a=='*'||a==':') // o takim samym priorytecie
                    {                  
                        putc(stos.top(),wyniki); // wypisujemy je na wyjscie
                        stos.pop();
                        }
                    else
                    break;
                    }
                stos.push(wejscie[i]); // i dopisujemy biezacy operator na stos
                }
            continue;
            }
        // k2 e)
        if(wejscie[i]=='+'||wejscie[i]=='-') // jesli jest operatorem
        {                                    // o priorytecie 1 ('+','-')
            if(stos.empty())           // a stos jest pusty
            stos.push(wejscie[i]);     // zapisujemy go na stos
            else if(stos.top()=='(')   
            // albo na stosie jest operator o nizszym priorytecie
            stos.push(wejscie[i]);     // zapisujemy go na stos
            else // w przeciwnym wypadku
            {
                while(!stos.empty()) // dopuki na stosie sie operatory
                {
                    a=stos.top(); // o priorytecie rownym lub wyzszym
                    if(a=='*'||a==':'||a=='+'||a=='-') // if(a!='(')
                    {
                        putc(stos.top(),wyniki); // wypisujemy je na wyjscie
                        stos.pop();
                        }
                    else
                    break;
                    }
                stos.push(wejscie[i]); // i dopisujemy biezacy operator na stos
                }
        continue;
            }
        // k2 a)                    jesli to operand lub jego czesc
        putc(wejscie[i],wyniki); // wypisujemy go na wyjscie
        }
    // k3    
    while(!stos.empty()) // jesli po przetworzeniu wszystkich znakow wyrazenia
    {                    // cos zostalo na stosie
        putc(stos.top(),wyniki); // wypisujemy to na wyjscie
        stos.pop();
        }
    /* Koniec wlasciwego algorytmu */
    putc('\n',wyniki); // dopisane znaku nowej linii na wyjscie
    memset(wejscie,0,80); // wyzerowanie bufora przed nastepnym odczytem
    }
    
printf("\n\n\tWyniki zapisane do wyniki.txt. Zamykam pliki.");
fclose(dane);
fclose(wyniki);

printf("\n\n\tGotowe. Nacisnij enter.");
getchar();
return 0;
}
    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT