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

/**
 * rpn.c - a simple Reverse Polish Notation calculator.
 */

// +-----------+------------------------------------------------------
// | Constants |
// +-----------+

// The capacity of the stack
#define STACK_CAPACITY 16


// +---------+--------------------------------------------------------
// | Globals |
// +---------+

// The latest error message
char *last_error = "";

// The total number of errors
int errors = 0;


// +-----------------+------------------------------------------------
// | Other Functions |
// +-----------------+

/**
 * Do reverse-polish-notation calculations taking each input token from
 * vec.  Tokens are represented as strings.  Returns the value of the
 * computation, or INT_MIN if there's an error.  If there is an error,
 * also sets last_error to the error it noted.
 */
int 
rpn (int count, char *vec[])
{
  int stack[STACK_CAPACITY] = { 0 }; 
                         // The stack of numbers for RPN evaluation
  int top = 0;           // The top of the stack.  That is, the first
                         //   empty space on the stack.  Also the number
                         //   of items on the stack.
  int i;

  for (i = 0; i < count; i++)
    {
      if (strcmp (vec[i], "+") == 0)
        {
          top--;
          if (top <= 0)
            {
              last_error = "ERROR: Stack underflow.";
              return INT_MIN;
            }
          stack[top-1] = stack[top-1] + stack[top];
        } // "+"
      else if (strcmp (vec[i], "-") == 0)
        {
          top--;
          if (top <= 0)
            {
              last_error = "ERROR: Stack underflow.";
              return INT_MIN;
            }
          stack[top-1] = stack[top-1] - stack[top];
        } // "-"
      else if (strcmp (vec[i], "*") == 0)
        {
          top--;
          if (top <= 0)
            {
              last_error = "ERROR: Stack underflow.";
              return INT_MIN;
            }
          stack[top-1] = stack[top-1] * stack[top];
        } // "*" 
      else if (strcmp (vec[i], "/") == 0)
        {
          top--;
          if (top <= 0)
            {
              last_error = "ERROR: Stack underflow.";
              return INT_MIN;
            }
          stack[top-1] = stack[top-1] / stack[top];
        } // "/"
      else if (strcmp (vec[i], "negate") == 0)
        {
          if (top <= 0)
            {
              last_error = "ERROR: Stack underflow.";
              return INT_MIN;
            }
          stack[top-1] = -stack[top-1];
        }
      else
        {
          if (top >= STACK_CAPACITY)
            {
              last_error = "ERROR!  Stack overflow";
              return INT_MIN;
            }
          stack[top] = atoi (vec[i]);
          top++;
        }
    }

  if (top != 1)
    {
      last_error = "ERROR! Finished with more than one value.";
      return INT_MIN;
    }

  return stack[0];
} // rpn

/**
 * Print the contents of a string vector.
 */
void
dump (int count, char *vec[])
{
  int i;
  if (count == 0)
    return;
  printf ("[%s", vec[0]);
  for (i = 1; i < count; i++)
    printf (" %s", vec[i]);
  printf ("]");
} // dump

/**
 * Do one test.
 */
int
check (int count, char *vec[], int expected)
{
  int result = rpn (count, vec);
  if (result != expected)
    {
      printf ("For ");
      dump (count, vec);
      printf (" expected %d, got %d.\n", expected, result);
      ++errors;
      if (result == INT_MIN)
        printf ("  %s\n", latest_error);
    }
} // check

int
main ()
{
   char *exp0[] = { "5" };              // Just a number
   char *exp1[] = { "5", "3", "+" };    // Simple operation
   char *exp2[] = { "5", "negate" };    // Negation
   char *exp3[] = { "4", "5" };         // Don't clear the stack
   char *exp4[] = { "3", "+" };         // Missing operand
   char *exp5[] = { "5", "3", "2", "1", "+", "*", "-" };
                                        // Variety of operations
   check (1, exp0, 5);
   check (3, exp1, 8);
   check (2, exp2, -5);
   check (2, exp3, 1);
   check (2, exp4, 1);
   check (7, exp5, -4);

   return EXIT_SUCCESS;
} // main