fork download
copy 
  1. #include <stddef.h>
  2. #include <stdint.h>
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <memory.h>
  6. #include <string.h>
  7.  
  8.  
  9. typedef enum TokenType_ {
  10.   TOKEN_TYPE_EOF,
  11.   TOKEN_TYPE_DELIM,
  12.   TOKEN_TYPE_NUM,
  13.   TOKEN_TYPE_X,
  14.   TOKEN_TYPE_PLUS,
  15.   TOKEN_TYPE_MINUS,
  16.   TOKEN_TYPE_EQUAL,
  17. } TokenType;
  18. /*
  19. static const char* TOKEN_TYPE_STR[6] = {
  20.   "TOKEN_TYPE_EOF",
  21.   "TOKEN_TYPE_DELIM",
  22.   "TOKEN_TYPE_NUM",
  23.   "TOKEN_TYPE_X"
  24.   "TOKEN_TYPE_PLUS",
  25.   "TOKEN_TYPE_MINUS",
  26.   "TOKEN_TYPE_EQUAL",
  27. };
  28. */
  29. typedef struct Token_ Token;
  30.  
  31. typedef struct Lexer_ Lexer;
  32.  
  33. Lexer *Lexer_init(Lexer*, FILE*, int);
  34. void Lexer_final(Lexer*);
  35. int Lexer_get(Lexer*);
  36. int Lexer_put(Lexer*, int);
  37. void Lexer_skip(Lexer*);
  38. int Lexer_tokenizer(Lexer*, Token*);
  39. void Lexer_tokenizer_num(Lexer*, Token*);
  40.  
  41. struct Token_ {
  42.   int num;
  43.   TokenType type;
  44. };
  45.  
  46. struct Lexer_ {
  47.   FILE* file;
  48.   int close;
  49.   int buf;
  50.   int is_buf;
  51. };
  52. Lexer *Lexer_init(Lexer *self, FILE* file, int close) {
  53.   self->file = file;
  54.   self->close = close;
  55.   self->is_buf = 0;
  56.   return self;
  57. }
  58. void Lexer_final(Lexer *self) {
  59.   if (self->file && self->close) {
  60.     fclose(self->file);
  61.   }
  62. }
  63. int Lexer_get(Lexer* self) {
  64.   if (EOF != self->buf && !self->is_buf) {
  65.     return self->buf = fgetc(self->file);
  66.   }
  67.   self->is_buf = 0;
  68.   return self->buf;
  69. }
  70. int Lexer_put(Lexer* self, int c) {
  71.   if (self->is_buf) {
  72.     fprintf(stderr, "ERROR!: Lexer_put: buffer full.\n");
  73.     return 1;
  74.   }
  75.   self->is_buf = 1;
  76.   self->buf = c;
  77.   return 0;
  78. }
  79. int Lexer_tokenizer(Lexer* self, Token *token) {
  80.   if (NULL == token) {
  81.     fprintf(stderr, "ERROR!: Lexer_tokenizer: failed malloc.\n");
  82.     return 1;
  83.   }
  84.   Lexer_skip(self);
  85.   int c;
  86.   switch (c = Lexer_get(self)) {
  87.     case EOF:           token->type = TOKEN_TYPE_EOF;   break;
  88.     case ';':           token->type = TOKEN_TYPE_DELIM; break;
  89.     case '0': case '1': case '2': case '3': case '4':
  90.     case '5': case '6': case '7': case '8': case '9':
  91.       token->type = TOKEN_TYPE_NUM;
  92.       token->num = c - '0';
  93.       Lexer_tokenizer_num(self, token);
  94.       break;
  95.     case 'x': case 'X': token->type = TOKEN_TYPE_X;     break;
  96.     case '+':           token->type = TOKEN_TYPE_PLUS;  break;
  97.     case '-':           token->type = TOKEN_TYPE_MINUS; break;
  98.     case '=':           token->type = TOKEN_TYPE_EQUAL; break;
  99.     default:
  100.       Lexer_put(self, c);
  101.       return 1;
  102.   }
  103.   return 0;
  104. }
  105. void Lexer_skip(Lexer* self) {
  106.   int c;
  107.   for (;;) {
  108.     switch (c = Lexer_get(self)) {
  109.       case ' ': case '\t': case '\r': case '\n':        break;
  110.       default: Lexer_put(self, c);                     return;
  111.     }
  112.   }
  113. }
  114. void Lexer_tokenizer_num(Lexer* self, Token* token) {
  115.   int c;
  116.   for (;;) {
  117.     switch (c = Lexer_get(self)) {
  118.       case '0': case '1': case '2': case '3': case '4':
  119.       case '5': case '6': case '7': case '8': case '9':
  120.         token->num *= 10;
  121.         token->num += c - '0';
  122.         break;
  123.       default:
  124.         Lexer_put(self, c);
  125.         return;
  126.     }
  127.   }
  128. }
  129.  
  130. typedef enum CellType_ {
  131.   CELL_TYPE_TRIPLE,
  132.   CELL_TYPE_NUM,
  133.   CELL_TYPE_X,
  134.   CELL_TYPE_MINUS_X,
  135. } CellType;
  136.  
  137. static const char* CELL_TYPE_STR[4] = {
  138.   "CELL_TYPE_TRIPLE",
  139.   "CELL_TYPE_NUM",
  140.   "CELL_TYPE_X",
  141.   "CELL_TYPE_MINUS_X",
  142. };
  143.  
  144. typedef struct Cell_ Cell;
  145.  
  146. typedef enum Operator_ {
  147.   OP_PLUS,
  148.   OP_MINUS,
  149.   OP_EQUAL,
  150. } Operator;
  151.  
  152. typedef struct Triple_ Triple;
  153.  
  154. void Cell_fput(FILE*, Cell*);
  155. Cell* Cell_new_triple(Triple*);
  156. Cell* Cell_new_num(int);
  157. Cell* Cell_new_x(void);
  158. Cell* Cell_new_minus_x(void);
  159. void Cell_delete(Cell*);
  160.  
  161. int Cell_minus(Cell*);
  162. int Cell_swap(Cell*);
  163. int Cell_solver(Cell*);
  164. int Cell_count_x(Cell*);
  165. int Cell_eval(Cell*);
  166.  
  167. void Triple_fput(FILE*, Triple*);
  168. Triple* Triple_new(Operator, Cell*, Cell*);
  169. void Triple_delete(Triple*);
  170.  
  171. struct Cell_ {
  172.   CellType type;
  173.   union {
  174.     Triple *triple;
  175.     int num;
  176.   } val;
  177. };
  178. struct Triple_ {
  179.   Operator op;
  180.   Cell* lhs;
  181.   Cell* rhs;
  182. };
  183. void Cell_fput(FILE *stream, Cell *self) {
  184.   if (NULL == self) {
  185.     fprintf(stream, "NULL");
  186.   } else {
  187.     switch (self->type) {
  188.       case CELL_TYPE_TRIPLE:
  189.         Triple_fput(stream, self->val.triple);
  190.         break;
  191.       case CELL_TYPE_NUM:
  192.         fprintf(stream, "%i", self->val.num);
  193.         break;
  194.       case CELL_TYPE_X:
  195.         fprintf(stream, "X");
  196.         break;
  197.       case CELL_TYPE_MINUS_X:
  198.         fprintf(stream, "MINUS_X");
  199.         break;
  200.       default:
  201.         fprintf(stream, "invalid type");
  202.         break;
  203.     }
  204.   }
  205. }
  206. Cell* Cell_new_triple(Triple* triple) {
  207.   Cell *self = malloc(sizeof(Cell));
  208.   self->type = CELL_TYPE_TRIPLE;
  209.   self->val.triple = triple;
  210.   return self;
  211. }
  212. Cell* Cell_new_num(int num) {
  213.   Cell *self = malloc(sizeof(Cell));
  214.   self->type = CELL_TYPE_NUM;
  215.   self->val.num = num;
  216.   return self;
  217. }
  218. Cell* Cell_new_x(void) {
  219.   Cell *self = malloc(sizeof(Cell));
  220.   self->type = CELL_TYPE_X;
  221.   return self;
  222. }
  223. Cell* Cell_new_minus_x(void) {
  224.   Cell *self = malloc(sizeof(Cell));
  225.   self->type = CELL_TYPE_MINUS_X;
  226.   return self;
  227. }
  228. void Cell_delete(Cell *self) {
  229.   if (NULL == self) { return; }
  230.   switch (self->type) {
  231.     case CELL_TYPE_TRIPLE:
  232.       Triple_delete(self->val.triple);
  233.       break;
  234.     case CELL_TYPE_NUM:
  235.     case CELL_TYPE_X:
  236.     default:
  237.       break;
  238.   }
  239.   free(self);
  240. }
  241. int Cell_minus(Cell* self) {
  242.   switch (self->type) {
  243.     case CELL_TYPE_TRIPLE:
  244.       Cell_minus(self->val.triple->lhs);
  245.       Cell_minus(self->val.triple->rhs);
  246.       break;
  247.     case CELL_TYPE_NUM:         self->val.num *= -1;            break;
  248.     case CELL_TYPE_X:           self->type = CELL_TYPE_MINUS_X; break;
  249.     case CELL_TYPE_MINUS_X:     self->type = CELL_TYPE_X;       break;
  250.   }
  251.   return 0;
  252. }
  253. int Cell_swap(Cell* self) {
  254.   if (CELL_TYPE_TRIPLE != self->type) {
  255.     fprintf(stderr, "ERROR!: Cell_solver: invalid swap.\n");
  256.     return 1;
  257.   }
  258.   if (OP_MINUS == self->val.triple->op) {
  259.     Cell_minus(self->val.triple->rhs);
  260.     self->val.triple->op = OP_PLUS;
  261.   }
  262.   Cell* tmp = self->val.triple->lhs;
  263.   self->val.triple->lhs = self->val.triple->rhs;
  264.   self->val.triple->rhs = tmp;
  265.   return 0;
  266. }
  267. int Cell_solver(Cell *self) {
  268.   Cell_fput(stdout, self); fputc('\n', stdout);
  269.   if (CELL_TYPE_TRIPLE != self->type ||
  270.       OP_EQUAL != self->val.triple->op ||
  271.       1 != Cell_count_x(self)) {
  272.     fprintf(stderr, "ERROR!: Cell_solver: invalid cell.\n");
  273.     return 1;
  274.   }
  275.   if (0 == Cell_count_x(self->val.triple->lhs)) {
  276.     Cell_swap(self);
  277.   }
  278.   while (CELL_TYPE_TRIPLE == self->val.triple->lhs->type) {
  279.     if (0 == Cell_count_x(self->val.triple->lhs->val.triple->lhs)) {
  280.       Cell_swap(self->val.triple->lhs);
  281.     }
  282.     switch (self->val.triple->lhs->val.triple->op) {
  283.       case OP_PLUS: {
  284.         Cell* tmp = self->val.triple->lhs->val.triple->rhs;
  285.         self->val.triple->lhs = self->val.triple->lhs->val.triple->lhs;
  286.         Triple* triple = Triple_new(OP_MINUS, self->val.triple->rhs, NULL);
  287.         triple->rhs = tmp;
  288.         self->val.triple->rhs = Cell_new_triple(triple);
  289.         break;
  290.       }
  291.       case OP_MINUS: {
  292.         Cell* tmp = self->val.triple->lhs->val.triple->rhs;
  293.         self->val.triple->lhs = self->val.triple->lhs->val.triple->lhs;
  294.         Triple* triple = Triple_new(OP_PLUS, self->val.triple->rhs, NULL);
  295.         triple->rhs = tmp;
  296.         self->val.triple->rhs = Cell_new_triple(triple);
  297.         break;
  298.       }
  299.       default:
  300.         fprintf(stderr, "ERROR!: Cell_solver: invalid cell.\n");
  301.         return 1;
  302.     }
  303.   }
  304.   if (CELL_TYPE_MINUS_X == self->val.triple->lhs->type) {
  305.     Cell_minus(self->val.triple->rhs);
  306.     self->val.triple->lhs->type = CELL_TYPE_X;
  307.   }
  308.   Cell_fput(stdout, self); fputc('\n', stdout);
  309.   printf("x = %i\n\n", Cell_eval(self->val.triple->rhs));
  310.   return 0;
  311. }
  312. int Cell_count_x(Cell *self) {
  313.   switch (self->type) {
  314.     case CELL_TYPE_TRIPLE:
  315.       return (Cell_count_x(self->val.triple->lhs) +
  316.               Cell_count_x(self->val.triple->rhs));
  317.     case CELL_TYPE_X:
  318.     case CELL_TYPE_MINUS_X:
  319.       return 1;
  320.     default:
  321.       return 0;
  322.   }
  323. }
  324. int Cell_eval(Cell *self) {
  325.   switch (self->type) {
  326.     case CELL_TYPE_TRIPLE:
  327.       switch (self->val.triple->op) {
  328.         case OP_PLUS:   return (Cell_eval(self->val.triple->lhs) +
  329.                                 Cell_eval(self->val.triple->rhs));
  330.         case OP_MINUS:  return (Cell_eval(self->val.triple->lhs) -
  331.                                 Cell_eval(self->val.triple->rhs));
  332.         default:
  333.           fprintf(stderr, "ERROR!: Cell_eval: invalid cell op.\n");
  334.           return 1;
  335.       }
  336.       break;
  337.     case CELL_TYPE_NUM:
  338.       return self->val.num;
  339.     case CELL_TYPE_X:
  340.     case CELL_TYPE_MINUS_X:
  341.     default:
  342.       fprintf(stderr, "ERROR!: Cell_eval: invalid cell %s.\n",
  343.               CELL_TYPE_STR[self->type]);
  344.       return 1;
  345.   }
  346. }
  347.  
  348. static const char* const OP_STR[3] = { "+", "-", "=", };
  349.  
  350. void Triple_fput(FILE *stream, Triple *self) {
  351.   fprintf(stream, "(%s, ", OP_STR[self->op]);
  352.   Cell_fput(stream, self->lhs);
  353.   fprintf(stream, ", ");
  354.   Cell_fput(stream, self->rhs);
  355.   fprintf(stream, ")");
  356. }
  357. Triple* Triple_new(Operator op, Cell* lhs, Cell* rhs) {
  358.   Triple *self = malloc(sizeof(Triple));
  359.   self->op = op;
  360.   self->lhs = lhs;
  361.   self->rhs = rhs;
  362.   return self;
  363. }
  364. void Triple_delete(Triple *self) {
  365.   if (NULL == self) { return; }
  366.   Cell_delete(self->lhs);
  367.   Cell_delete(self->rhs);
  368.   free(self);
  369. }
  370.  
  371. typedef struct Parser_ Parser;
  372. struct Parser_ {
  373.   Lexer lexer;
  374.   Token token[2];
  375.   int buf_cnt;
  376. };
  377. Parser *Parser_init(Parser*, FILE*, int);
  378. void Parser_final(Parser*);
  379. Token *Parser_get(Parser*);
  380. int Parser_put(Parser*, Token*);
  381. int Parser_start(Parser*);
  382. Cell *Parser_assign(Parser*);
  383. Cell *Parser_expr(Parser*);
  384. Cell *Parser_expr_tail(Parser*);
  385. Cell *Parser_signed(Parser*);
  386. Cell *Parser_elem(Parser*);
  387. int parse_file(FILE*, int);
  388. int parse_buffer(const char*, size_t len);
  389. int parse_str(const char*);
  390. Parser *Parser_init(Parser *self, FILE *file, int close) {
  391.   Lexer_init(&self->lexer, file, close);
  392.   self->buf_cnt = 0;
  393.   return self;
  394. }
  395. void Parser_final(Parser *self) {
  396.   if (NULL == self) { return; }
  397.   Lexer_final(&self->lexer);
  398. }
  399. Token *Parser_get(Parser* self) {
  400.   if (0 == self->buf_cnt) {
  401.     if (0 != Lexer_tokenizer(&self->lexer, &self->token[0])) {
  402.       fprintf(stderr, "ERROR!: Parser_get: failed Lexer_tokenizer.\n");
  403.       return NULL;
  404.     }
  405.     return &self->token[0];
  406.   }
  407.   return &self->token[self->buf_cnt--];
  408. }
  409. int Parser_put(Parser* self, Token* token) {
  410.   if (1 <= self->buf_cnt) {
  411.     fprintf(stderr, "ERROR!: Parser_put: buffer full.\n");
  412.     return 1;
  413.   }
  414.   memcpy(&self->token[++self->buf_cnt], token, sizeof(Token));
  415.   return 0;
  416. }
  417. int Parser_start(Parser *self) {
  418.   for(;;) {
  419.     Cell* cell = Parser_assign(self);
  420.     if (!cell) { return 1; }
  421.     // Cell_fput(stdout, cell); putc('\n', stdout);
  422.     Cell_solver(cell);
  423.     Cell_delete(cell);
  424.   }
  425. }
  426. Cell *Parser_assign(Parser *self) {
  427.   Cell* cell = Parser_expr(self);
  428.   if(!cell) { return NULL; }
  429.   Token *token = Parser_get(self);
  430.   switch (token->type) {
  431.     case TOKEN_TYPE_EQUAL:
  432.       cell = Cell_new_triple(Triple_new(OP_EQUAL, cell, NULL));
  433.       break;
  434.     default:
  435.       fprintf(stderr, "ERROR!: Parser_assign: invalid cell.\n");
  436.       Cell_delete(cell);
  437.       return NULL;
  438.   }
  439.   Cell* rhs = Parser_expr(self);
  440.   if(!rhs) {
  441.     fprintf(stderr, "ERROR!: Parser_assign: invalid cell.\n");
  442.     Cell_delete(cell);
  443.     return NULL;
  444.   }
  445.   cell->val.triple->rhs = rhs;
  446.   token = Parser_get(self);
  447.   switch (token->type) {
  448.     case TOKEN_TYPE_DELIM:
  449.       break;
  450.     default:
  451.       fprintf(stderr, "ERROR!: Parser_assign: invalid cell.\n");
  452.       Cell_delete(cell);
  453.       return NULL;
  454.   }
  455.   return cell;
  456. }
  457. Cell *Parser_expr(Parser *self) {
  458.   Cell* cell = Parser_signed(self);
  459.   if(!cell) { return NULL; }
  460.   for (;;) {
  461.     Cell* tail = Parser_expr_tail(self);
  462.     if(!tail) { break; }
  463.     tail->val.triple->lhs = cell;
  464.     cell = tail;
  465.   }
  466.   return cell;
  467. }
  468. Cell *Parser_expr_tail(Parser *self) {
  469.   Cell* cell = NULL;
  470.   Token *token = Parser_get(self);
  471.   switch (token->type) {
  472.     case TOKEN_TYPE_PLUS: {
  473.       Cell* rhs = Parser_signed(self);
  474.       if (NULL == rhs) { Parser_put(self, token); return NULL; }
  475.       cell = Cell_new_triple(Triple_new(OP_PLUS, NULL, rhs));
  476.       break;
  477.     }
  478.     case TOKEN_TYPE_MINUS: {
  479.       Cell* rhs = Parser_signed(self);
  480.       if (NULL == rhs) { Parser_put(self, token); return NULL; }
  481.       cell = Cell_new_triple(Triple_new(OP_MINUS, NULL, rhs));
  482.       break;
  483.     }
  484.     default:
  485.       Parser_put(self, token);
  486.       return NULL;
  487.   }
  488.   return cell;
  489. }
  490. Cell *Parser_signed(Parser *self) {
  491.   Token *token = Parser_get(self);
  492.   switch (token->type) {
  493.     case TOKEN_TYPE_NUM:                return Cell_new_num(token->num);
  494.     case TOKEN_TYPE_X:                  return Cell_new_x();
  495.     case TOKEN_TYPE_PLUS: {
  496.       Cell* cell = Parser_elem(self);
  497.       if(!cell) { Parser_put(self, token); return NULL; }
  498.       return cell;
  499.     }
  500.     case TOKEN_TYPE_MINUS: {
  501.       Cell* cell = Parser_elem(self);
  502.       if(!cell) { Parser_put(self, token); return NULL; }
  503.       switch (cell->type) {
  504.         case CELL_TYPE_NUM:     cell->val.num *= -1;            break;
  505.         case CELL_TYPE_X:       cell->type = CELL_TYPE_MINUS_X; break;
  506.         default:
  507.           fprintf(stderr, "ERROR!: Parser_signed: invalid cell.\n");
  508.           Cell_delete(cell);
  509.           return NULL;
  510.       }
  511.       return cell;
  512.     }
  513.     default: Parser_put(self, token);   return NULL;
  514.   }
  515. }
  516. Cell *Parser_elem(Parser *self) {
  517.   Token *token = Parser_get(self);
  518.   switch (token->type) {
  519.     case TOKEN_TYPE_NUM:                return Cell_new_num(token->num);
  520.     case TOKEN_TYPE_X:                  return Cell_new_x();
  521.     default: Parser_put(self, token);   return NULL;
  522.   }
  523. }
  524. int parse_file(FILE* file, int close) {
  525.   Parser parser;
  526.   Parser_init(&parser, file, close);
  527.   Parser_start(&parser);
  528.   Parser_final(&parser);
  529.   return 0;
  530. }
  531. int parse_buffer(const char* buffer, size_t length) {
  532.   FILE* file = tmpfile();
  533.   fwrite(buffer, 1, length, file);
  534.   fseek(file, 0, SEEK_SET);
  535.   return parse_file(file, 1);
  536. }
  537. int parse_str(const char* str) {
  538.   return parse_buffer(str, strlen(str));
  539. }
  540.  
  541. int main(int argc, char* argv[]) {
  542.   //parse_str("5 - 6 = x; x + 7 = 32; 4 - x = 43; 1 + -3 = 4 - 7 + -x;");
  543.   parse_file(stdin, 0);
  544.   return 0;
  545. }
  546.  
Success #stdin #stdout 0s 2312KB
comments (?)
stdin
copy 
5 - 6 = x;
x + 7 = 32;
4 - x = 43;
1 + -3 = 4 - 7 + -x;
stdout
copy 
(=, (-, 5, 6), X)
(=, X, (-, 5, 6))
x = -1

(=, (+, X, 7), 32)
(=, X, (-, 32, 7))
x = 25

(=, (-, 4, X), 43)
(=, X, (-, -43, -4))
x = -39

(=, (+, 1, -3), (+, (-, 4, 7), MINUS_X))
(=, X, (-, (+, -1, 3), (-, -4, -7)))
x = -1
https://ideone.com/3tNxUx
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!