#!/bin/sh
# This is a shar archive.
# The rest of this file is a shell script which will extract:
#
# 5_10a.h 5_10a1.c 5_10a2.c 5_10a3.c 5_11A.h 5_11B.h 5_11C.h 5_11D.h 5_11a.c 5_11b.c 5_11c.c 5_11d.c 5_11e.c 5_11f.c 5_11g.c 5_11h.c 5_11i.c error.h makefile table.h tst.c tst.cmp
#
# To extract the files from this shell archive file simply
# create a directory for this file, move the archive file
# to it and enter the command
#
#	sh filename
# 
# The files will be extracted automatically.
# Note: Do not use csh.
#
# Archive created: Mon Jul 30 23:02:40 EDT 1990
#
echo x - 5_10a.h
sed 's/^X//' > 5_10a.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// exercise 5.10
// class table
#ifndef TABLE_H
#define TABLE_H

#include <string.h>

/* declare the class which contains the names, */
/* values and pointers for a list of these names */
struct name
{
    char *string;
    name *next;

    union
	{
	double dvalue;
	float fvalue;
	void *pvalue;
	void (*pfvalue)();
	long lvalue;
	short svalue;
	unsigned long ulvalue;
	unsigned short usvalue;
	};

    name(char *str)
    {
	string = new char[strlen(str) + 1];
	strcpy(string, str);
	dvalue = 0;
    }

    ~name()
    {
	delete string;
    }
};

class table
{
    name **tbl;
    int size;

public:
    table(int sz = 23);
    ~table();

    name *look(char*, int = 0);
    name *insert(char *s) { return look(s, 1); }
    name *lookfor(char *s) { return look(s, 2); }
};
#endif /* TABLE_H */
!EOF!
ls -l 5_10a.h
echo x - 5_10a1.c
sed 's/^X//' > 5_10a1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// look up a name within a symbol table
#include <table.h>
#include <string.h>
#include <error.h>

name *table::look(char *p, int ins)
{
    // hash the name
    int ii = 0;
    char *pp = p;
    while (*pp)
        ii = (ii << 1) ^ *pp++;
    if (ii < 0)
        ii = -ii;
    ii %= size;

    // run down that list, looking for the name
    for (name *n = tbl[ii]; n; n = n->next)
        if (strcmp(p, n->string) == 0)
	    return n;

    // the name was not found
    switch (ins)
        {
	case 0:
            error("name not found");
	    return 0;

        case 2:
	    return 0;

        case 1:
	    name *nn = new name(p);
	    nn->next = tbl[ii];
	    tbl[ii] = nn;
	    return nn;

        default:
	    error("unknown ins value for table::look()");
	    return 0;
	}
}
!EOF!
ls -l 5_10a1.c
echo x - 5_10a2.c
sed 's/^X//' > 5_10a2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// construct a symbol table
#include <table.h>
#include <error.h>

table::table(int sz)
{
    if (sz <= 0)
        error("non-positive table size");

    tbl = new name*[size = sz];
    for (int i = 0; i < sz; i++)
        tbl[i] = 0;
}
!EOF!
ls -l 5_10a2.c
echo x - 5_10a3.c
sed 's/^X//' > 5_10a3.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// cleanup a symbol table
#include <table.h>

table::~table()
{
    for (int i = 0; i < size; i++)
        for (name *n = tbl[i]; n; n = n->next)
	    delete n;
	    
    delete tbl;
}
!EOF!
ls -l 5_10a3.c
echo x - 5_11A.h
sed 's/^X//' > 5_11A.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// expression evaluator
enum exprtype
{
    NUMBER, END,
    PLUS = '+', MINUS = '-',
    MUL = '*', DIV = '/',
    LP = '(', RP = ')',
    ASSIGN = '=', NAME,
    SEMICOLON = ';'
};
!EOF!
ls -l 5_11A.h
echo x - 5_11B.h
sed 's/^X//' > 5_11B.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
struct tree
{
    tree *left, *right, *next;
    exprtype type;
    union
    {
	int value;
	char *cvalue;
    };

    tree() { left = right = next = 0; }
    ~tree() { delete left; delete right; delete next; }
};
!EOF!
ls -l 5_11B.h
echo x - 5_11C.h
sed 's/^X//' > 5_11C.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
struct token
{
    exprtype type;
    union
    {
        int value;
	char *cvalue;
    };
};
!EOF!
ls -l 5_11C.h
echo x - 5_11D.h
sed 's/^X//' > 5_11D.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
class expr
{
    tree *head;
    int evaluated, value;
    table variables;

public:
    expr(char*);
    int eval();
    void print();
};
!EOF!
ls -l 5_11D.h
echo x - 5_11a.c
sed 's/^X//' > 5_11a.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// included within get_token()		DELETE
default:
    if (isalpha(ch))
	{
	// read in the name
	char namestring[100];
	char *p = namestring;
	for (*p++ = ch;
	     input.get(ch) &&
	     (isalnum(ch) || (ch == '_'));
	     *p++ = ch)
	    ;
	input.putback(ch);
	*p = 0;

	// save the name
	curr_tok.cvalue = new char[p - namestring + 1];
	strcpy(curr_tok.cvalue, namestring);
	curr_tok.type = NAME;

	// insert the name into the variable name table
	name *n = variables->insert(curr_tok.cvalue);
	n->lvalue = 0;
	return;
	}
!EOF!
ls -l 5_11a.c
echo x - 5_11b.c
sed 's/^X//' > 5_11b.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// included within prim()		DELETE
case NAME:
    get_token(input, variables);	// skip name
    ret->cvalue = curr_tok.cvalue;

    if (curr_tok.type == ASSIGN)
	{
	get_token(input, variables);	// skip '='
	ret->type = ASSIGN;
	ret->left = get_expr(input, variables);
	}

    else
	ret->type = NAME;
    return ret;

case SEMICOLON:
    ret->type = SEMICOLON;
    get_token(input, variables);	// skip ';'
    return ret;
!EOF!
ls -l 5_11b.c
echo x - 5_11c.c
sed 's/^X//' > 5_11c.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// included within expandtree()		DELETE
else
    {
    tree *ret = get_expr(input, variables);
    for (tree *nhead = ret;
	 curr_tok.type == SEMICOLON;
	 nhead = nhead->next)
	 {
	 get_token(input, variables);
	 nhead->next = get_expr(input, variables);
	 }
    return ret;
    }
!EOF!
ls -l 5_11c.c
echo x - 5_11d.c
sed 's/^X//' > 5_11d.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// Evaluate the expression
int expr::eval()
{
    if (!evaluated)
	{
	for (tree *nhead = head;
	     nhead;
	     nhead = nhead->next)
	    value = treeval(nhead, &variables);
	evaluated++;
	}

    return value;
}
!EOF!
ls -l 5_11d.c
echo x - 5_11e.c
sed 's/^X//' > 5_11e.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// included within treeval()		DELETE
case ASSIGN:
    int val = treeval(head->left, variables);
    variables->look(head->cvalue)->lvalue = val;
    return val;

case NAME:
    return variables->look(head->cvalue)->lvalue;

case SEMICOLON:
    return 0;
!EOF!
ls -l 5_11e.c
echo x - 5_11f.c
sed 's/^X//' > 5_11f.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// Print the expression list
void expr::print()
{
    for (tree *nhead = head; ; )
	{
	infixprint(nhead);
	nhead = nhead->next;
	if (!nhead)
	    break;
	cout << "; ";
	}
}
!EOF!
ls -l 5_11f.c
echo x - 5_11g.c
sed 's/^X//' > 5_11g.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// included within get_token()		DELETE
case '*': case '+': case '(':
case '/': case '-': case ')':
case '=': case ';':		// new
!EOF!
ls -l 5_11g.c
echo x - 5_11h.c
sed 's/^X//' > 5_11h.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
static void get_token(istream&, table*);
static tree* get_expr(istream&, table*);
static tree* term(istream&, table*);
static tree* prim(istream&, table*);
!EOF!
ls -l 5_11h.c
echo x - 5_11i.c
sed 's/^X//' > 5_11i.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// included within infixprint()		DELETE
case ASSIGN:
    cout << head->cvalue << " = ";
    infixprint (head->left);
    break;

case NAME:
    cout << head->cvalue;
    break;
!EOF!
ls -l 5_11i.c
echo x - error.h
sed 's/^X//' > error.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#ifndef ERRORH
# define ERRORH

int error(const char *fmt ...);

#endif /* ERRORH */
!EOF!
ls -l error.h
echo x - makefile
sed 's/^X//' > makefile << '!EOF!'
CC= CC -I. -I../../CC
ERROR=  ../../error.o
CFLAGS= -I. -g +i

all: tst

tst: tst.c 5_11A.h 5_11B.h 5_11C.h 5_11D.h 5_11a.c 5_11b.c 5_11c.c 5_11d.c 5_11e.c 5_11f.c 5_11g.c 5_11h.c 5_11i.c
	$(CC) $(CFLAGS) tst.c -o tst $(ERROR)

CMP= tst.cmp
OUT= tst.out

tst.out: tst ;	./tst > tst.out

test: all $(OUT) $(CMP)
	cmp tst.out tst.cmp
	echo tests done
!EOF!
ls -l makefile
echo x - table.h
sed 's/^X//' > table.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include "5_10a.h"
!EOF!
ls -l table.h
echo x - tst.c
sed 's/^X//' > tst.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <stream.h>
#include <string.h>
#include <ctype.h>

#include <error.h>

#include "5_10a.h"	// class table
#include "5_10a1.c"	// table::lock
#include "5_10a2.c"	// table::table()
#include "5_10a3.c"	// table::~table()

#include "5_11A.h"	// enum exprtype
#include "5_11B.h"	// struct tree
#include "5_11C.h"	// struct token
#include "5_11D.h"	// class expr

static token curr_tok;

#include "5_11h.c"	// forward declarations

static tree* term(istream& input, table *variables)
{
    tree* left = prim(input, variables);

    for (;;)
	switch (curr_tok.type)
	    {
	    case MUL:
	    case DIV:
		tree* head = new tree;
		head->type = curr_tok.type;
		head->left = left;
		get_token(input, variables);	// eat '*','/'
		head->right = prim(input, variables);
		left = head;
		break;

	    default:		// collapse node
		return left;
	    }
}


tree *expandtree(istream &input, table *variables)
{
    if (curr_tok.type == END)
	{
	tree *ret = new tree;
	ret->type = NUMBER;
	ret->value = 0;
	return ret;
	}

#include "5_11c.c"	// else get series of expressions
}

static tree* prim(istream& input, table *variables)
{
    tree* ret = new tree;

    switch (curr_tok.type)
	{
	case NUMBER:
	    ret->type = NUMBER;
	    ret->value = curr_tok.value;
	    get_token(input, variables);		// skip number
	    return ret;

	case MINUS:
	    ret->type = MINUS;
	    get_token(input, variables);		// skip '-'
	    ret->left = prim(input, variables);
	    ret->right = 0;
	    return ret;

	case LP:
	    ret->type = LP;
	    get_token(input, variables);		// skip '('
	    ret->left = get_expr(input, variables);
	    if (curr_tok.type != RP)
	        {
		error(") expected");
		break;
		}
	    get_token(input, variables);		// skip ')'
	    return ret;

	case END:
	    error("end of expression unexpected");
	    break;

#include "5_11b.c"	// case NAME

	default:
	    error("prim: unknown type within tree, %c", curr_tok.type);
	    break;
	}

    // error case
    ret->value = 0;
    ret->type = NUMBER;
    return ret;
}


expr:: expr(char* s)
{
    istream input(strlen(s), s);
    evaluated = 0;
    get_token(input, &variables);
    head = expandtree(input, &variables);
}

static tree* get_expr(istream& input, table *variables)
{
    tree* left = term(input, variables);

    for (;;)
	switch (curr_tok.type)
	    {
	    case PLUS:
	    case MINUS:
		tree* head = new tree;
		head->type = curr_tok.type;
		head->left = left;
		get_token(input, variables);	// eat '+','-'
		head->right = term(input, variables);
		left = head;
		break;

	    default:		// collapse node
		return left;
	    }
}

// Evaluate the given expression tree
int treeval(tree* head, table *variables)
{
    if (head)
	switch (head->type)
	    {
	    case PLUS:
		return treeval(head->left, variables) +
		       treeval(head->right, variables);

	    case MINUS:
		if (head->right)
		    return treeval(head->left, variables) -
			   treeval(head->right, variables);
		else
		    return -treeval(head->left, variables);

	    case DIV:
	        int l = treeval(head->left, variables);
	        int r = treeval(head->right, variables);
		if (r != 0)
		    return l / r;
		else
		    return error("division by 0");

	    case MUL:
		return treeval(head->left, variables) *
		       treeval(head->right, variables);

	    case NUMBER:
		return head->value;

	    case LP:
		return treeval(head->left, variables);

#include "5_11e.c"	// case ASSIGN, NAME

	    case RP:
	    case END:
		error ("invalid type within treeval, '%c'", head->type);
		break;
	    }

    else
	error("NULL node found");
    return 0;
}

// print out the tree in infix format
static void infixprint(tree* head)
{
    cout << "( ";
    if (head)
	switch (head->type)
	    {
	    case PLUS:
	    case DIV:
	    case MUL:
		infixprint (head->left);
		cout << chr (head->type) << " ";
		infixprint (head->right);
		break;

	    case MINUS:
		if (head->right)
		    {
		    infixprint (head->left);
		    cout << "- ";
		    infixprint (head->right);
		    }

		else
		    {
		    cout << "- ";
		    infixprint (head->left);
		    }
		break;

	    case NUMBER:
		cout << head->value;
		break;

	    case LP:
		infixprint (head->left);
		break;

#include "5_11i.c"

	    case RP:
	    case SEMICOLON:
	    case END:
		error ("invalid type within infixprint, '%c'", head->type);
		break;
	    }

    else
	error ("NULL node found");

    cout << " ) ";
}

#include "5_11d.c"	// expr::eval()

static void get_token(istream &input, table *variables)
{
    char ch;
    do  {	// skip whitespace
	if (!input.get(ch))
	    { curr_tok.type = END; return; }
    } while (isspace(ch));

    switch (ch)
	{
#include "5_11g.c"
	    curr_tok.type = ch;
	    return;

	case '0': case '1': case '2': case '3':
	case '4': case '5': case '6': case '7':
	case '8': case '9':
	    input.putback(ch);
	    input >> curr_tok.value;
	    curr_tok.type = NUMBER;
	    return;

#include "5_11a.c"	// isalpha()
	    error("bad token, ch='%c'", ch);
	    curr_tok.type = END;
	    return;
	}
}

#include "5_11f.c"	// expr::print()

char *strs[] =
{
    "",
    "1 ",
    "2*3 ",
    "2-3 ",
    "5/2",
    "123/4+123*4-3",
    "a=5/2; 57+a-3 ",
    0
};

void lookat(char *s)
{
    cout << "x = '" << s << "'\n";
    expr x(s);
    cout << "x = "; x.print(); cout << "\n";
    cout << "x = " << x.eval() << "\n";
    cout << "\n";
}

main(int argc, char **argv)
{
    if (argc > 1)
	while (*++argv)
	    lookat(*argv);

    else
	for (int i = 0; strs[i]; i++)
	    lookat(strs[i]);

    return 0;
}
!EOF!
ls -l tst.c
echo x - tst.cmp
sed 's/^X//' > tst.cmp << '!EOF!'
x = ''
x = ( 0 ) 
x = 0

x = '1 '
x = ( 1 ) 
x = 1

x = '2*3 '
x = ( ( 2 ) * ( 3 )  ) 
x = 6

x = '2-3 '
x = ( ( 2 ) - ( 3 )  ) 
x = -1

x = '5/2'
x = ( ( 5 ) / ( 2 )  ) 
x = 2

x = '123/4+123*4-3'
x = ( ( ( ( 123 ) / ( 4 )  ) + ( ( 123 ) * ( 4 )  )  ) - ( 3 )  ) 
x = 519

x = 'a=5/2; 57+a-3 '
x = ( a = ( ( 5 ) / ( 2 )  )  ) ; ( ( ( 57 ) + ( a )  ) - ( 3 )  ) 
x = 56

!EOF!
ls -l tst.cmp
# The following exit is to ensure that extra garbage 
# after the end of the shar file will be ignored.
exit 0