fork(6) download
copy 
  1. /**************************************
  2.  * eggache? egg hurt?
  3.  * support: + - * / % ^ ( )
  4.  *-------------------------------------
  5.  * original
  6.  * E -> E+T|E-T|T
  7.  * T -> T*F|T/F|T%F|F
  8.  * F -> N^F|N
  9.  * N -> (E)|-VAL|+VAL|VAL
  10.  *-------------------------------------
  11.  * remove left recursive
  12.  * E -> TE'
  13.  * E'-> +TE'|-TE'|e
  14.  * T -> FT'
  15.  * T'-> *FT'|/FT'|%FT'|e
  16.  * F -> NF'
  17.  * F'-> ^F|e
  18.  * N -> (E)|-VAL|+VAL|VAL
  19.  * ------------------------------------
  20.  * char set [0-9]|.|e|+|-|*|/|%|^|(|)
  21.  * VAL := [0-9]+(\.[0-9]+)?(e(+|-)?[0-9]+)?
  22.  * ************************************/
  23.  
  24. #include <stdio.h>
  25. #include <math.h>
  26.  
  27. #define ARRAY_SIZE(a) (int)(sizeof(a)/sizeof(*a))
  28. typedef enum {
  29.     LLS_NUM,
  30.     LLS_ADD,
  31.     LLS_SUB,
  32.     LLS_MUL,
  33.     LLS_DIV,
  34.     LLS_MOD,
  35.     LLS_POW,
  36.     LLS_LBR,
  37.     LLS_RBR,
  38.     LLS_END,
  39.     LLS_ERR,
  40. } LLSTATE;
  41.  
  42. typedef enum {
  43.     LLE_OK,
  44.     LLE_INVALID_CHAR,
  45.     LLE_BK_NOT_MATCH,
  46.     LLE_NOT_A_NUM,
  47.     LLE_NOT_OPERATOR,
  48. } LLERROR;
  49.  
  50. #define LL_VAL_DEFVAL 0
  51. typedef double LL_VAL;
  52.  
  53. typedef struct LL_state {
  54.     const char* expr;
  55.     LL_VAL val;
  56.     int read;
  57.     LLSTATE state;
  58.     int errcode;
  59. } LL_state;
  60.  
  61. LL_VAL LL_E( LL_state* self );
  62. LL_VAL LL_T( LL_state* self );
  63. LL_VAL LL_F( LL_state* self );
  64.  
  65. LL_VAL LL_NUM( LL_state* self ) {
  66.     LL_VAL ret;
  67.     int len;
  68.     sscanf( &self->expr[self->read],
  69.             "%lf%n", &ret, &len ); // %lf !! I'm lazy
  70.     self->read += len;
  71.     return ret;
  72. }
  73.  
  74. LLSTATE LL_PARSE( LL_state* self ) {
  75.     char c = self->expr[self->read];
  76.     while ( c == ' ' ) //ignore space
  77.         c = self->expr[++self->read];
  78.     if ( c >= '0' && c <= '9' ) {
  79.         self->val = LL_NUM( self );
  80.         self->state = LLS_NUM;
  81.     } else {
  82.         ++self->read;
  83.         if ( c == '+' ) {
  84.             self->state = LLS_ADD;
  85.         } else if ( c == '-' ) {
  86.             self->state = LLS_SUB;
  87.         } else if ( c == '*' ) {
  88.             self->state = LLS_MUL;
  89.         } else if ( c == '/' ) {
  90.             self->state = LLS_DIV;
  91.         } else if ( c == '%' ) {
  92.             self->state = LLS_MOD;
  93.         } else if ( c == '^' ) {
  94.             self->state = LLS_POW;
  95.         } else if ( c == '(' ) {
  96.             self->state = LLS_LBR;
  97.         } else if ( c == ')' ) {
  98.             self->state = LLS_RBR;
  99.         } else if ( c == '\0' ) {
  100.             self->state = LLS_END;
  101.         } else {
  102.             self->errcode = LLE_INVALID_CHAR;
  103.             self->state = LLS_ERR;
  104.         }
  105.     }
  106.     return self->state;
  107. }
  108.  
  109. LL_VAL LL_N( LL_state* self ) { // F -> (E)|-VAL|+VAL|VAL
  110.     LL_VAL ret = LL_VAL_DEFVAL;
  111.     int lbr_pos = self->read;
  112.     if ( self->state == LLS_ERR ) return ret;
  113.     switch ( self->state ) {
  114.     case LLS_LBR:
  115.         LL_PARSE( self );
  116.         ret = LL_E( self );
  117.         if ( self->state != LLS_RBR ) {
  118.             if ( self->errcode == LLE_OK ) {
  119.                 self->errcode = LLE_BK_NOT_MATCH;
  120.                 self->read = lbr_pos;
  121.             }
  122.             self->state = LLS_ERR;
  123.             return ret;
  124.         }
  125.         break;
  126.     case LLS_ADD:
  127.     case LLS_SUB:
  128.         if ( 1 ) {
  129.             LLSTATE s = self->state;
  130.             LL_PARSE( self );
  131.             if ( self->state != LLS_NUM ) {
  132.                 self->errcode = LLE_NOT_A_NUM;
  133.                 self->state = LLS_ERR;
  134.                 return ret;
  135.             }
  136.             ret = ( s == LLS_ADD ? self->val : -self->val ) ;
  137.         }
  138.         break;
  139.     case LLS_NUM:
  140.         ret = self->val;
  141.         break;
  142.     default:
  143.         self->errcode = LLE_NOT_A_NUM;
  144.         self->state = LLS_ERR;
  145.         return ret;
  146.     }
  147.     LL_PARSE( self );
  148.     return ret;
  149. }
  150.  
  151. LL_VAL LL_F_( LL_state* self ) { // F'-> ^F|e
  152.     LL_VAL val = self->val;
  153.     if ( self->state == LLS_ERR ) return val;
  154.     switch ( self->state ) {
  155.     case LLS_POW:
  156.         LL_PARSE( self );
  157.         return pow( val, LL_F( self ) );
  158.     case LLS_ADD:
  159.     case LLS_SUB:
  160.     case LLS_MUL:
  161.     case LLS_DIV:
  162.     case LLS_MOD:
  163.     case LLS_RBR:
  164.     case LLS_END:
  165.     case LLS_ERR:
  166.         return val;
  167.     default:
  168.         self->errcode = LLE_NOT_OPERATOR;
  169.         self->state = LLS_ERR;
  170.         return val;
  171.     }
  172. }
  173.  
  174. LL_VAL LL_F( LL_state* self ) { // F -> NF'
  175.     self->val = LL_N( self );
  176.     return LL_F_( self );
  177. }
  178.  
  179. LL_VAL LL_T_( LL_state* self ) { // T'-> *FT'|/FT'|%FT'|e
  180.     LL_VAL val = self->val;
  181.     if ( self->state == LLS_ERR ) return val;
  182.     switch ( self->state ) {
  183.     case LLS_MUL:
  184.         LL_PARSE( self );
  185.         self->val = val * LL_F( self );
  186.         return LL_T_( self );
  187.     case LLS_DIV:
  188.         LL_PARSE( self );
  189.         self->val = val / LL_F( self );
  190.         return LL_T_( self );
  191.     case LLS_MOD:
  192.         LL_PARSE( self );
  193.         self->val = fmod( val, LL_F( self ) );
  194.         return LL_T_( self );
  195.     case LLS_ADD:
  196.     case LLS_SUB:
  197.     case LLS_RBR:
  198.     case LLS_END:
  199.     case LLS_ERR:
  200.         return val;
  201.     default:
  202.         self->errcode = LLE_NOT_OPERATOR;
  203.         self->state = LLS_ERR;
  204.         return val;
  205.     }
  206. }
  207.  
  208. LL_VAL LL_T( LL_state* self ) { // T -> FT'
  209.     self->val = LL_F( self );
  210.     return LL_T_( self );
  211. }
  212.  
  213. LL_VAL LL_E_( LL_state* self ) { // E'-> +TE'|-TE'|e
  214.     LL_VAL val = self->val;
  215.     if ( self->state == LLS_ERR ) return val;
  216.     switch ( self->state ) {
  217.     case LLS_ADD:
  218.         LL_PARSE( self );
  219.         self->val = val + LL_T( self );
  220.         return LL_E_( self );
  221.     case LLS_SUB:
  222.         LL_PARSE( self );
  223.         self->val = val - LL_T( self );
  224.         return LL_E_( self );
  225.     case LLS_RBR:
  226.     case LLS_END:
  227.     case LLS_ERR:
  228.         return val;
  229.     default:
  230.         self->errcode = LLE_NOT_OPERATOR;
  231.         self->state = LLS_ERR;
  232.         return val;
  233.     }
  234. }
  235.  
  236. LL_VAL LL_E( LL_state* self ) { // E -> TE'
  237.     self->val = LL_T( self );
  238.     return LL_E_( self );
  239. }
  240.  
  241. int LL_calc( const char* expr, LL_VAL* val, int* pos ) {
  242.     LL_state self = {expr, *val};
  243.     LL_PARSE( &self );
  244.     *val = LL_E( &self );
  245.     *pos = self.read;
  246.     if ( self.errcode == LLE_OK && self.state != LLS_END ) {
  247.         self.errcode = LLE_BK_NOT_MATCH;
  248.     }
  249.     return self.errcode;
  250. }
  251.  
  252. const char* LL_get_err_string( int errcode ) {
  253.     static const char* errstr[] = {
  254.         "",
  255.         "invalid character",
  256.         "bracket does not match",
  257.         "not a number",
  258.         "need operator",
  259.     };
  260.     if ( errcode < 0 || errcode > ARRAY_SIZE( errstr ) ) {
  261.         errcode = 0;
  262.     }
  263.     return errstr[errcode];
  264. }
  265.  
  266. int main() {
  267.     char str[1024];
  268.     LL_VAL v;
  269.     int cnt_out = 0;
  270.     while ( gets( str ) ) {
  271.         int r, pos;
  272.         r = LL_calc( str, &v, &pos );
  273.         printf( "out[%d]: " , ++cnt_out );
  274.         if ( r == LLE_OK ) {
  275.             printf( "%s= %.10g\n", str, v );
  276.         } else {
  277.             printf( "error code %d: %s\n", r, LL_get_err_string( r ) );
  278.             printf( "%s\n", str );
  279.             printf( "%*s\n", pos, "^" );
  280.         }
  281.     }
  282.     return 0;
  283. }
  284.  
Success #stdin #stdout 0s 2256KB
comments (?)
stdin
copy 
1+2*3
(1+2)*3
(1+2)*(3+4)
5/(5-1/5)
(1+2
(1+)
1+1)
10*-5
1--(1)
3&5
4*(1 2)
2^32
2^2^4
2^-4
-2^3
-2^4
-2%3
19%5
stdout
copy 
out[1]: 1+2*3= 7
out[2]: (1+2)*3= 9
out[3]: (1+2)*(3+4)= 21
out[4]: 5/(5-1/5)= 1.041666667
out[5]: error code 2: bracket does not match
(1+2
^
out[6]: error code 3: not a number
(1+)
   ^
out[7]: error code 2: bracket does not match
1+1)
   ^
out[8]: 10*-5= -50
out[9]: error code 3: not a number
1--(1)
   ^
out[10]: error code 1: invalid character
3&5
 ^
out[11]: error code 4: need operator
4*(1 2)
     ^
out[12]: 2^32= 4294967296
out[13]: 2^2^4= 65536
out[14]: 2^-4= 0.0625
out[15]: -2^3= -8
out[16]: -2^4= 16
out[17]: -2%3= -2
out[18]: 19%5= 4
https://ideone.com/o2Ag4
language:
C (gcc 8.3)
created:
10 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!