Question

In this assignment, we will explore some simple expressions and evaluate them. We will use an unconventional approach and severely limit the expressions. The focus will be on operator precedence.

The only operators we support are logical or (|), logical and (&), less than (<), equal to (=), greater than (>), add (+), subtract (-), multiply (*) and divide (/). Each has a precedence level from 1 to 5 where higher precedence operators are evaluated first, from left-to-right. For example, "1 + 2 * 3" is 1+6 = 7. It is NOT 3*3 = 9.

To evaluate an expression like "8 - 2*2 - 3" we first split it into two parts: "8 - 2*2" and "3". We recursively evaluate "8 - 2*2" = 4 and "3" = 3. We subtract to get 4-3 = 1. Note that we look for the operators from right to left so they get evaluated from left to right (as shown in this example).

When we recursively evaluate "8 - 2*2" we split it into "8" = 8 and "2*2" = 4 so it returns 8-4 = 4.

Don't worry about errors like divide-by-zero, overflow, etc. All operators and numbers are exactly one character long. No unary operators like negation (-) or not (!) and no parentheses are allowed.

You are not permitted to make substantive changes to the existing code. You should only modify the two TBD blocks.

Here is some sample output (you are not given the debug statements with ***):

Value of 4 is 4 as expected

Value of 9+8 is 17 as expected

*** Value of 4 * 5 is 20

Value of 3 + 4 * 5 is 23 as expected

*** Value of 9 - 2 is 7

Value of 9 - 2 - 1 is 6 as expected

*** Value of 3=4 is 0

*** Value of 5<6 is 1

*** Value of 7<8 is 1

*** Value of 5<6 & 7<8 is 1

Value of 3=4 | 5<6 & 7<8 is 1 as expected

*** Value of 3 * 6 is 18

Value of 2 + 3 * 6 is 20

Value of 8/4 is 2

Value of 3=4 is 0

Value of BOB + 5 is an Error

Hint #1: chars in C are the same as ints. '0' equals 48, etc.

Hint #2: sc is the starting char, 0 is first. ec is ending char plus 1. Given "1+3" sc=2 ec=3 is just "3".

// gcc -Wall eval.c -o /tmp/eval
// /tmp/eval "2 + 3 * 6" "8/4" "3=4" "BOB + 5"
// prints:    20          2     0     Error

#include <stdio.h>
#include <string.h>

// Not really very good to have a special number for errors
#define ERR 102413

static double orFn(double x, double y) {
  return (x != 0 || y != 0 ? 1 : 0);
}

static double andFn(double x, double y) {
  return (x != 0 && y != 0 ? 1 : 0);
}

static double ltFn(double x, double y) {
  return (x < y ? 1 : 0);
}

static double eqFn(double x, double y) {
  return (x == y ? 1 : 0);
}

static double gtFn(double x, double y) {
  return (x > y ? 1 : 0);
}

static double multFn(double x, double y) {
  return x * y;
}

static double divFn(double x, double y) {
  return x / y;
}

static double addFn(double x, double y) {
  return x + y;
}

static double subFn(double x, double y) {
  return x - y;
}

typedef struct OPER {
  char oper;
  int precedence;
  double (*func) (double x, double y);
} oper_t;

static oper_t operators[] = {
  {'|', 1, orFn},
  {'&', 2, andFn},
  {'<', 3, ltFn},
  {'=', 3, eqFn},
  {'>', 3, gtFn},
  {'+', 4, addFn},
  {'-', 4, subFn},
  {'*', 5, multFn},
  {'/', 5, divFn}
};
static int numOpers = sizeof(operators) / sizeof(oper_t);       // numOpers is 9

// Careful, this is recursive
static double eval(char *expr, int sc, int ec) {
  int level;
  int i;
  int op;
  
  // Trim spaces (don't worry about errors here)
  while(expr[sc] == ' ') sc++;
  while(expr[ec-1] == ' ') ec--;

  // If just one character, must be a number
  if (sc == ec - 1) {
    char ch = expr[sc];
    // TBD -- if ch is '0' to '9', convert it to a number and return it
    return ERR;
  }
  
  // Must be of the form: left oper right
  for (level = 1; level <= 5; level++) {
    for (op = 0; op < numOpers; op++) {
      // TBD -- if the operator[op] has the right precedence AND
      // TBD -- if we can find operator[op].oper in the substring RIGHT to LEFT
      // TBD -- then recursively call eval() with left then right of the operator[op].oper
      // TBD -- and then if left or right returned ERR, return ERR
      // TBD -- otherwise return operators[op].func(left, right)
    }
  }
  return ERR;
}

static void check(char *expr, double expected) {
  double result = eval(expr, 0, strlen(expr));
  if (result == expected) {
    printf("Value of %s is %g as expected\n\n", expr, result);
  } else {
    printf("Value of %s is %g instead of expected %g\n\n", expr, result, expected);
  }
}

int main(int argc, char *argv[]) {
  int i;
  
  // Recommend getting these to work one at a time
  check(" 4 ", 4);
  check("9+8", 17);
  check(" 3 + 4 * 5 ", 23);
  check(" 9 - 2 - 1", 6);
  check("3=4 | 5<6 & 7<8", 1);

  for (i = 1; i < argc; i++) {
    char *expr = argv[i];
    double result = eval(expr, 0, strlen(expr));
    if (result == ERR) {
      printf("Value of %s is an Error\n\n", expr);
    } else {
      printf("Value of %s is %g\n\n", expr, result);
    }
  }
}

Answer 1

• Updated C program:-

  #include <stdio.h>
  #include <string.h>

  // Not really very good to have a special number for errors
  #define ERR 102413

  static double orFn(double x, double y) {
  return (x != 0 || y != 0 ? 1 : 0);
  }

  static double andFn(double x, double y) {
  return (x != 0 && y != 0 ? 1 : 0);
  }

  static double ltFn(double x, double y) {
  return (x < y ? 1 : 0);
  }

  static double eqFn(double x, double y) {
  return (x == y ? 1 : 0);
  }

  static double gtFn(double x, double y) {
  return (x > y ? 1 : 0);
  }

  static double multFn(double x, double y) {
  return x * y;
  }

  static double divFn(double x, double y) {
  return x / y;
  }

  static double addFn(double x, double y) {
  return x + y;
  }

  static double subFn(double x, double y) {
  return x - y;
  }

  typedef struct OPER {
  char oper;
  int precedence;
  double (*func) (double x, double y);
  } oper_t;

  static oper_t operators[] = {
  {'|', 1, orFn},
  {'&', 2, andFn},
  {'<', 3, ltFn},
  {'=', 3, eqFn},
  {'>', 3, gtFn},
  {'+', 4, addFn},
  {'-', 4, subFn},
  {'*', 5, multFn},
  {'/', 5, divFn}
  };
  static int numOpers = sizeof(operators) / sizeof(oper_t); // numOpers is 9

  // Careful, this is recursive
  static double eval(char *expr, int sc, int ec) {
  int level;
  int i;
  int op;
  double left, right;
    
  // Trim spaces (don't worry about errors here)
  while(expr[sc] == ' ') sc++;
  while(expr[ec-1] == ' ') ec--;

  // If just one character, must be a number
  if (sc == ec - 1) {
  char ch = expr[sc];
  switch(ch)
  {
  case '0':
  case '1':
  case '2':
  case '3':
  case '4':
  case '5':
  case '6':
  case '7':
  case '8':
  case '9': return (double)ch-48;
  default: break;
  }
  return ERR;
  }
    
  // Must be of the form: left oper right
  for (level = 1; level <= 5; level++) {
  for (op = 0; op < numOpers; op++) {
  for(i=ec-1;i>=sc;i--){
  if (operators[op].oper == expr[i] && operators[op].precedence == level)
  {
  left = eval(expr, sc, i);
  right = eval(expr, i+1, ec);
  if (left == ERR || right == ERR)
  {
  return ERR;
  }
  else
  return operators[op].func(left, right);
  }
  }
  }
  }
  return ERR;
  }

  static void check(char *expr, double expected) {
  double result = eval(expr, 0, strlen(expr));
  if (result == expected) {
  printf("Value of %s is %g as expected\n\n", expr, result);
  } else {
  printf("Value of %s is %g instead of expected %g\n\n", expr, result, expected);
  }
  }

  int main(int argc, char *argv[]) {
  int i;
    
  // Recommend getting these to work one at a time
  check(" 4 ", 4);
  check("9+8", 17);
  check(" 3 + 4 * 5 ", 23);
  check(" 9 - 2 - 1", 6);
  check("3=4 | 5<6 & 7<8", 1);

  
  for (i = 1; i < argc; i++) {
  char *expr = argv[i];
  double result = eval(expr, 0, strlen(expr));
  if (result == ERR) {
  printf("Value of %s is an Error\n\n", expr);
  } else {
  printf("Value of %s is %g\n\n", expr, result);
  }
  }
  }

  Output:-