#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
#include <math.h>

/* lexer */
typedef enum {INT_TYPE, REAL_TYPE, CHAR_TYPE, SYMBOL, EOF_TOK, END_LINE, UNKNOWN} Type;
typedef enum {ADD_SYMB, SUB_SYMB, MUL_SYMB, DIV_SYMB,
              POW_SYMB, MOD_SYMB, LBRACK, RBRACK, ASSIGN,
              FACT_SYMB} Symbol;
typedef enum {MISSING_FRAC,UNKNOWN_TOKEN,MISSING_RBRACK,
              MISSING_LBRACK, MISSING_OPERAND,
              UNKNOWN_ERROR, MISSING_VARIABLE,
              REAL_MOD, TYPE_ERROR,
              VALUE_ERROR} Error;

typedef union
{
  int int_val;
  double real_val;
  char id;
  Symbol symb;
} Value;

typedef struct
{
  Type type;
  Value val;
} Token;

double get_fract_part(void);
void next_char(void);
Token get_number(void);
Token get_token(void);
void print_token(Token* t);
void empty_buffer(void);

char current_char;
jmp_buf env;

void error(Error err);

/* parser */
typedef enum {INT, REAL, NAN} Num_Type;
typedef enum {ADD, SUB, MUL, DIV, MOD, POW, FACT} Operator;
typedef enum {TREE, LEAF} Node_Type;
typedef struct Expression Expression;

typedef union 
{
  int integer;
  double real;
} Int_or_Real;

typedef struct
{
  Num_Type type;
  Int_or_Real val;
} Number;

typedef union
{
  Expression *expression;
  Number num;
} Node;

typedef struct
{
  Node_Type type;
  Node node;
} Tree;

struct Expression
{
  Operator op;
  Tree* left;
  Tree* right;
};

Tree* parse_expression(void);
Tree* parse_right_expression(Tree* n);
Tree* parse_term(void);
Tree* parse_right_term(Tree* n);
Tree* parse_factor(void);
void advance(void);
void free_tree(Tree* tree);

Token token;
Tree* head;

void init_variables(void);
Number variables[26];
void copy_num(Number *dest, const Number *src);

/* calc */
Number solve(Tree* tree);
double calc_int(int a, int b, Operator o);
double calc_doubles(double a, double b, Operator o);
Number get_res(Number a, Number b, Operator o);
void print_number(Number n);
Number get_res_unary(Number n, Operator o);

/* other */
int int_pow(int x, int n);
int fact(int n);

int main(void)
{
  Token tok;
  init_variables();
  while(tok.type != EOF_TOK)
  {
    printf("- ");
    next_char();
    if(current_char == '\n' || current_char == EOF)
    {
      printf("Exit...\n");
      break;
    }
    else if(!setjmp(env))
    {
      Tree* tree = NULL;
      advance();
      tree = parse_expression();
      if(token.type != EOF_TOK && token.type != END_LINE)
      {
        error(MISSING_LBRACK);
      }
      print_number(solve(tree));
      free_tree(tree);
    }
    empty_buffer();
  }
  
  return EXIT_SUCCESS;
}


/* ----- lexer ---- */
void empty_buffer(void)
{
  while(current_char != EOF && current_char != '\n')
    next_char();
}

void next_char(void)
{
  current_char = getchar();
}

void error(Error err)
{
  free_tree(head);
  printf("Error: ");
  switch(err)
  {
  case MISSING_FRAC:
    printf("fractional part missing.\n");
    break;
  case UNKNOWN_TOKEN:
    printf("token %c not recognized.\n", token.val.id);
    break;
  case MISSING_RBRACK:
    printf("right bracket is missing.\n");
    break;
  case MISSING_LBRACK:
    printf("left bracket is missing.\n");
    break;
  case MISSING_OPERAND:
    printf("operand is missing.\n");
    break;
  case MISSING_VARIABLE:
    printf("variable %c does not exist.\n", token.val.id);
    break;
  case TYPE_ERROR:
    printf("operation with incompatible type(s).\n");
    break;
  case VALUE_ERROR:
    printf("operation with incompatible value(s).\n");
    break;
  case UNKNOWN_ERROR:
  default:
    printf("unknown error.\n");
    break;
  }
  longjmp(env,-1);
}

Token get_token(void)
{
  while(current_char == ' ' || current_char == '\t')
  {
    next_char();
  }
  if(current_char >= '0' && current_char <= '9')
  {
    return get_number();
  }
  else if(current_char >= 'a' && current_char <= 'z')
  {
    Token tok;
    tok.type = CHAR_TYPE;
    tok.val.id = current_char;
    next_char();
    return tok;
  }
  else
  {
    Token tok;
    tok.type = SYMBOL;
    switch(current_char)
    {
    case '+':
      tok.val.symb = ADD_SYMB;
      break;
    case '-':
      tok.val.symb = SUB_SYMB;
      break;
    case '*':
      tok.val.symb = MUL_SYMB;
      break;
    case '/':
      tok.val.symb = DIV_SYMB;
      break;
    case '%':
      tok.val.symb = MOD_SYMB;
      break;
    case '^':
      tok.val.symb = POW_SYMB;
      break;
    case '!':
      tok.val.symb = FACT_SYMB;
      break;
    case '(':
      tok.val.symb = LBRACK;
      break;
    case ')':
      tok.val.symb = RBRACK;
      break;
    case '=':
      tok.val.symb = ASSIGN;
      break;
    case '\n':
      tok.type = END_LINE;
      return tok;
    case EOF:
      tok.type = EOF_TOK;
      return tok;
    default:
      tok.type = UNKNOWN;
      tok.val.id = current_char;
      return tok;
    }
    next_char();
    return tok;
  }  
}

Token get_number(void) 
{
  Token tok;
  tok.val.int_val = 0;
  tok.type = INT_TYPE;
  while(current_char >= '0' && current_char <= '9')
  {
    tok.val.int_val = tok.val.int_val * 10 + current_char - '0';
    next_char();
  }
  if(current_char == '.')
  {
    next_char();
    tok.val.real_val = tok.val.int_val + get_fract_part();
    tok.type = REAL_TYPE;
  }
  return tok;
}

double get_fract_part(void)
{
  int n;
  double d = 0.0;
  if(!(current_char >= '0' && current_char <= '9'))
    error(MISSING_FRAC);
  for(n = 10; current_char >= '0' && current_char <= '9'; n *= 10)
  {
    d += (current_char - '0') / (double)n;
    next_char();
  }
  return d;
}

/* ----- parser ---- */

void advance(void)
{
  token = get_token();
  if(token.type == UNKNOWN)
    error(UNKNOWN_TOKEN);
}

void init_variables(void)
{
  int i;
  for(i = 0; i < 26; i++)
  {
    Number b;
    b.type = NAN;
    copy_num(&variables[i], &b);
  }
}

Tree* parse_expression(void)
{
  Tree* left_tree = parse_term();
  head = left_tree;
  return parse_right_expression(left_tree);  
}

Tree* parse_right_expression(Tree* n)
{
  if(token.type == SYMBOL && 
     (token.val.symb == ADD_SYMB || token.val.symb == SUB_SYMB))
  {
    Tree* tree = malloc(sizeof(Tree));
    tree->node.expression = malloc(sizeof(Expression));
    tree->node.expression->left = n;
    tree->type = TREE;
    tree->node.expression->op = token.val.symb == ADD_SYMB ? ADD : SUB;
    advance();
    tree->node.expression->right = parse_term();
    head = tree;
    return parse_right_expression(tree);
  }
  else
  {
    return n;
  }  
}

Tree* parse_term(void)
{
  Tree* left_tree = parse_factor();
  return parse_right_term(left_tree);
}

Tree* parse_right_term(Tree* n)
{
  if(token.type == SYMBOL && 
     (token.val.symb == MUL_SYMB || token.val.symb == DIV_SYMB
      || token.val.symb == MOD_SYMB || token.val.symb == POW_SYMB))
  {
    Tree* tree = malloc(sizeof(Tree));
    Operator tmp;
    tree->node.expression = malloc(sizeof(Expression));
    tree->type = TREE;
    if(token.val.symb == MUL_SYMB)
      tmp = MUL;
    else if(token.val.symb == DIV_SYMB)
      tmp = DIV;
    else if(token.val.symb == MOD_SYMB)
      tmp = MOD;
    else if(token.val.symb == POW_SYMB)
      tmp = POW;
    tree->node.expression->op = tmp;
    tree->node.expression->left = n;
    advance();
    tree->node.expression->right = parse_factor();
    head = tree;
    return parse_right_term(tree);
  }
  else
  {
    return n;
  }
}

Tree* parse_factor(void)
{
  Tree* tree = NULL;
  if(token.type == INT_TYPE || token.type == REAL_TYPE)
  {
    tree = malloc(sizeof(Tree));
    tree->type = LEAF;
    if(token.type == INT_TYPE)
    {
      tree->node.num.type = INT;
      tree->node.num.val.integer = token.val.int_val;
    }
    else
    {
      tree->node.num.type = REAL;
      tree->node.num.val.real = token.val.real_val;
    }
    advance();
  }
  else if(token.type == SYMBOL && token.val.symb == LBRACK)
  {
    advance();
    tree = parse_expression();
    if(token.type != SYMBOL || token.val.symb != RBRACK)
    {
      error(MISSING_RBRACK);
    }
    advance();
  }
  else if(token.type == CHAR_TYPE)
  {
    Token tmp = token;
    advance();
    if(token.type == SYMBOL && token.val.symb == ASSIGN)
    {
      advance();
      tree = parse_expression();
      variables[tmp.val.id - 'a'] = solve(tree);
      return tree;
    }
    if(variables[tmp.val.id - 'a'].type == NAN)
    {
      token = tmp;
      error(MISSING_VARIABLE);
    }
    tree = malloc(sizeof(Tree));
    tree->type = LEAF;
    copy_num(&(tree->node.num), &variables[tmp.val.id - 'a']);
  }
  else if(token.type == SYMBOL && token.val.symb == RBRACK)
  {
    error(MISSING_LBRACK);
  }
  else if(token.type == SYMBOL && token.val.symb == ADD_SYMB)
  {
    return parse_factor();
  }
  else if(token.type == SYMBOL && token.val.symb == SUB_SYMB)
  {
    tree = malloc(sizeof(Tree));
    advance();
    tree->node.expression = malloc(sizeof(Expression));
    tree->node.expression->op = SUB;
    tree->node.expression->left = NULL;
    tree->node.expression->right = parse_factor();
  }
  else
  {
    error(MISSING_OPERAND);
  }
  if(token.type == SYMBOL && token.val.symb == FACT_SYMB)
  {
    Tree* new_tree = malloc(sizeof(Tree));
    new_tree->node.expression = malloc(sizeof(Expression));
    new_tree->node.expression->op = FACT;
    new_tree->node.expression->left = tree;
    new_tree->node.expression->right = NULL;
    tree = new_tree;
    advance();
  }
  return tree;
}

/* calc */
int calc_ints(int a, int b, Operator o)
{
  switch(o)
  {
  case ADD:
    return a + b;
  case SUB:
    return a - b;
  case MUL:
    return a * b;
  case DIV:
    return a / b;
  case MOD:
    return a % b;
  case POW:
    return int_pow(a, b);
  default:
    error(UNKNOWN_ERROR);
    return 0;
  }
}

double calc_doubles(double a, double b, Operator o)
{
  switch(o)
  {
  case ADD:
    return a + b;
  case SUB:
    return a - b;
  case MUL:
    return a * b;
  case DIV:
    return a / b;
  case MOD:
    error(REAL_MOD);
  case POW:
    return pow(a, b);
  default:
    error(UNKNOWN_ERROR);
    return 0;
  }
}

Number get_res(Number a, Number b, Operator o)
{
  Number sol;
  if(a.type == INT && b.type == INT)
  {
    sol.type = INT;
    sol.val.integer = calc_ints(a.val.integer,b.val.integer, o);
  }
  else
  {
    double d1 = a.type == REAL ? a.val.real : a.val.integer;
    double d2 = b.type == REAL ? b.val.real : b.val.integer;
    sol.type = REAL;
    sol.val.real = calc_doubles(d1,d2,o);
  }
  return sol;
}

Number get_res_unary(Number n, Operator o)
{
  if(o == FACT)
  {
    if(n.type == INT)
    {
      if(n.val.integer < 0)
      {
        error(VALUE_ERROR);
      }
      n.val.integer = fact(n.val.integer);
    }
    else
    {
      error(TYPE_ERROR);
    }
  }
  else if(o == SUB)
  {
    if(n.type == INT)
    {
      n.val.integer *= -1;
    }
    else
    {
      n.val.real *= -1;
    }
  }
  else
  {
    error(UNKNOWN_ERROR);
  }
  return n;
}

Number solve(Tree* tree)
{
  if(tree->type == LEAF)
  {
    return tree->node.num;
  }
  else
  {
    Operator o = tree->node.expression->op;
    Tree* left = tree->node.expression->left;
    Tree* right = tree->node.expression->right;
    if(left == NULL)
    {
      return get_res_unary(solve(right), o);
    }
    if(right == NULL)
    {
      return get_res_unary(solve(left), o);
    }
    return get_res(solve(left), solve(right), o);
  }
}

void print_number(Number n)
{
  switch(n.type)
  {
  case INT:
    printf("%d\n", n.val.integer);
    break;
  case REAL:
    printf("%f\n", n.val.real);
    break;
  default:
    error(UNKNOWN_ERROR);
    break;
  }
}

void free_tree(Tree* tree)
{
  if(tree == NULL)
    return;
  if(tree->type == LEAF)
  {
    free(tree);
  }
  else
  {
    free_tree(tree->node.expression->left);
    free_tree(tree->node.expression->right);
    free(tree->node.expression);
    free(tree);
  }
}

void copy_num(Number *dest, const Number *src)
{
  dest->type = src->type;
  if(src->type == INT)
  {
    dest->val.integer = src->val.integer;
  }
  else if(src->type == REAL)
  {
    dest->val.real = src->val.real;
  }
}


/* other */
int int_pow(int x, int n)
{
  int i, res;
  for(i = 0, res = 1; i < n; i++)
  {
    res *= x;
  }
  return res;
}

int fact(int n)
{
  int i, res;
  for(i = 1, res = 1; i <= n; i++)
  {
    res *= i;
  }
  return res;    
}

- 1+3
4
- 1.2+8.4
9.600000
- (2*4+1)/2
4
- (2*4+1)/2.0
4.500000
- 2+4)
Error: left bracket is missing.
- (2+4 -  
Error: operand is missing.
- (2+4-"
Error: token " not recognized.
- (8*2
Error: right bracket is missing.
- (2 + 4) * 4 + (9 / 2.0) 
28.500000
- a = 7      
7
- b = a^2 % 4
1
- c = a + b
8
- (a + 3*b) % c
2
- -c + 2*a
6
- a! / 10
504

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>

/* #define DEBUG */

typedef enum Type
{
    NONE = 0,
    NOMBRE,
    OPERATEUR
} Type;

typedef struct Pile
{
    Type type;
    double valeur;
    struct Pile * suivant;
} Pile;

Pile * Pile_Constructeur(void);
void Pile_Ajout(Pile **pile, double valeur);
double Pile_Enleve(Pile **pile);
void Pile_Destructeur(Pile **pile);
void Pile_Afficher(Pile **pile);

int isoperator(char c);
double Calcul_NPI(double n1, double n2, char c);
void Analyse_NPI(const char * chaine);

Pile * Pile_Constructeur(void)
{
    Pile *pile = malloc(sizeof(*pile));

    pile->valeur = 0;
    pile->type = NONE;
    pile->suivant = NULL;

    return (pile);
}

void Pile_Ajout(Pile **pile, double valeur)
{
    Pile *nouveau = malloc(sizeof(*nouveau));

    nouveau->valeur = valeur;
    nouveau->suivant = *pile;
    *pile = nouveau;;
}

double Pile_Enleve(Pile **pile)
{
    double valeur = 0.0;
    Pile * temporaire;

    if (pile != NULL && *pile != NULL)
    {
        temporaire = *pile;
        valeur = temporaire->valeur;
        free(*pile), *pile = NULL;

        *pile = temporaire->suivant;
    }

    free(temporaire);

    return valeur;
}

void Pile_Destructeur(Pile **pile)
{
    while (*pile != NULL)
    {
        Pile_Enleve(pile);
    }
}

void Pile_Afficher(Pile **pile)
{
    Pile * affiche;

    affiche = *pile;

    puts("");

    while (affiche != NULL)
    {
        printf("%f\n", affiche->valeur);
        affiche = affiche->suivant;
    }

    puts("NULL\n");
}

int isoperator(char c)
{
    int i, taille;
    const char operations[] = {'+', '-', '*', '/', '%', '^'};

    taille = sizeof(operations) / sizeof(*operations);

    for (i = 0; i < taille; i++)
    {
        if (c == operations[i])
            return 1;
    }

    return 0;
}

double Calcul_NPI(double n1, double n2, char c)
{
    if (c == '+')
        return n2 + n1;
    else if (c == '-')
        return n2 - n1;
    else if (c == '*')
        return n2 * n1;
    else if (c == '/')
        return n2 / n1;
    else if (c == '%')
        return (int)n2 % (int)n1;
    else if (c == '^')
        return pow(n2, n1);
    else
        return NONE;
}

void Analyse_NPI(const char * chaine)
{
    Pile * pile;
    double n1, n2, resultat;

    pile = Pile_Constructeur();
    n1 = n2 = resultat = 0;

    do
    {
        if (isdigit(*chaine))
        {
            Pile_Ajout(&pile, strtod(chaine, NULL));

            while (*chaine != ' ' && *chaine++ != '\n');
        }

        else if (isoperator(*chaine))
        {
            n1 = Pile_Enleve(&pile);
            n2 = Pile_Enleve(&pile);

            resultat = Calcul_NPI(n1, n2, *chaine);

            Pile_Ajout(&pile, resultat);
        }

    } while (*chaine++);

#ifdef DEBUG
    Pile_Afficher(&pile);
#endif

    printf("Resultat = %3.f\n", pile->valeur);

    Pile_Destructeur(&pile);
}

int main(void)
{
    char s[200];
    fgets(s, sizeof(s), stdin);

    Analyse_NPI(s);

    return EXIT_SUCCESS;
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <errno.h>
#include <ctype.h>

#define TAILLE 200
#define N_OP 8

enum
{
    E_NO = 0,
    E_PFER,
    E_DIV,
    E_MALLOC,
    NB_ERR
};

typedef enum Type
{
    NUL,
    NOMBRE,
    OPERATEUR,
    P_OUVRANTE,
    P_FERMANTE
} Type;

typedef enum Operation
{
    NONE,
    ADD,
    SUB,
    MUL,
    DIV,
    MOD,
    POW
} Operation;

typedef struct Token
{
    Operation operation;
    char signe;
    int priorite;
} Token;

typedef struct Arbre
{
    Token token;
    Type type;
    struct Arbre * droite;
    struct Arbre * gauche;
    double valeur;

} Arbre;

void Afficher_Erreur(int num);
Arbre * Regle1(char * s, int op, int prio);
Arbre * Regle2(char ** s);
Arbre * Regle3(char ** s);
Arbre * Analyse_Chaine(char * chaine);
double Calcul_Courant(Arbre * arbre);

Token token[N_OP] =
{
    {ADD, '+', 1},
    {SUB, '-', 1},
    {MUL, '*', 2},
    {DIV, '/', 2},
    {MOD, '%', 2},
    {POW, '^', 3},
    {NONE, '(', 4},
    {NONE, ')', 4}
};

const char * const Erreur[NB_ERR] =
{
    "",
    "Parenthese fermante manquante",
    "Division par zero",
    "Erreur de malloc"
};

void Afficher_Erreur(int num)
{
    printf("Erreur : %s\n", Erreur[num]);
}

/* Règle 1 == règle E -> EsE */

Arbre * Regle1(char * s, int op, int prio)
{
    char * tmp;
    Arbre * abr;

    abr = malloc(sizeof(*abr));
    if (abr == NULL)
        Afficher_Erreur(E_MALLOC);

    tmp = strchr(s, op);
    if (tmp == NULL)
    {
        return NULL;
    }

    abr->token.signe = *tmp;
    abr->token.priorite = prio;
    abr->type = OPERATEUR;

    *tmp = '\0';
    tmp++;

    abr->gauche = Analyse_Chaine(s);
    abr->droite = Analyse_Chaine(tmp);

    return abr;
}

/* Règle 2 == règle E -> E */

Arbre * Regle2(char ** s)
{
    Arbre * abr;
    double n;

    if (!isdigit(**s))
        return NULL;

    errno = 0;
    n = strtod(*s, s);

    if (errno == ERANGE)
    {
        fprintf(stderr, "Erreur.\n");
        return NULL;
    }

    abr = malloc(sizeof (*abr));
    if (abr == NULL)
        Afficher_Erreur(E_MALLOC);

    abr->gauche = NULL;
    abr->droite = NULL;
    abr->type = NOMBRE;
    abr->valeur = n;

    return abr;
}

/* Règle 3 == règle E -> (E) */

Arbre * Regle3(char ** s)
{
}

Arbre * Analyse_Chaine(char * s)
{
    Arbre * arbre = NULL;
    int i;

   /* arbre = Regle3(&s);*/

    if(arbre == NULL)
    {
        for (i = 0; i < N_OP; i++)
        {
            arbre = Regle1(s, token[i].signe, token[i].priorite);
            if (arbre != NULL)
                return arbre;
        }

        arbre = Regle2(&s);
    }

    return arbre;
}

double Calcul_Courant(Arbre * arbre)
{
    double resultat, n1, n2;

    if (arbre == NULL)
        return 0.0;

    switch(arbre->type)
    {
        case NOMBRE:
            resultat = arbre->valeur;
        break;

        case OPERATEUR:
            n1 = Calcul_Courant(arbre->gauche);
            n2 = Calcul_Courant(arbre->droite);

            switch(arbre->token.signe)
            {
                case '+':
                    arbre->token.operation = ADD;
                    resultat = n1 + n2;
                break;

                case '-':
                    arbre->token.operation = SUB;
                    resultat = n1 - n2;
                break;

                case '*':
                    arbre->token.operation = MUL;
                    resultat = n1 * n2;
                break;

                case '/':
                    if (n2 == 0.)
                    {
                        Afficher_Erreur(E_DIV);
                        break;
                    }

                    arbre->token.operation = DIV;
                    resultat = n1 / n2;
                break;

                case '%':
                    arbre->token.operation = MOD;
                    resultat = (int)n1 % (int)n2;
                break;

                case '^':
                    arbre->token.operation = POW;
                    resultat = pow(n1, n2);
                break;

                default:
                    arbre->token.operation = NONE;
                    resultat = 0.0;
                break;

            } break;

        default:
            arbre->token.operation = NONE;
            resultat = 0.0;
        break;
  }

    return resultat;
}

int main(void)
{
    char s[TAILLE];
    Arbre * arbre;
    double x;
    int continuer = 1;

    while (continuer)
    {
        printf(">> ");
        fgets(s, sizeof(s), stdin);

        arbre = Analyse_Chaine(s);
        x = Calcul_Courant(arbre);

        printf("%.3f\n", x);

        if (*s == 'q')
            continuer = 0;
    }

    return EXIT_SUCCESS;
}