Zerkij jednym okiem na ten kod i potraktuj go jako jeden ze sposobów. Algorytm jest prosty, na stos leci wszystko jak leci z małymi wyjątkami:
- Zamknięcie nawiasu usuwa ze stosu cały aktualny ciąg należący do nawiasu
- Dodanie operatora usuwa (oblicza) wszystkie operatory na stosie, jeśli tylko ich poziom 'ważności' jest niższy lub równy aktualnemu:
stos: 1+2
dodajemy + // lub jakikolwiek mocniejszy operator od tego między 1 a 2
1+2 zostaje zamienione na 3
i dopiero teraz dodajemy +
- Zmiana znaku (znak minusa) jest wprowadzana tuż po wykryciu dopisania liczby, jeżeli przed minusem jest jakikolwiek operator:
stos: 1+-
dodajemy 2
stos zmienia się na "1+" a "2" zmienia znak
Zatem miejsce na stosie jest oszczędzane, co można obliczyć jest obliczane.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <windows.h>
#define USE_FLOAT // włącz obsługę liczb rzeczywistych
#define SKIP_SPACES // ignoruj spacje
#ifdef USE_FLOAT
typedef float FINT;
#else
typedef int FINT;
#endif
// typy tokenów na stosie
typedef enum {TYPE_ERROR=0, TYPE_INTEGER, TYPE_OPERATOR } TYPE;
// sposób przechowywania tokenów na stosie
typedef struct {
TYPE type;
char *src;
union {
int optype; // zawsze INT dla TYPE_OPERATOR
FINT value; // INT lub FLOAT dla TYPE_INTEGER
};
} NODE;
// numery błędów
typedef enum {
ERROR_EMPTYSTACK=1, // funkcja calcEval nie akceptuje pustego stosu
ERROR_MISSINGOPERATOR, // nie znaleziono operatora w g_map
ERROR_MISSINGINTEGER, // operator wymaga dwóch liczb
ERROR_INTEGEREXPECTED, // na stosie pozostał operator zamiast liczby
ERROR_BRACENOTOPENED, // zamknięcie nawiasu bez otwarcia
ERROR_BADOPERATOR, // tylko '-' i '(' można dodać do pustego stosu
ERROR_BADTOKEN, // nieznany token - ani operator, ani cyfra
ERROR_STACKOVERFLOW, // brak miejsca na stosie, zwiększ STACKSIZE (jest poniżej)
ERROR_BRACENOTCLOSED, // niezamknięty nawias
ERROR_EMPTYBRACE, // pusty nawias
ERROR_OPERATOREXPECTED // oczekiwano operator przed liczbą
} CALCERROR;
// błędy o indeksach ERRORSTR[CALCERROR]
char *ERRORSTR[] = {"ok",
"funkcja calcEval nie akceptuje pustego stosu",
"nie znaleziono operatora na stosie",
"operator wymaga dwoch liczb",
"na stosie pozostal operator zamiast liczby",
"zamkniecie nawiasu bez otwarcia",
"tylko '-' i '(' mozna dodac do pustego stosu",
"nieznany token - ani operator, ani cyfra",
"brak miejsca na stosie",
"nie zamkniety nawias",
"pusty nawias",
"oczekiwano operatora przed liczba"
};
#define STACKSIZE (4096/sizeof(NODE))
typedef FINT FUNC(FINT, FINT);
// mapowanie znaków na typy - to będzie tablica g_map [256] - dla 256 znaków ascii
typedef struct {
TYPE type;
int level; // poziom pierwszeństwa: 0:niski
FUNC *func;
} CHARMAP;
// pomocnicza struktura do obliczania wyrażeń w nawiasach
typedef struct {
int spMin;
unsigned char *text;
} RECURSIONPARAM;
static CHARMAP g_map[256]; // mapowanie znaków ascii na wewnętrzne typy i funkcje
static NODE g_stack[STACKSIZE]; // stos tokenów
static int g_top;
// handlery operatorów
// printf pokazuje co jest aktualnie obliczne
// operatory '%' oraz '^' nie działają z FLOAT
#ifdef USE_FLOAT
FINT fnDodawanie(FINT a, FINT b) {printf("func: %f+%f=%f\n", a,b,a+b); return a+b;}
FINT fnOdejmowanie(FINT a, FINT b) {printf("func: %f-%f=%f\n", a,b,a-b); return a-b;}
FINT fnDzielenie(FINT a, FINT b) {printf("func: %f/%f=%f\n", a,b,a/b); return a/b;}
FINT fnMnozenie(FINT a, FINT b) {printf("func: %f*%f=%f\n", a,b,a*b); return a*b;}
FINT fnReszta(FINT a, FINT b) {printf("func: %f%%%f=%f\n",a,b,(FINT)((int)a%(int)b)); return (FINT)((int)a%(int)b);}
FINT fnXor(FINT a, FINT b) {printf("func: %f^%f=%f\n", a,b,(FINT)((int)a^(int)b)); return (FINT)((int)a^(int)b);}
#else
FINT fnDodawanie(FINT a, FINT b) {printf("func: %d+%d=%d\n", a,b,a+b); return a+b;}
FINT fnOdejmowanie(FINT a, FINT b) {printf("func: %d-%d=%d\n", a,b,a-b); return a-b;}
FINT fnDzielenie(FINT a, FINT b) {printf("func: %d/%d=%d\n", a,b,a/b); return a/b;}
FINT fnMnozenie(FINT a, FINT b) {printf("func: %d*%d=%d\n", a,b,a*b); return a*b;}
FINT fnReszta(FINT a, FINT b) {printf("func: %d%%%d=%d\n",a,b,a%b); return a%b;}
FINT fnXor(FINT a, FINT b) {printf("func: %d^%d=%d\n", a,b,a^b); return a^b;}
#endif
// jednokrotna inicjalizacja - wypełnia tablicę mapującą znaki ascii na typy/funkcja
void calcInit(void)
{
if (!g_map['0'].type)
{
for (int a='0'; a<='9'; a++)
{
g_map[a].type = TYPE_INTEGER;
}
g_map['^'].type = TYPE_OPERATOR;
g_map['^'].level = 0;
g_map['^'].func = fnXor;
g_map['+'].type = TYPE_OPERATOR; // '+' i '-' mają taki sam poziom
g_map['+'].level = 1;
g_map['+'].func = fnDodawanie;
g_map['-'].type = TYPE_OPERATOR;
g_map['-'].level = 1;
g_map['-'].func = fnOdejmowanie;
g_map['%'].type = TYPE_OPERATOR;
g_map['%'].level = 2;
g_map['%'].func = fnReszta;
g_map['*'].type = TYPE_OPERATOR; // '*' i '/' mają taki sam poziom
g_map['*'].level = 3;
g_map['*'].func = fnMnozenie;
g_map['/'].type = TYPE_OPERATOR;
g_map['/'].level = 3;
g_map['/'].func = fnDzielenie;
// indeksom 'literowym' można nadać typ TYPE_VARIABLE
// a gdy po takim tokenie wystąpi nawias, to mamy funkcję...
}
}
#define LEVEL_MAX 2 // najwyższy poziom ważności operatora
int calcEval(FINT *wynik, int spMin, char** ppv) // zwraca numer błędu
{
// oblicza 'wartość' (int/float) tokenów na stosie, od pozycji spMin aż do g_top
// w razie powodzenia, g_stack[spMin] będzie wynikiem, a g_top będzie równe spMin.
// spMin to relatywny początek stosu - wymagany dla obsługi nawiasów
if (!g_top)
{
// error: stos jest pusty
*ppv = ""; // nie znamy pozycji w buforze
return ERROR_EMPTYSTACK;
}
while (g_top > (spMin+1)) // od spMin to g_top
{
// znajdź pierwszy operator o najwyższym poziomie ważności
int level = -1;
int pos, posmax;
FUNC *func;
for (pos=g_top-1; pos>=spMin; pos--)
{
if (g_stack[pos].type == TYPE_OPERATOR) // mamy jakiś operator
{
// mamy operator
int op = g_stack[pos].optype;
int lvl = g_map[op].level;
if (lvl > level) // zapamiętaj jego pozycję jeśli jest ważniejszy od poprzedniego
{
func = g_map[op].func;
posmax = pos;
level = lvl;
if (level == LEVEL_MAX) break; // nie szukaj dalej
}
}
}
if (level == -1)
{
// error: nie znaleziono operatora, na stosie jest kilka liczb (huh?)
*ppv = g_stack[pos].src;
return ERROR_MISSINGOPERATOR;
}
// operator jest na pozycji posmax. Sprawdź czy po obu stronach jest liczba
if ((g_stack[posmax-1].type != TYPE_INTEGER) || (g_stack[posmax+1].type != TYPE_INTEGER))
{
// error: brakuje liczby
*ppv = g_stack[posmax].src;
return ERROR_MISSINGINTEGER;
}
// oblicz: wynik wpisz na pozycji pierwszej liczby
g_stack[posmax-1].value = func(g_stack[posmax-1].value, g_stack[posmax+1].value);
// usuń operator i drugą liczbę ze stosu
int removeCount = g_top - posmax;
if (removeCount) memcpy(&g_stack[posmax], &g_stack[posmax+2], removeCount * sizeof(NODE));
g_top -= 2;
}
// jeżeli na relatywnym początku stosu jest operator, zgłoś błąd
if (!spMin && (g_stack[0].type != TYPE_INTEGER))
{
// error: oczekiwano liczby
*ppv = g_stack[0].src;
return ERROR_INTEGEREXPECTED;
}
*wynik = g_stack[spMin].value;
return 0;
}
int calcParse(char *_text, void *reserved, FINT *wynik, char** ppv)
{
// _text: wyrażenie matematyczne do obliczenia
// reserved - zarezerwowane, musi być zerem (jeśli nie jest, to wskazuje na RECURSIONPARAM - obliczenie nawiasu)
// wynik - no comment
// ppv - adres zmiennej typu char* która otrzymuje adres znaku (w buforze _text) który powoduje błąd
NODE node;
node.type = TYPE_ERROR;
int size, err;
unsigned char *text = (unsigned char*)_text; // zmiana na unsigned dla indeksowania w g_map[]
unsigned char *start = text;
// jednokrotnie zainicjuj
calcInit();
if (!reserved) // jednokrotnie wyzeruj
{
g_top = 0;
*ppv = NULL;
}
while (*text)
{
#ifdef SKIP_SPACES
while (*text==' ') text++;
#endif
node.src = (char*)text; // zapisz początek tokenu
node.type = g_map[*text].type; // i jego typ
if (node.type == TYPE_INTEGER)
{
#ifdef USE_FLOAT
sscanf((char*)text, "%f%n", &node.value, &size);
#else
sscanf((char*)text, "%d%n", &node.value, &size);
#endif
text += size; // pomiń liczbę
integer:
// jeżeli to liczba ze znakiem, zmień jej znak już teraz
// stos: -liczba
// stos: [cokolwiek][operator]-liczba
if (g_top && (g_stack[g_top-1].type == TYPE_OPERATOR) && (g_stack[g_top-1].optype == '-'))
{
if (g_top == 1) // -5
{
g_top = 0; // usuń '-' ze stosu
node.value = -node.value;
}
else if (g_stack[g_top-2].type == TYPE_OPERATOR) // 2*-3
{
g_top--; // usuń '-' ze stosu
node.value = -node.value;
// jeżeli zmieniamy znak wyrażenia w nawiasie "[tokeny]-(expression)" to
// trzeba też przesunąć do tyłu pozycję znaku '(' w nadrzędnej funkcji
if (reserved) ((RECURSIONPARAM*)reserved)->spMin--;
}
}
else if (g_top && (g_stack[g_top-1].type == TYPE_INTEGER))
{
// dwie kolejne liczby nie są dopuszczalne
*ppv = node.src;
return ERROR_OPERATOREXPECTED;
}
}
else if (node.type == TYPE_OPERATOR)
{
if (!g_top && (*text != '-'))
{
// error: tylko '-' (i nawiasy) można dodać do pustego stosu
*ppv = (char*)text;
return ERROR_BADOPERATOR;
}
node.optype = *text;
text++;
// jeżeli poprzedni (aż do zera) operator jest mocniejszy lub równy aktualnemu "2+3+" lub "2*3+"
// to można już conieco obliczyć zwalniając stos.
int spMin = 0;
if (reserved) spMin = ((RECURSIONPARAM*)reserved)->spMin;
while (g_top >= (spMin+3))
{
int opPrev = g_stack[g_top-2].optype;
if (g_map[opPrev].level >= g_map[node.optype].level)
{
err = calcEval((FINT*)&opPrev, spMin, ppv);
if (err)
{
if (!*ppv) *ppv = (char*)text;
return err;
}
}
else
break;
}
}
else if (*text == '(')
{
// mamy otwarcie nawiasu. Użyjemy rekurencji by obliczyć wartość w nawiasie.
// parametr 'reserved' użyjemy by zdobyć adres końca wyrażenia w nawiasie,
// jako pozycję w buforze _text
RECURSIONPARAM r;
r.spMin = g_top; // zapamiętaj wierzchołek stosu bo chcemy obliczyć tylko od tego miejsca
text++;
// jeżeli _text jest pusty (np. gdy '(' jest ostatnim znakiem)
if (!*text)
{
*ppv = (char*)text-1;
return ERROR_BRACENOTCLOSED;
}
else if (*text == ')')
{
*ppv = (char*)text-1;
return ERROR_EMPTYBRACE;
}
err = calcParse((char*)text, &r, &node.value, ppv);
if (err)
{
if (!*ppv) *ppv = (char*)text;
return err;
}
// a wynik potraktujemy jakby to była liczba. Skaczemy do handlera TYPE_INTEGER
// żeby wykonać dodatkowe, opcjonalne akcje - np. zmiana znaku dla przykładu -(3+4)
text = r.text; // text jest ustawiony za zamykającym nawiasem
node.type = TYPE_INTEGER;
// wynik już jest na stosie, więc ściągamy go
g_top--;
goto integer;
}
else if (*text == ')')
{
if (!reserved)
{
// zerowy poziom rekurencji - błąd, ')' bez '('
*ppv = (char*)text;
return ERROR_BRACENOTOPENED;
}
// zamknięcie nawiasu: obliczamy wszystko od początku nawiasu
((RECURSIONPARAM*)reserved)->text = text+1;
err = calcEval(wynik, ((RECURSIONPARAM*)reserved)->spMin, ppv);
return err;
}
else
{
// error: nieznany token: odstęp, litera lub operator
if (!*ppv) *ppv = (char*)text;
return ERROR_BADTOKEN;
}
if (g_top >= STACKSIZE)
{
// error: przepełniony stos
*ppv = (char*)text;
return ERROR_STACKOVERFLOW;
}
g_stack[g_top].type = node.type;
g_stack[g_top].value = node.value;
g_stack[g_top].src = node.src;
g_top++;
}
if (!reserved)
{
return calcEval(wynik, 0, ppv);
}
return calcEval(wynik, ((RECURSIONPARAM*)reserved)->spMin, ppv);
}
void StackDump(void)
{
for (int a=0;a<g_top;a++)
{
NODE *node = &g_stack[a];
printf("index: %d %s ", a, (node->type == TYPE_INTEGER) ? "LICZBA" : "OPERATOR");
if (node->type == TYPE_INTEGER)
{
#ifdef USE_FLOAT
printf("%f\n", (double)node->value);
#else
printf("%d\n", node->value);
#endif
}
else if (node->type == TYPE_OPERATOR)
{
printf("%c\n", node->optype);
}
}
}
int main()
{
FINT wynik;
char *pszError;
//int err = calcParse("-2+-2*-2", 0, &wynik, &pszError);
//int err = calcParse("2+2*2+5%2", 0, &wynik, &pszError);
//int err = calcParse("2+2*2", 0, &wynik, &pszError);
//int err = calcParse("2*2+2", 0, &wynik, &pszError);
//int err = calcParse("1+-(2)", 0, &wynik, &pszError);
//int err = calcParse("1 1", 0, &wynik, &pszError); // błąd
// będzie błąd gdy USE_FLOAT nie jest zdefiniowane - nieznany token '.'
int err = calcParse("2*4-(2.1+8)^(3-2)/18", 0, &wynik, &pszError);
if (err) // napisz jaki to błąd, który to znak, oraz wypisz zawartość stosu
{
printf("ERROR: %s \"%s\"\n", ERRORSTR[err], pszError);
#ifndef USE_FLOAT
if (*pszError == '.') puts("brakuje #define USE_FLOAT");
#endif
puts("\nDump stosu:");
StackDump();
}
else // nie było błędu
{
#ifdef USE_FLOAT
printf("calcParse: wynik=%f\n", (double)wynik);
#else
printf("calcParse: wynik=%d\n", wynik);
#endif
}
}
Nie pisałem tego specjalnie żeby odpowiedzieć, miałem już ten kod, ale nie obsługiwał on nawiasów. Od razu mówię że liczba zmiennoprzecinkowa zaczynająca się od kropki nie jest uznawana jako liczba (w funkcji calcInit trzeba to dodać), oraz to, że zapewne brakuje obsługi kilku innych błędów.