jweinst1
5/22/2018 - 8:27 AM

interview_question.c

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

/*Question*/
// Given a nested list expression, such as
// (e (b c) d) or (ao (bo (co))) in a string,
// Parse the expression and produce a linked-list object that can have an arbitrary depth.
// 
// the "items" in the list are just strings of any alphanumeric chracter.
// Consider the cases of an empty list and a syntax error, like an unmatched parenthesis.
// You can use any language you want.

/*Solution*/

typedef enum
{
  LispType_null, //represents empty
  LispType_list,
  LispType_value
} LispType;

// Represents lisp style list node
// head can be either value or another list, allowing arbitrary depth.
struct LispNode
{
  LispType type;
  void* head;
  struct LispNode* tail;
};

typedef struct LispNode LispNode;

// Constrcutor 
LispNode* LispNode_new(LispType t, void* head, LispNode* tail)
{
  LispNode* newNode = (LispNode*)malloc(sizeof(LispNode));
  newNode->type = t;
  newNode->head = head;
  newNode->tail = tail;
  return newNode;
}

// Moves code pointer past white space regions
void LispParse_white_space(const char** code)
{
  const char* mover = *code;
  while(isspace(*mover)) mover++;
  *code = mover;
}

// Gets length of alphanumeric sequence in C-string
size_t LispParse_item_len(const char* string)
{
  size_t total = 0;
  while(isalnum(*string++)) total++;
  return total;
}



char* LispParse_item(const char** code)
{
  const char* mover = *code;
  size_t len = LispParse_item_len(mover);
  // Allocates + 1 for null character
  char* parsed_item = (char*)malloc(len + 1);
  // String does not end with null so strncpy is used.
  strncpy(parsed_item, mover, len);
  parsed_item[len] = '\0'; // appends null character
  mover += len;
  *code = mover;
  return parsed_item;
}

// Parses lists to an arbitary depth
int LispParse_list(LispNode* lst, const char** code)
{
  if(**code != ')')
  {
     if(isspace(**code)) LispParse_white_space(code);
     if(isalnum(**code))
     {

        lst->type = LispType_value;
        lst->head = LispParse_item(code);
        lst->tail = LispNode_new(LispType_null, NULL, NULL);
        return LispParse_list(lst->tail, code);
     }
     else if(**code == '(')
    {
        *code += 1;
        lst->type = LispType_list;
        lst->head = LispNode_new(LispType_null, NULL, NULL);
        if(!LispParse_list((LispNode*)(lst->head), code))
        {
            // Raises failed parse up the call stack.
            return 0;
        }
        lst->tail = LispNode_new(LispType_null, NULL, NULL);
        return LispParse_list(lst->tail, code);
    }
    else
    {
        fprintf(stderr, "Syntax Error: Expected [a-zA-Z0-9] or (lst), got %c\n", **code);
         return 0;
    }
  }
  // moves to allow parsing to move back up one level.
  *code += 1;
  return 1;
}



// Top level parsing function
// if returned node type is null no parsing occurred.
LispNode* LispParse_code(const char* code)
{
  LispNode* node = LispNode_new(LispType_null, NULL, NULL);
  if(*code)
  {
      if(isspace(*code)) LispParse_white_space(&code);
      if(*code == '(')
      {
        code++;
        LispParse_list(node, &code);
      }
      else
      {
          fprintf(stderr, "Syntax Error: Expected '(', found '%c'\n", *code);
          return node;
      }
  }
  return node;
}

/////////////////////SOLUTION END//////////////

/*DEBUG METHOD*/

void LispNode_debug(LispNode* lst)
{
      printf("LispNode(");
      printf("head=");
      switch(lst->type)
      {
          case LispType_null:
              printf("null");
              break;
          case LispType_list:
              LispNode_debug((LispNode*)(lst->head));
              break;
          case LispType_value:
              printf("%s", (char*)(lst->head));
              break;
      }
      printf(",tail=");
      if(lst->tail == NULL) printf("null");
      else LispNode_debug(lst->tail);
      printf(")");
}

int main(void) {
  LispNode* foo = LispParse_code("(3 (6) 1)\n");
  LispNode_debug(foo);
  putc('\n', stdout);

/*
LispNode(head=3,tail=LispNode(head=LispNode(head=6,tail=LispNode(head=null,tail=null)),tail=LispNode(head=1,tail=LispNode(head=null,tail=null))))
*/
  return 0;
}