// Taschenrechner mit Operator Grammar Parser
// (= tabellengesteuerter Shift / Reduce - Parser)
//
// Aufruf: ogp
// (der Input wird vom Terminal gelesen)
// 
// Klaus Kusche, 2013

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

// Arten von Token
typedef enum {
  t_begin,      // Zeilenanfang
  t_end,        // Zeilenende
  t_assign,     // =
  t_plus,       // +
  t_minus,      // -
  t_mul,        // *
  t_div,        // /
  t_pow,        // ^
  t_neg,        // unäres -
  t_lpar,       // (
  t_rpar,       // )
  t_last,       // ! für letztes Ergebnis
  t_var,        // Variable (1 Kleinbuchstabe)
  t_const,      // Konstante (E für e, P für pi)
  t_value       // Kommazahl
} type_t;

// Typ eines Input-Tokens = Typ eines Elementes des Parse Stacks
typedef struct token token;
struct token {
  type_t type;     // Art des Tokens
  short unsigned int line, col;   // Position des Tokens im Source
  double value;    // Wert: 
                   // t_value, t_const: Der eigene Wert
                   // t_var: Index der Variable (0...25)
                   // Sonst: Undefiniert.
  token *left;     // In der Input-Liste: Null
                   // Am Parse-Stack: Vorgänger am Stack
                   // Im Parse Tree: Linker Sohn
  token *right;    // In der Input-Liste: Nächstes Token am Input
                   // Am Parse-Stack: Teilbaum schon verarbeiteter nachfolgender Token
                   // Im Parse Tree: Rechter Sohn
};

///////////////////////////////////////////////////////////////////////////////
// Lexikalischer Teil
///////////////////////////////////////////////////////////////////////////////

// Lege ein neues Token an
token *newToken(type_t type, int line, int col, double value);

// Liefert pro Aufruf die Token einer Input-Zeile als einfach verkettete Liste
// (mit einem t_begin-Token am Anfang und einem t_end-Token am Ende)
token *lexLine(void);

// Hilfstabelle: Nach welchen Token folgt ein binäres Rechenzeichen?
// (dasselbe Input-Zeichen - wird je nach Vorgänger
// entweder in das Token t_minus oder das Token t_neg verwandelt)
bool binOpFollows[] = {
  false,     // Zeilenanfang
  false,     // Zeilenende
  false,     // =
  false,     // +
  false,     // -
  false,     // *
  false,     // /
  false,     // ^
  false,     // unäres -
  false,     // (
  true,      // )
  true,      // ! für letztes Ergebnis
  true,      // Variable
  true,      // Konstante (E für e, P für pi)
  true       // Kommazahl
};

// Lege ein neues Token an
token *newToken(type_t type, int line, int col, double value)
{
  token *p;

  p = (token *) (malloc(sizeof(token)));

  if (p == NULL) {
    fprintf(stderr, "Out of memory!\n");
    exit(EXIT_FAILURE);
  }

  p->type = type;
  p->line = line;
  p->col = col;
  p->value = value;
  p->left = p->right = NULL;

  return p;
}

// Liefert pro Aufruf die Token einer Input-Zeile als einfach verkettete Liste
// (mit einem t_begin-Token am Anfang und einem t_end-Token am Ende)
token *lexLine(void)
{
  token *head, *tail; // ... der Token-Liste
  type_t type;        // ... des aktuellen Tokens
  double val;         // ... des aktuellen Tokens
  static int line;    // aktuelle Zeilennummer
  int col;            // aktuelle Spaltennummer
  int c;              // aktuelles Zeichen, wegen EOF int statt char

  head = tail = newToken(t_begin, line, 0, 0);
  ++line;

  for (col = 1; ; ++col) {
    c = getchar();
    switch (c) {
      case EOF:
      case '\n':
        goto done;
        break;
      case ' ':
      case '\t':
        continue;   // kein Token, mit nächstem Zeichen weitermachen
        break;
      case '1': case '2': case '3': case '4': case '5': 
      case '6': case '7': case '8': case '9': case '0':
        val = 0;
        do {
          val = val * 10 + (c - '0');
          c = getchar(); ++col;
        } while (isdigit(c));
        
        if (c == '.') {
          double frac = 0.1;
          c = getchar(); ++col;
          while (isdigit(c)) {
            val += frac * (c - '0');
            frac /= 10;
            c = getchar(); ++col;
          }
        }

        if ((c == 'e') || (c == 'E')) {
          int expon = 0;
          int esgn = 1;
          c = getchar(); ++col;
          if (c == '+') {
            c = getchar(); ++col;
          } else if (c == '-') {
            esgn = -1;
            c = getchar(); ++col;
          }
          if (!isdigit(c)) {
            printf("Line %d, col %d: Digit expected\n", line, col);
          } else {
            do {
              expon = expon * 10 + (c - '0');
              c = getchar(); ++col;
            } while (isdigit(c));
          }
          val *= pow(10.0, ((double) (esgn * expon)));
        }

        // 1 zuviel gelesenes Zeichen nach der Kommazahl rückgängig machen
        ungetc(c, stdin); --col;

        type = t_value;
        break;
      case 'a': case 'b': case 'c': case 'd': case 'e': 
      case 'f': case 'g': case 'h': case 'i': case 'j': 
      case 'k': case 'l': case 'm': case 'n': case 'o': 
      case 'p': case 'q': case 'r': case 's': case 't': 
      case 'u': case 'v': case 'w': case 'x': case 'y': 
      case 'z':
        type = t_var;
        val = (double)(c - 'a');
        break;
      case 'E':
        type = t_const;
        val = M_E;
        break;
      case 'P':
        type = t_const;
        val = M_PI;
        break;
      case '!':
        type = t_last;
        val = 0;
        break;
      case '(':
        type = t_lpar;
        val = 0;
        break;
      case ')':
        type = t_rpar;
        val = 0;
        break;
      case '+':
        type = t_plus;
        val = 0;
        break;
      case '-':
        type = binOpFollows[tail->type] ? t_minus : t_neg;
        val = 0;
        break;
      case '*':
        type = t_mul;
        val = 0;
        break;
      case '/':
        type = t_div;
        val = 0;
        break;
      case '^':
        type = t_pow;
        val = 0;
        break;
      case '=':
        type = t_assign;
        val = 0;
        break;
      default:
        printf("Line %d, col %d: Illegal character %c\n", line, col, c);
        continue;  // kein Token, mit nächstem Zeichen weitermachen
        break;
    }
    tail = tail->right = newToken(type, line, col, val);
  }  

done:
  tail->right = newToken(t_end, line, col, 0);
  return head;
}

///////////////////////////////////////////////////////////////////////////////
// Syntaxverarbeitung
///////////////////////////////////////////////////////////////////////////////

// Gib einen Syntaxfehler an der aktuellen Position aus
void error(token *pos, const char *msg);

// Prüfe, ob an dem Token t kein Unterbaum hängt
// Wenn doch: Fehler msg an Position pos
void checkNull(token *t, token *pos, const char *msg);

// Prüfe, ob an dem Token t ein Unterbaum hängt
// Wenn nicht: Fehler msg an Position pos
void checkVal(token *t, token *pos, const char *msg);

// Parse eine Zeile Tokens: Shift/Reduce-Schleife
// Ergebnis: Parse Tree
token *parseLine(token *input);

// Die Shift/Reduce-Steuertabelle
typedef struct ogpEntry ogpEntry;
struct ogpEntry {
  int left, right;        // Linke und rechte Priorität
};

ogpEntry ogpTab[] = {
  { 0, 0},        // Zeilenanfang
  { 0, 0},        // Zeilenende
  { 201, 200},    // =
  { 300, 301},    // +
  { 300, 301},    // -
  { 400, 401},    // *
  { 400, 401},    // /
  { 501, 500},    // ^
  { 900, 600},    // unäres -
  { 900, 100},    // (
  { 100, 901},    // )
  { 900, 901},    // ! für letztes Ergebnis
  { 900, 901},    // Variable
  { 900, 901},    // Konstante (E für e, P für pi)
  { 900, 901}     // Kommazahl                      
};

// Gib einen Syntaxfehler an der aktuellen Position aus
void error(token *pos, const char *msg)
{
  printf("Line %d, col %d: %s\n", pos->line, pos->col, msg);
}

// Prüfe, ob an dem Token t kein Unterbaum hängt
// Wenn doch: Fehler msg an Position pos
void checkNull(token *t, token *pos, const char *msg)
{
  if (t->right != NULL) {
    error(pos, msg);
  }
}

// Prüfe, ob an dem Token t ein Unterbaum hängt
// Wenn nicht: Fehler msg an Position pos
void checkVal(token *t, token *pos, const char *msg)
{
  if (t->right == NULL) {
    error(pos, msg);
  }
}

// Parse eine Zeile Tokens: Shift/Reduce-Schleife
// Ergebnis: Parse Tree
token *parseLine(token *input)
{
  // input zeigt auf das nächste zu lesende Token der Input-Liste
  // stack zeigt auf das oberste (unreduzierte!) Token am Parse-Stack
  token *stack, *t;
  
  // leg das erste Token (t_begin) als einziges Token auf den Stack
  stack = input;
  input = input->right;
  stack->right = NULL;

  // Schiebe oder reduziere,
  // bis der Input nur mehr das Ende-Token enthält und
  // das oberste bzw. einzige unreduzierte Tokem am Stack das Begin-Token ist
  while (!((stack->type == t_begin) && (input->type == t_end))) {
    // Befrage die Tabelle, ob ein Shift oder ein Reduce folgt:
    // Vergleiche den Rechts-Wert des obersten unreduzierten Token am Stack
    // mit dem Links-Wert des nächsten Token im Input
    if (ogpTab[stack->type].right > ogpTab[input->type].left) {
      // Reduce: Verwandle das oberste Stack-Token in einen Teilbaum
      // Top of Stack ändert sich!
      t = stack;
      stack = stack->left;
      switch (t->type) {
        case t_assign:
        case t_plus:
        case t_minus:
        case t_mul:
        case t_div:
        case t_pow:
          // Binären Operator reduzieren
          // Am Operator muss etwas hängen (der rechte Operand)
          // Am Vorgänger muss etwas hängen (der linke Operand)
          // Der linke Operand wird umgehängt: Er wird linker Sohn des Operators
          // Der Operator samt beiden Operanden wird an den Vorgänger angehängt
          checkVal(t, t, "Operand missing after operator");
          checkVal(stack, t, "Operand missing before operator");
          t->left = stack->right;
          stack->right = t;
          break;
        case t_neg:
          // Unären Operator reduzieren
          // Am Operator muss etwas hängen (der Operand)
          // Am Vorgänger darf nichts hängen
          // Der Operator samt Operand wird an den Vorgänger angehängt
          checkVal(t, t, "Operand missing after unary operator");
          checkNull(stack, t, "Illegal operand before unary operator");
          t->left = NULL;
          stack->right = t;
          break;
        case t_lpar:
          // Linke Klammer reduzieren
          // Das passiert nur, wenn die entsprechende rechte Klammer fehlt!
          error(t, "No matching )");
          // Hänge trotzdem den Klammerninhalt an den Vorgänger
          checkNull(stack, t, "Operator missing before (");
          stack->right = t->right;
          free(t);
          break;
        case t_rpar:
          // Rechte Klammer reduzieren
          // An der rechten Klammer darf nichts hängen
          // Der Vorgänger muss die entsprechende linke Klammer sein
          // An ihr hängt rechts der Inhalt der Klammern
          assert(t->right == NULL);  // darf wegen OGP-Prioritäten nie passieren
          if (stack->type != t_lpar) {
            error(t, "No matching (");
            free(t);
            break;
          }
          checkVal(stack, t, "Value missing in ()");

          // Der Inhalt der Klammern wird an den Vorvorgänger gehängt
          // Dort darf noch nichts hängen
          // Die beiden Klammern werden freigegeben,
          // der Parse Tree enthält keine Klammern mehr.
          free(t);
          t = stack;
          stack = stack->left;
          checkNull(stack, t, "Operator missing before (");
          stack->right = t->right;
          free(t);
          break;
        case t_last:
        case t_var:
        case t_const:
        case t_value:
          // Einfachen Wert reduzieren
          // Am Vorgänger und am Wert selbst darf nichts hängen
          // Der Wert wird an den Vorgänger angehängt
          checkNull(stack, t, "Operator missing before value");
          assert(t->right == NULL);  // darf wegen OGP-Prioritäten nie passieren
          t->left = NULL;
          stack->right = t;
          break;
        case t_begin:
        case t_end:
          // Begin und End dürfen nie reduziert werden!
        default:
          assert(false);
          break;
      }
    } else {
      // Shift: Lege das Input-Token oben auf den Stack
      input->left = stack;
      stack = input;
      input = input->right;
      stack->right = NULL;
    }
  }

  // Alle Token sind fertig verarbeitet:
  // Am Stack liegt nur mehr das Anfang-Token
  // Am Input steht nur mehr das Ende-Token
  // Rechts am Anfang-Token hängt der komplette fertige Parse Tree
  t = stack->right;
  free(stack); free(input);
  return t;
}

///////////////////////////////////////////////////////////////////////////////
// Auswertung (bei echtem Compiler: Code-Generierung)
///////////////////////////////////////////////////////////////////////////////

// Variable auf linker Seite von = auswerten:
// Liefert Variablen-Index oder -1 bei Fehler
int getVarNum(token *root);

// Baum rekursiv durchwandern und ausrechnen (und auch gleich freigeben)
double evalTree(token *root);

// Speicher für die Variablen a-z
double vars[26];

// Speicher für das Ergebnis der letzten Zeile
double lastVal;

// Variable auf linker Seite von = auswerten:
// Liefert Variablen-Index oder -1 bei Fehler
int getVarNum(token *root)
{
  int var;

  // bei Fehlern im Baum hat der Parser schon die Meldung ausgegeben
  if (root == NULL) return -1;

  if (root->type == t_var) {
    var = (int)(root->value);
  } else {
    var = -1;   // Fehlermeldung macht der Aufrufer
  }

  free(root);
  return var;
}

// Baum rekursiv durchwandern und ausrechnen (und auch gleich freigeben)
double evalTree(token *root)
{
  double result;
  double tmp;
  int var;
  
  // bei Fehlern im Baum hat der Parser schon die Meldung ausgegeben
  if (root == NULL) return 0;
  
  switch (root->type) {
    case t_assign:
      var = getVarNum(root->left);
      result = evalTree(root->right);
      if (var == -1) {
        error(root, "Left side of = is no variable");
      } else {        
        vars[var] = result;
      }
      break;
    case t_plus:
      result = evalTree(root->left) + evalTree(root->right);
      break;
    case t_minus:
      result = evalTree(root->left) - evalTree(root->right);
      break;
    case t_mul:
      result = evalTree(root->left) * evalTree(root->right);
      break;
    case t_div:
      tmp = evalTree(root->right);
      if (tmp == 0) {
        error(root, "Division by 0");
        result = HUGE_VAL;
      } else {
        result = evalTree(root->left) / tmp;
      }      
      break;
    case t_pow:
      result = pow(evalTree(root->left), evalTree(root->right));
      break;
    case t_neg:
      result = -evalTree(root->right);
      break;
    case t_last:
      result = lastVal;
      break;
    case t_var:
      result = vars[((int)(root->value))];
      break;
    case t_const:
    case t_value:
      result = root->value;
      break;
    case t_lpar:   // Klammern werden vom Parser entfernt
    case t_rpar:
    case t_begin:  // Begin und End kommen im Baum auch nie vor
    case t_end:
    default:
      assert(false);
      break;
  }

  free(root);
  return result;
}

///////////////////////////////////////////////////////////////////////////////
// Hauptprogramm
///////////////////////////////////////////////////////////////////////////////

int main(void)
{
  token *list, *tree;
  
  for (;;) {
    // Input zeilenweise verarbeiten
    list = lexLine();
    tree = parseLine(list);
    if (tree == NULL) break;
    lastVal = evalTree(tree);
    printf("%.12g\n", lastVal);
  }
  
  exit(EXIT_SUCCESS);
}