Kalkulator

    -- Sebastian Pawlak, 2002.


Prezentuję tu program, którego zadaniem jest obliczanie wartości wyrażeń arytmetycznych. Obsługiwane są operatory arytmetyczne (^ * / + -), przy czym najwyższy priorytet ma operator ^, następnie * /, następnie + -. Łączność operatorów jest lewostronna. Argumentami mogą być liczby rzeczywiste nieujemne. Wyrażenie zapisane w notacji nawiasowej konwertowane jest do tożsamego zapisanego w Odwrotnej Notacji Polskiej. Następnie wyrażenie w ONP obliczane jest z wykorzystaniem stosu.

Myślę, że warty uwagi jest algorytm przekształcania wyrażenia zapisanego w notacji nawiasowej do wyrażenia zapisanego w Odwrotnej Notacji Polskiej:

Krok 1
Jeżeli nie ma więcej znaków w ciągu wejściowym, to realizuj krok 6; w przeciwnym razie, przeczytaj następny element (nawias, operator lub argument) i nazwij go x.

Krok 2
Jeżeli x jest argumentem, to zapisz go w ciągu wyjściowym, umieść po nim spację i przejdź do realizacji kroku 1.

Krok 3
Jeżeli x jest nawiasem otwierającym, wpisz go na stos i realizuj krok 1. Jeżeli x jest nawiasem zamykającym, przejdź do realizacji kroku 4, a w przeciwnym razie - kroku 5.

Krok 4
Jeżeli na wierzchu stosu nie ma nawiasu otwierającego, to wycofaj ten obiekt ze stosu wpisując go do ciągu wyjściowego, a zaraz za nim wpisz spację i przejdź do wykonywania kroku 4. Jeżeli na wierzchołku stosu jest nawias otwierający, to wycofaj go ze stosu i przejdź do realizacji kroku 1.

Krok 5
W przypadku, gdy priorytet elementu wierzchołkowego stosu jest większy lub równy priorytetowi x, wycofaj element z wierzchołka stosu, wpisz go do ciągu wyjściowego, a potem wpisz za nim znacznik i powtórz krok 5. W przeciwnym razie, połóż x na wierzchołek stosu i wróć do wykonywania kroku 1.

Krok 6
Opróżnij stos po jednym elemencie, wpisując każdy z nich do ciągu wyjściowego i wstawiając między nimi spację; i to już koniec.


Kod źródłowy pliku "stos.h":

/* stos.h: plik naglowkowy biblioteki z implementacja stosu.
 * Sebastian Pawlak, 2002
 */

#ifndef _STOS_H
#define _STOS_H

void push(double);
double pop(void);

#endif

Kod źródłowy pliku "stos.c":

/* stos.c: biblioteka z implementacja stosu.
 * Sebastian Pawlak, 2002
 */
#include <stdio.h>
#include "stos.h"

#define MAX_STOS 512 /* maksymalny rozmiar stosu */

double stos[MAX_STOS];
int sp = 0; /* wskaznik kolejnego wolnego miejsca na stosie */


/* push: wstawia element na stos */
void push(double element)
{
    if (sp < MAX_STOS)
        stos[sp++] = element;
    else
	printf("push: Przepelnienie stosu!\n");
}


/* pop: zdejmuje element ze stosu */
double pop(void)
{
    if (sp > 0)
        return stos[--sp];

    return 0;
}

Kod źródłowy pliku "kalkulator.c":

/**************************
 *   K A L K U L A T O R  *
 * Sebastian Pawlak, 2002 *
 **************************/

#include <stdio.h>
#include <math.h>    /* dla pow() */
#include <string.h>  /* dla strlen() */
#include <stdlib.h>  /* dla atoi() */
#include "stos.h"

#define MAX 1024  /* maksymalna dlugosc wyrazenia (OdwNotPl) w znakach */

void konwerterOdwNotPl(char *, char *);
double oblicz(char *);


int main(void)
{
    char wyrazenie[MAX], wyrazenieOdwNotPl[MAX];

    printf("Podaj wyrazenie arytmetyczne:\n");
    scanf("%s", wyrazenie);

    konwerterOdwNotPl(wyrazenieOdwNotPl, wyrazenie);
    printf("Wynik konwersji do Odwrotnej Notacji Polskiej: %s\n",
           wyrazenieOdwNotPl);

    printf("Wynik: %.5g\n", oblicz(wyrazenieOdwNotPl));

    return 0;
}


/* konwerterOdwNotPl: funkcja przeksztalca wyrazenie zapisane w notacji
 * nawiasowej do wyrazenia w Odwrotnej Notacji Polskiej.
 *
 * Obslugiwane sa operatory: ^ * / + -
 */
void konwerterOdwNotPl(char *wynik, char *s)
{
    char x, y;

    while (x = *s++) {  /* krok 1 */
        if ((x >= '0' && x <= '9') || x == '.') {  /* krok 2 */
            /* kopiowanie calej liczby z wejscia na wyjscie */
            do
                *wynik++ = x;
            while (x = *s, ((x >= '0' && x <= '9') || x == '.') && s++);
            *wynik++ = ' ';

        } else if (x == '(')  /* krok 3 */
            push((double)'(');

        else if (x == ')')  /* krok 4 */
            while ((y = (char)pop()) != '(')
                *wynik++ = y, *wynik++ = ' ';

        else {  /* krok 5 */
            while (y = (char)pop(),
                   y && (y == '^' || (y == '*' || y == '/') && x != '^' ||
                   (y == '+' || y == '-') && x != '*' && x != '/' && x != '^'))
                *wynik++ = y, *wynik++ = ' ';
            push((double)y);
            push((double)x);
        }
    }

    while(x = (char)pop())  /* krok 6 */
        *wynik++ = x, *wynik++ = ' ';

    *wynik = '\0';  /* zakonczenie lancucha wyjsciowego */
}


/* oblicz: funkcja oblicza wartosc wyrazenia arytmetycznego zapisanego w
 * Odwrotnej Notacji Polskiej
 */
double oblicz(char *s)
{
    char element[MAX];
    double op2;

    while (sscanf(s, "%s", element) != -1) {
        s += strlen(element) + 1;
        switch (element[0]) {
            case '0': case '1': case '2':
            case '3': case '4': case '5':
            case '6': case '7': case '8': case '9': case '.': /* liczba */
	        push(atof(element));
		break;

            case '^':
		op2 = pop();  /* ze wzgledu na nieprzemiennosc potegowania */
		push(pow(pop(), op2));
		break;

	    case '*':
		push(pop() * pop());
		break;

            case '/':
                op2 = pop();  /* ze wzgledu na nieprzemiennosc dzielenia */
                if (op2 != 0.0)
                    push(pop() / op2);
                else {
                    printf("oblicz: Blad dzielenia przez zero!\n");
                    return -1;
                }
		break;

            case '+':
                push(pop() + pop());
                break;

            case '-':
                op2 = pop();  /* ze wzgledu na nieprzemiennosc odejmowania */
                push(pop() - op2);
                break;

            default:
                printf("oblicz: Blad - nieznany znak!\n");
                return -1;
        }
    }

    return pop(); /* zwraca wynik */
}
w3cw3c
automatyka przemysłowa