C Symbol Tables

[DarkWater]

Well, I felt like trying to write a small language for set notations because a) I was bored, b) it could be useful if I need to deal with sets for math.  I know how to use Bison and Flex for basic things, so I got my syntax and rules taken care of just fine.  The problem is now implementing a fast symbol table for variables and a way to store the actual numbers from a given set in an array (I don't know the size beforehand and I feel like just specifying an exact number of elements would be too limiting).  Does anyone have any ideas?  I'd be really grateful for a push in the right direction and a little bit of a lesson on the theory behind symbol tables.

 

Btw, here's what the (tentative) syntax looks like:

{6, 8, 9}; //defines a set

@var; //variable

@var = {6, 8, 9}; //assignment

print @var; print {6, 8, 9}; //printing

@var = @var ^ {7}; //union

@var = @var & {8, 9} //intersection

@var = @var ! {2, 6}; //complement

@var = sum(sort(product(@var))); //function calls

 

I have much more to worry about after getting variables to store and sets to be in arrays, but I can work on that after I get this done.  Thanks.

[corbin]

"store the actual numbers from a given set in an array (I don't know the size beforehand and I feel like just specifying an exact number of elements would be too limiting)."

 

 

Why not use a vector or a hash table?

 

 

As for the rest, I have no idea.

[DarkWater]

"store the actual numbers from a given set in an array (I don't know the size beforehand and I feel like just specifying an exact number of elements would be too limiting)."

 

 

Why not use a vector or a hash table?

 

 

As for the rest, I have no idea.

 

Use a hash table for the variables or the sets?

 

EDIT: I was thinking maybe a linked list for the sets, but it'll get quite cumbersome to traverse.  Any better methods?

[corbin]

Depends....  How exactly do you want to store it?  You could have two vectors, one variables, and the other values.  Or you could have a hash table.  Pretty sure anything will get cumbersome to traverse x.x.

 

 

Maybe I misunderstood your goal earlier.  Are you making an equation solver, or a calculator type thing?  I thought eq solver at first, but now I think you meant calculator type thingy.

[DarkWater]

Just a general calculator type thing for sets.

[DarkWater]

Okay, I decided to work on a small linked list library for the sets.  Works pretty well so far.  Can someone please read through it for me and see if there's anything awry?  Also, I was wondering if there was a better way to do ll_pop() than checking two nodes ahead so I don't overshoot the 2nd to last node.  You'll see what I mean.

 

ll.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "ll.h"

noderef_t ll_init(int data) {
noderef_t head;
head = malloc(sizeof(node_t));
assert(head != NULL);
head->next = NULL;
head->data = data;
return head;
}

void ll_print(noderef_t list) {
printf("{\n");
while (list != NULL) {
	printf("\t%d\n", list->data);
	list = list->next;
}
printf("}\n");
}

int ll_length(noderef_t head) {
noderef_t current = head;
int count = 0;

while (current != NULL) {
	count++;
	current = current->next;
}
return count;
}

void ll_unshift(noderef_t* head, int data) {
noderef_t newList = malloc(sizeof(struct node));
assert(newList != NULL);
newList->data = data;
newList->next = *head;
*head = newList;
}

void ll_push(noderef_t* head, int data) {
noderef_t current = *head;
noderef_t newNode;

newNode = malloc(sizeof(struct node));
assert(newNode != NULL);
newNode->data = data;
newNode->next = NULL;

while (current->next != NULL) {
	current = current->next; //get to end of list
}

current->next = newNode;
}

int ll_pop(noderef_t* head) {
noderef_t current = *head;
int data;

while (current->next->next != NULL) {
	current = current->next;
}

data = current->next->data;
free(current->next);
current->next = NULL;
return data;
}

int ll_shift(noderef_t* head) {
noderef_t gone;
int data;

gone = *head;
assert(gone != NULL);

data = gone->data;
*head = gone->next;

free(gone);

return data;
}

void ll_close(noderef_t* head) {
noderef_t current = *head;
noderef_t next;

while (current != NULL) {
	next = current->next;
	free(current);
	current = next;
}

*head = NULL;
}

 

ll.h

#ifndef _LL_H_
#define _LL_H_
typedef struct node {
 int data;
	 struct node *next;
} node_t;

typedef node_t* noderef_t;

struct node* ll_init(int);
int ll_length(struct node*);
void ll_close(struct node**);
void ll_unshift(noderef_t*, int);
void ll_push(noderef_t*, int);
void ll_print(noderef_t);
int ll_shift(noderef_t*);
int ll_pop(noderef_t*);

#endif /* LL_H */

 

linkedlist.c

#include <stdio.h>
#include <stdlib.h>
#include "ll.h"

int
main(int argc, char** argv) {
noderef_t ll;
ll = ll_init(1);
ll_unshift(&ll, 5);
ll_push(&ll, 6);
ll_print(ll);

printf("\n%d  %d\n", ll_shift(&ll), ll_pop(&ll));

ll_print(ll);
ll_close(&ll);
exit(0);
}

 

Thanks a lot.

 

EDIT: Just so you guys know, after I finish get everything done with these basic functions, I'm adding combining, intersections, and unions.  And some other stuff, probably.

[DarkWater]

Anyone? D: