Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //лексический анализ
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- struct Node {
- int k;
- int v;
- int balance;
- struct Node *parent, *left, *right;
- };
- typedef struct Node Node;
- Node *replaceNode(Node *t, Node *x, Node *y) {
- if (x == t) {
- t = y;
- if (y)
- y->parent = NULL;
- } else {
- Node *p = x->parent;
- if (y)
- y->parent = p;
- if (p->left == x)
- p->left = y;
- else
- p->right = y;
- }
- return t;
- }
- Node *rotateLeft(Node *t, Node *x) {
- Node *y = x->right;
- replaceNode(t, x, y);
- Node *b = y->left;
- if (b)
- b->parent = x;
- x->right = b;
- x->parent = y;
- y->left = x;
- x->balance--;
- if (y->balance > 0)
- x->balance -= y->balance;
- y->balance--;
- if (x->balance < 0)
- y->balance += x->balance;
- return t;
- }
- Node *rotateRight(Node *t, Node *x) {
- Node *y = x->left;
- replaceNode(t, x, y);
- Node *b = y->right;
- if (b)
- b->parent = x;
- x->left = b;
- x->parent = y;
- y->right = x;
- x->balance++;
- if (y->balance < 0)
- x->balance += y->balance;
- y->balance++;
- if (x->balance > 0)
- y->balance -= x->balance;
- return t;
- }
- Node *insert(Node *t, int k, int v) {
- Node *y = calloc(1, sizeof(Node));
- y->k = k;
- y->v = v;
- if (t == NULL) {
- t = y;
- } else {
- Node *x = t;
- while (1) {
- if (k < x->k) {
- if (!x->left) {
- x->left = y;
- y->parent = x;
- break;
- }
- x = x->left;
- } else {
- if (!x->right) {
- x->right = y;
- y->parent = x;
- break;
- }
- x = x->right;
- }
- }
- }
- return t;
- }
- Node *insertAVL(Node *t, int k, int v) {
- Node *a = insert(t, k, v);
- while (1) {
- Node *x = a->parent;
- if (!x)
- break;
- if (a == x->left) {
- x->balance--;
- if (!x->balance)
- break;
- if (x->balance == -2) {
- if (a->balance == 1)
- rotateRight(t, a);
- rotateLeft(t, x);
- break;
- }
- } else {
- x->balance++;
- if (!x->balance)
- break;
- if (x->balance == 2) {
- if (a->balance == -1)
- rotateLeft(t, a);
- rotateRight(t, x);
- break;
- }
- }
- a = x;
- }
- return a;
- }
- int getAVL(Node *t, int k) {
- Node *x = t;
- while (x && x->k != k)
- if (k < x->k)
- x = x->left;
- else
- x = x->right;
- if (x)
- return x->v;
- return -1;
- }
- void freeAVL(Node *t) {
- if (!t)
- return;
- freeAVL(t->left);
- freeAVL(t->right);
- free(t);
- }
- enum tok_type {
- TOK, NUM, VAR, SPC
- };
- typedef enum tok_type tok_type;
- tok_type getType(char c) {
- if ('0' <= c && c <= '9')
- return NUM;
- if ('a' <= c && c <= 'z')
- return VAR;
- if ('A' <= c && c <= 'Z')
- return VAR;
- if(c == ' ')
- return SPC;
- return TOK;
- }
- int getSpec(char c) {
- switch (c) {
- case '+':
- return 0;
- case '-':
- return 1;
- case '*':
- return 2;
- case '/':
- return 3;
- case '(':
- return 4;
- case ')':
- return 5;
- }
- return 0;
- }
- int main(void) {
- int n;
- scanf("%d", &n);
- char str[n + 1];
- str[n] = '\0';
- fgetc(stdin);
- fgets(str, n + 1, stdin);
- Node *t = NULL;
- char *tok = str;
- int id = 0;
- while (*tok) {
- switch (getType(*tok)) {
- case SPC:
- while(getType(*tok) == SPC) tok++;
- break;
- case TOK:
- printf("SPEC ");
- printf("%d", getSpec(*tok));
- printf("\n");
- tok++;
- break;
- case NUM:
- printf("CONST ");
- while (getType(*tok) == NUM)
- printf("%c", *tok++);
- printf("\n");
- break;
- case VAR:
- printf("IDENT ");
- unsigned int tmp = 5381;
- while (getType(*tok) != TOK && getType(*tok) != SPC) {
- tmp = ((tmp << 5) + tmp) + *tok++;
- }
- if (!t) {
- printf("%d\n", id);
- t = insertAVL(t, tmp, id++);
- } else {
- int tid = getAVL(t, tmp);
- if (tid == -1) {
- printf("%d\n", id);
- t = insertAVL(t, tmp, id++);
- } else
- printf("%d\n", tid);
- }
- break;
- }
- }
- freeAVL(t);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement