#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;
}