#!/bin/sh
# This is a shar archive.
# The rest of this file is a shell script which will extract:
#
# 5_5A.h 5_5B.h 5_5E.h 5_5a.c 5_5a.cmp 5_5a0.c 5_5a1.c 5_5a2.c 5_5a3.c 5_5a4.c 5_5a5.c 5_5a_all.c 5_5a_pr.c 5_5b.c 5_5b.cmp 5_5b1.c 5_5b2.c 5_5b_pr.c 5_5c.cmp 5_5c1.c 5_5c2.c 5_5c3.c 5_5c3_6.c 5_5c3_W.c 5_5c3a.h 5_5c3b.h 5_5c3i.c 5_5c3iac.c 5_5c3iah.h 5_5c3sth.h 5_5c3sth6.h 5_5cO1.c 5_5cO2.c 5_5cO3.c 5_5cO4.c 5_5cOa.c 5_5cOb.c 5_5c_pr.c 5_5d.cmp 5_5d.h 5_5d1.c 5_5d2.c 5_5d3.c 5_5d_pr.c 5_5e.cmp 5_5e1.c 5_5e3.c 5_5e4.c 5_5e5.c 5_5e_all.c 5_5f1.c 5_5f2.c 5_5x1.c 5_5x2.c 5_5x3.c 5_5x4.c 5_5x5.c 5_5x6.c intalloc.c intalloc.h intset.c intset.h intset2.c junk.c main.c makefile stackalloc.h
#
# 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:03:33 EDT 1990
#
echo x - 5_5A.h
sed 's/^X//' > 5_5A.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=')'
};
!EOF!
ls -l 5_5A.h
echo x - 5_5B.h
sed 's/^X//' > 5_5B.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;
    exprtype type;
    int value;

    tree() { left = right = 0; }
    ~tree() { delete left; delete right; }
    void print(int level);	// DELETE
};

class expr
{
    tree *head;
    int evaluated, value;

public:
    expr(char*);
    ~expr() { delete head; }
    int eval();
    void print();
    void eprint();	// DELETE
};

struct token
{
    exprtype type;
    int value;
};
!EOF!
ls -l 5_5B.h
echo x - 5_5E.h
sed 's/^X//' > 5_5E.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
struct tree
{
    tree() { }
    virtual ~tree() { }
    virtual int eval() { return 0; }
    virtual void print() { }
};

struct unary_op : tree
{
    tree *left;
    unary_op() { left = 0; }
    ~unary_op() { delete left; }
};

struct binary_op : unary_op
{
    tree *right;
    binary_op() { right = 0; }
    ~binary_op() { delete right; }
};

struct number_leaf : tree
{
    int value;
    number_leaf(int v) { value = v; }
    int eval() { return value; }
    void print() { cout << "( " << value << " ) "; }
};

struct plus_op : binary_op
{
    int eval()
    { return left->eval() + right->eval(); }

    void print()
    {
	cout << "( ";
	left->print();
	cout << "+ ";
	right->print();
	cout << ") ";
    }
};

struct unary_minus_op : unary_op
{
    int eval()
    { return - left->eval(); }

    void print()
    {
	cout << "( - ";
	left->print();
    }
};

struct binary_minus_op : binary_op
{
    int eval()
    { return left->eval() - right->eval(); }

    void print()
    {
	cout << "( ";
	left->print();
	cout << "- ";
	right->print();
	cout << ") ";
    }
};

struct mult_op : binary_op
{
    int eval()
    { return left->eval() * right->eval(); }

    void print()
    {
	cout << "( ";
	left->print();
	cout << "* ";
	right->print();
	cout << ") ";
    }
};

struct div_op : binary_op
{
    int eval()
    {
	int l = left->eval();
	int r = right->eval();
	return (r != 0) ?
	       (l / r) :
	       error("division by 0");
    }

    void print()
    {
	cout << "( ";
	left->print();
	cout << "/ ";
	right->print();
	cout << ") ";
    }
};

struct lparen_op : unary_op
{
    int eval()
    { return left->eval(); }

    void print()
    {
	cout << "( ";
	left->print();
	cout << ") ";
    }
};

class expr
{
    tree *head;
    int evaluated, value;

public:
    expr(char*);
    ~expr() { delete head; }
    int eval();
    void print();
};

struct token
{
    exprtype type;
    int value;
};
!EOF!
ls -l 5_5E.h
echo x - 5_5a.c
sed 's/^X//' > 5_5a.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <5.5A.h>
static void treeprint(tree* head)
{
    if (head)
	switch (head->type)
	    {
	    case PLUS: case MINUS: case DIV: case MULT:
		cout << "(";
		treeprint(head->left);
		cout << chr(head->type);
		treeprint(head->right);
		cout << ")";
		break;

	    case NEG:
		cout << "-(";
		treeprint(head->left);
		cout << ")";
		break;

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

	    default:
		error("unknown type within tree");
		break;
	    }

    else
        error("null node found");
}

void expr:: print()
{
    treeprint(head);
}

!EOF!
ls -l 5_5a.c
echo x - 5_5a.cmp
sed 's/^X//' > 5_5a.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

!EOF!
ls -l 5_5a.cmp
echo x - 5_5a0.c
sed 's/^X//' > 5_5a0.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
static token curr_tok;

static void get_token(istream&);
static tree* get_expr(istream&);
static tree* term(istream&);
static tree* prim(istream&);
!EOF!
ls -l 5_5a0.c
echo x - 5_5a1.c
sed 's/^X//' > 5_5a1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
tree *expandtree(istream &input)
{
    if (curr_tok.type == END)
	{
if (debug)	cout << "expandtree() sees END\n";	// DELETE
	tree *ret = new tree;
	ret->type = NUMBER;
	ret->value = 0;
	return ret;
	}

    else
	return get_expr(input);
}

expr:: expr(char* s)
{
    istream input(strlen(s), s);
    evaluated = 0;
    get_token(input);
    head = expandtree(input);
    if (debug) head->print(0);	// DELETE
}
!EOF!
ls -l 5_5a1.c
echo x - 5_5a2.c
sed 's/^X//' > 5_5a2.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 &input)
{
    char ch;
    do  {	// skip whitespace
	if (!input.get(ch))
	    { curr_tok.type = END; return; }
    } while (isspace(ch));

    switch (ch)
	{
	case '*': case '/': case '+': case '-':
	case '(': case ')':
	    curr_tok.type = ch;
if (debug) cout << "get_token() returns '" << chr(ch) << "'\n"; // DELETE
	    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;
if (debug) cout << "get_token() returns NUMBER='" << curr_tok.value << "'\n"; // DELETE
	    return;

	default:
	    error("bad token");
	    curr_tok.type = END;
	    return;
	}
}
!EOF!
ls -l 5_5a2.c
echo x - 5_5a3.c
sed 's/^X//' > 5_5a3.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
static tree* get_expr(istream& input)
{
    tree* left = term(input);

    for (;;)
	switch (curr_tok.type)
	    {
	    case PLUS:
	    case MINUS:
if (debug) cout << "get_expr() sees +/-\n";	// DELETE
if (debug) { cout << "get_expr():left:\n"; left->print(0); }	// DELETE
		tree* head = new tree;
		head->type = curr_tok.type;
		head->left = left;
		get_token(input);	// eat '+','-'
		head->right = term(input);
		left = head;
if (debug) { cout << "get_expr():new left:\n"; left->print(0); } // DELETE
		break;

	    default:		// collapse node
if (debug) cout << "get_expr() sees other\n";	// DELETE
if (debug) { cout << "left:\n"; left->print(0); }	// DELETE
		return left;
	    }
}
!EOF!
ls -l 5_5a3.c
echo x - 5_5a4.c
sed 's/^X//' > 5_5a4.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
static tree* term(istream& input)
{
    tree* left = prim(input);

    for (;;)
	switch (curr_tok.type)
	    {
	    case MUL:
	    case DIV:
if (debug) cout << "term() sees +/-\n";	// DELETE
if (debug) { cout << "term():left:\n"; left->print(0); }	// DELETE
		tree* head = new tree;
		head->type = curr_tok.type;
		head->left = left;
		get_token(input);	// eat '*','/'
		head->right = prim(input);
		left = head;
if (debug) { cout << "term():new left:\n"; left->print(0); }	// DELETE
		break;

	    default:		// collapse node
if (debug) cout << "term() sees other\n";	// DELETE
if (debug) { cout << "left:\n"; left->print(0); }	// DELETE
		return left;
	    }
}
!EOF!
ls -l 5_5a4.c
echo x - 5_5a5.c
sed 's/^X//' > 5_5a5.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
static tree* prim(istream& input)
{
    tree* ret = new tree;

    switch (curr_tok.type)
	{
	case NUMBER:
if (debug) cout << "prim() sees NUMBER " << curr_tok.value << "\n";	// DELETE
	    ret->type = NUMBER;
	    ret->value = curr_tok.value;
	    get_token(input);		// skip number
if (debug) { cout << "prim():ret:\n"; ret->print(0); }	// DELETE
	    return ret;

	case MINUS:
if (debug) cout << "prim() sees -\n";	// DELETE
	    ret->type = MINUS;
	    get_token(input);		// skip '-'
	    ret->left = prim(input);
	    ret->right = 0;
if (debug) { cout << "prim():ret:\n"; ret->print(0); }	// DELETE
	    return ret;

	case LP:
if (debug) cout << "prim() sees (\n";	// DELETE
	    ret->type = LP;
	    get_token(input);		// skip '('
	    ret->left = get_expr(input);
	    if (curr_tok.type != RP)
	        {
		error(") expected");
		break;
		}
	    get_token(input);		// skip ')'
if (debug) { cout << "prim():ret:\n"; ret->print(0); }	// DELETE
	    return ret;

	case END:
if (debug) cout << "prim() sees END\n";	// DELETE
	    error("end of expression unexpected");
	    break;

	default:
if (debug) cout << "prim() sees UNKNOWN\n";	// DELETE
	    error("unknown type within tree");
	    break;
	}

    // error case
    ret->value = 0;
    ret->type = NUMBER;
    return ret;
}
!EOF!
ls -l 5_5a5.c
echo x - 5_5a_all.c
sed 's/^X//' > 5_5a_all.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 <debug.h>
int error(const char *fmt ...);

char prefix[512] = "....", *endprefix = &prefix[1];
char *incr()
{
    *endprefix++ = '.';
    *endprefix = '\0';
    return prefix+1;
}
char *decr()
{
    *--endprefix = '\0';
    return prefix;
}

char *unctrl(unsigned int c)
{
    static char x[5];
    char *p = x;

    if (c > 0177)
	*p++ = 'M', *p++ = '-', c -= 0200;
    if ((c < 040) || (c == 0177))
	*p++ = '^', *p++ = c ^ 0100;
    else
	*p++ = c;
    *p = '\0';
    return x;
}

#include "5_5A.h"	/* enum exprtype */
#include "5_5B.h"	/* class tree, expr, token */

#include "5_5a0.c"	/* forward declarations */

#include "5_5a5.c"	/* prim() */
#include "5_5a4.c"	/* term() */
#include "5_5a3.c"	/* get_expr() */
#include "5_5a2.c"	/* gettoken() */
#include "5_5a1.c"	/* expandtree, expr::expr() */

#include "5_5b2.c"	/* treeval() */
#include "5_5b1.c"	/* expr::eval() */

#include "main.c"

// print the expression tree
static char *spaces(int num)
{
    return form("%.*s", num * 3, " ");
}

void tree::print(int level)
{
    if (this)
	switch (this->type)
	    {
	    case PLUS:
	    case DIV:
	    case MUL:
		cout << spaces(level) << chr(this->type) << "\n";
		this->left->print(level + 1);
		this->right->print(level + 1);
		return;

	    case MINUS:
		cout << spaces(level) << chr(this->type) << "\n";
		if (this->right)
		    {
		    this->left->print(level + 1);
		    this->right->print(level + 1);
		    }
		else
		    this->left->print(level + 1);
		return;

	    case NUMBER:
		cout << spaces(level) << "# " << this->value << "\n";
		return;

	    case LP:
		cout << spaces(level) << chr(this->type) << "\n";
		this->left->print(level + 1);
		return;

	    case RP:
	    case END:
	    default:
		cout << spaces(level) << chr(this->type) << "\n";
		error("invalid type within tree");
		break;
	    }

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

void expr::eprint()
{ if (debug) head->print(0); }
!EOF!
ls -l 5_5a_all.c
echo x - 5_5a_pr.c
sed 's/^X//' > 5_5a_pr.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>
int error(const char *fmt ...);

#include "5_5A.h"
#include "5_5B.h"
#include "5_5c1.c"
!EOF!
ls -l 5_5a_pr.c
echo x - 5_5b.c
sed 's/^X//' > 5_5b.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <5.5A.h>
static void treeval(tree* head)
{
    if (head)
	{
	switch (head->type)
	    {
	    case PLUS:
	        return treeval(head->left) + treeval(head->right);

	    case MINUS:
	        return treeval(head->left) - treeval(head->right);

	    case DIV:
	        return treeval(head->left) / treeval(head->right);

	    case MULT:
	        return treeval(head->left) * treeval(head->right);

	    case NEG:
	        return -treeval(head->left);

	    case NUMBER:
	        return head->value;

	    default:
		error("unknown type within tree");
		break;
	    }

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

int expr:: eval()
{
    if (evaluated)
        return value;
    value = treeval(head);
    evaluated++;
}
!EOF!
ls -l 5_5b.c
echo x - 5_5b.cmp
sed 's/^X//' > 5_5b.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

!EOF!
ls -l 5_5b.cmp
echo x - 5_5b1.c
sed 's/^X//' > 5_5b1.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)
	{
	value = treeval(head);
	evaluated++;
	}
    return value;
}
!EOF!
ls -l 5_5b1.c
echo x - 5_5b2.c
sed 's/^X//' > 5_5b2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// Evaluate the given expression tree
static int treeval(tree* head)
{
    if (head)
	switch (head->type)
	    {
	    case PLUS:
		return treeval(head->left) +
		       treeval(head->right);

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

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

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

	    case NUMBER:
		return head->value;

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

	    case RP:
	    case END:
	    default:
		error("invalid type within tree");
		break;
	    }

    else
	error("NULL node found");
    return 0;
}
!EOF!
ls -l 5_5b2.c
echo x - 5_5b_pr.c
sed 's/^X//' > 5_5b_pr.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>
int error(const char *fmt ...);

#include "5_5A.h"
#include "5_5B.h"
#include "5_5c2.c"
!EOF!
ls -l 5_5b_pr.c
echo x - 5_5c.cmp
sed 's/^X//' > 5_5c.cmp << '!EOF!'
x = ''
x = 	MOVW &0, 0(%sp)
	MOVW 0(%sp), result

x = 0

x = '1 '
x = 	MOVW &1, 0(%sp)
	MOVW 0(%sp), result

x = 1

x = '2*3 '
x = 	MOVW &2, 0(%sp)
	MOVW &3, 4(%sp)
	MULW2 4(%sp), 0(%sp)
	MOVW 0(%sp), result

x = 6

x = '2-3 '
x = 	MOVW &2, 0(%sp)
	MOVW &3, 4(%sp)
	SUBW2 4(%sp), 0(%sp)
	MOVW 0(%sp), result

x = -1

x = '5/2'
x = 	MOVW &5, 0(%sp)
	MOVW &2, 4(%sp)
	DIVW2 4(%sp), 0(%sp)
	MOVW 0(%sp), result

x = 2

x = '123/4+123*4-3'
x = 	MOVW &123, 0(%sp)
	MOVW &4, 4(%sp)
	DIVW2 4(%sp), 0(%sp)
	MOVW &123, 4(%sp)
	MOVW &4, 8(%sp)
	MULW2 8(%sp), 4(%sp)
	ADDW2 4(%sp), 0(%sp)
	MOVW &3, 4(%sp)
	SUBW2 4(%sp), 0(%sp)
	MOVW 0(%sp), result

x = 519

!EOF!
ls -l 5_5c.cmp
echo x - 5_5c1.c
sed 's/^X//' > 5_5c1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// 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;

	    case RP:
	    case END:
	    default:
		error ("invalid type within tree");
		break;
	    }

    else
	error ("NULL node found");

    cout << " ) ";
}

void expr:: print()
{
    infixprint(head);
}

!EOF!
ls -l 5_5c1.c
echo x - 5_5c2.c
sed 's/^X//' > 5_5c2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// print out the tree in postfix format
static void postfixprint(tree* head)
{
    if (head)
	switch (head->type)
	    {
	    case PLUS: case DIV: case MUL:
		postfixprint(head->left);
		postfixprint(head->right);
		cout << chr(head->type);
		break;

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

		else
		    cout << "chg";
		break;

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

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

	    case RP:
	    case END:
	    default:
		error("invalid type within tree");
		break;
	    }

    else
	error("NULL node found");

    cout << " ";
}

void expr:: print()
{
    postfixprint(head);
}
!EOF!
ls -l 5_5c2.c
echo x - 5_5c3.c
sed 's/^X//' > 5_5c3.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// print out the tree in assembly format
// WE32100 version
#ifdef NONLOCAL		/* DELETE */
#include <intalloc.h>
#include <stackalloc.h>
#else		/* DELETE */
#include "intalloc.h"		/* DELETE */
#include "stackalloc.h"		/* DELETE */
#endif		/* DELETE */

// forward declaration of
// assemblyprint() for binop()
static void assemblyprint(tree* head,
    stackalloc &curloc, const intalloc *cursp);

#ifdef USE8086	/* DELETE */
#include "5_5c3_6.c"	/* DELETE */
#else		/* DELETE */
#include "5_5c3_W.c"	/* EXPAND */
#endif		/* DELETE */

// print out the appropriate assembly
// language instructions
static void assemblyprint(tree* head,
    stackalloc &curloc, const intalloc *cursp)
{
    if (head)
	{
	switch (head->type)
	    {
	    case PLUS: case MUL: case DIV:
		binop(head, curloc, cursp);
		break;

	    case MINUS:
		if (head->right)
		    binop(head, curloc, cursp);

		else
		    negop(head, curloc, cursp);
		break;

	    case NUMBER:
		svnumber(head, curloc);
		break;

	    case LP:
		assemblyprint(head->left, curloc,
		    cursp);
		break;

	    case RP:
	    case END:
	    default:
		error("invalid type within tree");
		break;
	    }
	}

    else
	error("NULL node found");
}

void expr:: print()
{
    setup();
    intalloc cursp(15, 15);
    stackalloc stacktop(&cursp);
    assemblyprint(head, stacktop, &cursp);
    finishup(stacktop);
}
!EOF!
ls -l 5_5c3.c
echo x - 5_5c3_6.c
sed 's/^X//' > 5_5c3_6.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// print out the tree in assembly format
// 8086 version

// initialize for the 8086
// set up register bp for the stack
void setup()
{
    cout << "\tpush bp\n" <<
	    "\tmov bp, sp\n";
}

// finish things up
void finishup(stackalloc &stacktop)
{
    cout << "\tmov ax, ";
    stacktop.print(cout) << "\n";
    cout << "\tmov result, ax\n";
    cout << "\tpop bp\n";
}

// print out a binary operator followed by the
// source and destination
static void binop(const tree *head,
    stackalloc &curloc, const intalloc *cursp)
{
    assemblyprint(head->left, curloc, cursp);
    stackalloc newloc(cursp);
    assemblyprint(head->right, newloc, cursp);
    cout << "\tmov ax,";
    curloc.print(cout) << "\n";
    cout << "\tmov bx,";
    newloc.print(cout) << "\n";

    switch (head->type)
	{
	case PLUS:  cout << "\tadd ax, bx\n"; break;
	case MUL:   cout << "\tmul bx\n"; break;
	case DIV:   cout << "\tmov dx, 0\n" <<
			    "\tdiv bx\n"; break;
	case MINUS: cout << "\tsub ax, bx\n"; break;
	}

    cout << "\tmov ";
    curloc.print(cout) << ", ax\n";
}

// print out a unary operator followed
// by the destination
static void negop(const tree *head,
    stackalloc &curloc, const intalloc *cursp)
{
    stackalloc newloc(cursp);
    assemblyprint(head->left, newloc, cursp);
    cout << "\tmov ax, ";
    newloc.print(cout) << "\n";
    cout << "\tneg ax";
    cout << "\tmov ";
    curloc.print(cout) << ", ax\n";
}

// store a number node at the current location
static void svnumber(tree* head, stackalloc &curloc)
{
    cout << "\tmov ";
    curloc.print(cout) << ", " << head->value << "\n";
}
!EOF!
ls -l 5_5c3_6.c
echo x - 5_5c3_W.c
sed 's/^X//' > 5_5c3_W.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// initialize for the WE32100
// (nothing to do)
void setup()
{
}

// finish things up
void finishup(stackalloc &stacktop)
{
    cout << "\tMOVW ";
    stacktop.print(cout) << ", result\n";
}

// print out a binary operator followed by the
// source and destination
static void binop(const tree *head,
    stackalloc &curloc, const intalloc *cursp)
{
    assemblyprint(head->left, curloc, cursp);
    stackalloc newloc(cursp);
    assemblyprint(head->right, newloc, cursp);

    switch (head->type)
	{
	case PLUS:  cout << "\tADDW2 "; break;
	case MUL:   cout << "\tMULW2 "; break;
	case DIV:   cout << "\tDIVW2 "; break;
	case MINUS: cout << "\tSUBW2 "; break;
	}

    newloc.print(cout) << ", ";
    curloc.print(cout) << "\n";
}

// print out a negate operator followed
// by the destination
static void negop(const tree *head,
    stackalloc &curloc, const intalloc *cursp)
{
    stackalloc newloc(cursp);
    assemblyprint(head->left, newloc, cursp);
    cout << "\tMNEGW2 ";
    newloc.print(cout) << ", ";
    curloc.print(cout) << "\n";
}

// store a number node at the current location
static void svnumber(tree* head, stackalloc &curloc)
{
    cout << "\tMOVW &" << head->value << ", ";
    curloc.print(cout) << "\n";
}
!EOF!
ls -l 5_5c3_W.c
echo x - 5_5c3a.h
sed 's/^X//' > 5_5c3a.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. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// intalloc.h
// allocate and deallocate a number
// from an integer set

#ifndef INTALLOC_H
# define INTALLOC_H

#ifdef NONLOCAL		/* DELETE */
#include <intset.h>
#else		/* DELETE */
#include "intset.h"	/* DELETE */
#endif		/* DELETE */

class intalloc
{
    intset *a;

public:
    intalloc(int m, int n) { a = new intset(m, n); }
    ~intalloc() { delete a; }

    int get();
    
    void free(int i)
    {
        a->remove(i);
    }
};
#endif /* INTALLOC_H */
!EOF!
ls -l 5_5c3a.h
echo x - 5_5c3b.h
sed 's/^X//' > 5_5c3b.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. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// stackalloc.h
// Manage a location on the stack.
// WE32100 version.
// Uses class intalloc to find
// the location.

#ifndef STACKALLOC_H
# define STACKALLOC_H

#ifdef NONLOCAL		/* DELETE */
#include <intalloc.h>
#else		/* DELETE */
#include "intalloc.h"	/* DELETE */
#endif		/* DELETE */
#include <stream.h>

class stackalloc
{
    int loc;
    const intalloc *ia;

public:
    stackalloc(const intalloc *a) :
	ia(a)
    {
	loc = a->get();
    }

    ~stackalloc()
    {
	ia->free(loc);
    }

#ifdef USE8086	/* DELETE */
#include "5_5c3sth6.h"	/* DELETE */
#else	/* DELETE */
    ostream &print(ostream &out)
    {
	out << (loc * 4) << "(%sp)";
	return out;
    }
#endif	/* DELETE */
};
#endif /* STACKALLOC_H */
!EOF!
ls -l 5_5c3b.h
echo x - 5_5c3i.c
sed 's/^X//' > 5_5c3i.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. */
#ifdef NONLOCAL	/* DELETE */
#include <intset.h>
#else /* DELETE */
#include "intset.h" /* DELETE */
#endif /* DELETE */

// remove a member from an intset
void intset::remove(int t)
{
    // look for the member
    // using a binary search,
    // just as was done in
    // intset::member()
    int l = 0;
    int u = cursize - 1;

    while (l <= u)
	{
	int m = (l+u) / 2;

	if (t < x[m]) u = m - 1;

	else if (t > x[m]) l = m + 1;

	else	// found it, shift the remaining
	    {	// elements to the left
	    for (int n = m + 1; n < cursize; n++, m++)
		x[m] = x[n];

	    cursize--;
	    return;
	    }
	}

    // not found, do nothing
}
!EOF!
ls -l 5_5c3i.c
echo x - 5_5c3iac.c
sed 's/^X//' > 5_5c3iac.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. */
#ifdef NONLOCAL	/* DELETE */
#include <intalloc.h>
#else /* DELETE */
#include "intalloc.h" /* DELETE */
#endif /* DELETE */

int intalloc::get()
{
    for (int i = 0; a->member(i); i++)
	;
    a->insert(i);
    return i;
}
!EOF!
ls -l 5_5c3iac.c
echo x - 5_5c3iah.h
sed 's/^X//' > 5_5c3iah.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. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// intalloc.h
// allocate and deallocate a number
// from an integer set

#ifndef INTALLOC_H
# define INTALLOC_H

#ifdef NONLOCAL		/* DELETE */
#include <intset.h>
#else		/* DELETE */
#include "intset.h"	/* DELETE */
#endif		/* DELETE */

class intalloc
{
    intset *a;

public:
    intalloc(int m, int n) { a = new intset(m, n); }
    ~intalloc() { delete a; }

    int get();
    
    void free(int i)
    {
        a->remove(i);
    }
};
#endif /* INTALLOC_H */
!EOF!
ls -l 5_5c3iah.h
echo x - 5_5c3sth.h
sed 's/^X//' > 5_5c3sth.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. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// stackalloc.h
// Manage a location on the stack.
// WE32100 version.
// Uses class intalloc to find
// the location.

#ifndef STACKALLOC_H
# define STACKALLOC_H

#ifdef NONLOCAL		/* DELETE */
#include <intalloc.h>
#else		/* DELETE */
#include "intalloc.h"	/* DELETE */
#endif		/* DELETE */
#include <stream.h>

class stackalloc
{
    int loc;
    const intalloc *ia;

public:
    stackalloc(const intalloc *a) :
	ia(a)
    {
	loc = a->get();
    }

    ~stackalloc()
    {
	ia->free(loc);
    }

#ifdef USE8086	/* DELETE */
#include "5_5c3sth6.h"	/* DELETE */
#else	/* DELETE */
    ostream &print(ostream &out)
    {
	out << (loc * 4) << "(%sp)";
	return out;
    }
#endif	/* DELETE */
};
#endif /* STACKALLOC_H */
!EOF!
ls -l 5_5c3sth.h
echo x - 5_5c3sth6.h
sed 's/^X//' > 5_5c3sth6.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// 8086 version of printing a
// location on the stack.
ostream &print(ostream &out)
{
    out << "[bp-" << ((loc * 2) + 2) << "]";
    return out;
}
!EOF!
ls -l 5_5c3sth6.h
echo x - 5_5cO1.c
sed 's/^X//' > 5_5cO1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include "5.5dir/5_5cOa.c"
#include "5.5dir/5_5c1.c"	/* expr::print() */
#include "5.5dir/5_5cOb.c"
!EOF!
ls -l 5_5cO1.c
echo x - 5_5cO2.c
sed 's/^X//' > 5_5cO2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include "5.5dir/5_5cOa.c"
#include "5.5dir/5_5c2.c"	/* expr::print() */
#include "5.5dir/5_5cOb.c"
!EOF!
ls -l 5_5cO2.c
echo x - 5_5cO3.c
sed 's/^X//' > 5_5cO3.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include "5.5dir/5_5cOa.c"
#include "5.5dir/5_5c3.c"	/* expr::print() */
#include "5.5dir/5_5cOb.c"
#include "5.5dir/5_5c3iac.c"
#include "5.5dir/5_5c3i.c"
#include "5.5dir/intset.c"
!EOF!
ls -l 5_5cO3.c
echo x - 5_5cO4.c
sed 's/^X//' > 5_5cO4.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#define USE8086
#include "5.5dir/5_5cOa.c"
#include "5.5dir/5_5c3.c"	/* expr::print() */
#include "5.5dir/5_5cOb.c"
#include "5.5dir/5_5c3iac.c"
#include "5.5dir/5_5c3i.c"
#include "5.5dir/intset.c"
!EOF!
ls -l 5_5cO4.c
echo x - 5_5cOa.c
sed 's/^X//' > 5_5cOa.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>
int error(const char *fmt ...);

char prefix[512] = "....", *endprefix = &prefix[1];
char *incr()
{
    *endprefix++ = '.';
    *endprefix = '\0';
    return prefix+1;
}
char *decr()
{
    *--endprefix = '\0';
    return prefix;
}

char *unctrl(unsigned int c)
{
    static char x[5];
    char *p = x;

    if (c > 0177)
	*p++ = 'M', *p++ = '-', c -= 0200;
    if ((c < 040) || (c == 0177))
	*p++ = '^', *p++ = c ^ 0100;
    else
	*p++ = c;
    *p = '\0';
    return x;
}

#include "5_5A.h"	/* enum exprtype */
#include "5_5B.h"	/* class tree, expr, token */

#include "5_5a0.c"	/* forward declarations */

#include "5_5a5.c"	/* prim() */
#include "5_5a4.c"	/* term() */
#include "5_5a3.c"	/* get_expr() */
#include "5_5a2.c"	/* gettoken() */
#include "5_5a1.c"	/* expandtree, expr::expr() */

#include "5_5b2.c"	/* treeval() */
#include "5_5b1.c"	/* expr::eval() */
!EOF!
ls -l 5_5cOa.c
echo x - 5_5cOb.c
sed 's/^X//' > 5_5cOb.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
main(int, char)
{
    char *s = "123/4+123*4-3";
    expr x(s);
    x.print();
    cout << "\n";
    return 0;
}

// print the expression tree
static char *spaces(int num)
{
    return form("%.*s", num * 3, " ");
}

void tree::print(int level)
{
    if (this)
	switch (this->type)
	    {
	    case PLUS:
	    case DIV:
	    case MUL:
		cout << spaces(level) << chr(this->type) << "\n";
		this->left->print(level + 1);
		this->right->print(level + 1);
		return;

	    case MINUS:
		cout << spaces(level) << chr(this->type) << "\n";
		if (this->right)
		    {
		    this->left->print(level + 1);
		    this->right->print(level + 1);
		    }
		else
		    this->left->print(level + 1);
		return;

	    case NUMBER:
		cout << spaces(level) << "# " << this->value << "\n";
		return;

	    case LP:
		cout << spaces(level) << chr(this->type) << "\n";
		this->left->print(level + 1);
		return;

	    case RP:
	    case END:
	    default:
		cout << spaces(level) << chr(this->type) << "\n";
		error("invalid type within tree");
		break;
	    }

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

void expr::eprint()
{ head->print(0); }
!EOF!
ls -l 5_5cOb.c
echo x - 5_5c_pr.c
sed 's/^X//' > 5_5c_pr.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. */
#include <stream.h>
#include <string.h>
#include <ctype.h>
int error(const char *fmt ...);

#include "5_5A.h"
#include "5_5B.h"
#include "5_5c3.c"
!EOF!
ls -l 5_5c_pr.c
echo x - 5_5d.cmp
sed 's/^X//' > 5_5d.cmp << '!EOF!'
x = ''
x = 	push bp
	mov bp, sp
	mov [bp-2], 0
	mov ax, [bp-2]
	mov result, ax
	pop bp

x = 0

x = '1 '
x = 	push bp
	mov bp, sp
	mov [bp-2], 1
	mov ax, [bp-2]
	mov result, ax
	pop bp

x = 1

x = '2*3 '
x = 	push bp
	mov bp, sp
	mov [bp-2], 2
	mov [bp-4], 3
	mov ax,[bp-2]
	mov bx,[bp-4]
	mul bx
	mov [bp-2], ax
	mov ax, [bp-2]
	mov result, ax
	pop bp

x = 6

x = '2-3 '
x = 	push bp
	mov bp, sp
	mov [bp-2], 2
	mov [bp-4], 3
	mov ax,[bp-2]
	mov bx,[bp-4]
	sub ax, bx
	mov [bp-2], ax
	mov ax, [bp-2]
	mov result, ax
	pop bp

x = -1

x = '5/2'
x = 	push bp
	mov bp, sp
	mov [bp-2], 5
	mov [bp-4], 2
	mov ax,[bp-2]
	mov bx,[bp-4]
	mov dx, 0
	div bx
	mov [bp-2], ax
	mov ax, [bp-2]
	mov result, ax
	pop bp

x = 2

x = '123/4+123*4-3'
x = 	push bp
	mov bp, sp
	mov [bp-2], 123
	mov [bp-4], 4
	mov ax,[bp-2]
	mov bx,[bp-4]
	mov dx, 0
	div bx
	mov [bp-2], ax
	mov [bp-4], 123
	mov [bp-6], 4
	mov ax,[bp-4]
	mov bx,[bp-6]
	mul bx
	mov [bp-4], ax
	mov ax,[bp-2]
	mov bx,[bp-4]
	add ax, bx
	mov [bp-2], ax
	mov [bp-4], 3
	mov ax,[bp-2]
	mov bx,[bp-4]
	sub ax, bx
	mov [bp-2], ax
	mov ax, [bp-2]
	mov result, ax
	pop bp

x = 519

!EOF!
ls -l 5_5d.cmp
echo x - 5_5d.h
sed 's/^X//' > 5_5d.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;
    exprtype type;
    int value;
};

class expr
{
    char *str;
    int evaluated, value;

public:
    expr(char*);
    ~expr() { delete str; }
    int eval();
    void print();
};

struct token
{
    exprtype type;
    int value;
};
!EOF!
ls -l 5_5d.h
echo x - 5_5d1.c
sed 's/^X//' > 5_5d1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <string.h>
expr:: expr(char* s)
{
    str = new char[strlen(s) + 1];
    strcpy(str, s);
    evaluated = 0;
}
!EOF!
ls -l 5_5d1.c
echo x - 5_5d2.c
sed 's/^X//' > 5_5d2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
int expr::eval()
{
    if (!evaluated)
	{
	istream input(strlen(s), s);
	get_token(input);
	tree *head = expandtree(input);
	value = treeval(head);
	delete head;
	evaluated++;
	}

    return value;
}
!EOF!
ls -l 5_5d2.c
echo x - 5_5d3.c
sed 's/^X//' > 5_5d3.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
void expr:: print()
{
    tree *head = expandtree(input);
    infixprint(head);
    delete head;
}
!EOF!
ls -l 5_5d3.c
echo x - 5_5d_pr.c
sed 's/^X//' > 5_5d_pr.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. */
#include <stream.h>
#include <string.h>
#include <ctype.h>
int error(const char *fmt ...);

#include "5_5A.h"
#include "5_5B.h"
#include "5_5c3.c"
!EOF!
ls -l 5_5d_pr.c
echo x - 5_5e.cmp
sed 's/^X//' > 5_5e.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

!EOF!
ls -l 5_5e.cmp
echo x - 5_5e1.c
sed 's/^X//' > 5_5e1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
tree *expandtree(istream &input)
{
    if (curr_tok.type == END)
	return new number_leaf(0);

    else
	return get_expr(input);
}

expr:: expr(char* s)
{
    istream input(strlen(s), s);
    evaluated = 0;
    get_token(input);
    head = expandtree(input);
}
!EOF!
ls -l 5_5e1.c
echo x - 5_5e3.c
sed 's/^X//' > 5_5e3.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
static tree* get_expr(istream& input)
{
    tree* left = term(input);

    for (;;)
	switch (curr_tok.type)
	    {
	    case PLUS:
	        plus_op *headp = new plus_op;
		headp->left = left;
		get_token(input);	// eat '+'
		headp->right = term(input);
		left = headp;
		break;

	    case MINUS:
		binary_minus_op* headm = new binary_minus_op;
		headm->left = left;
		get_token(input);	// eat '-'
		headm->right = term(input);
		left = headm;
		break;

	    default:		// collapse node
		return left;
	    }
}
!EOF!
ls -l 5_5e3.c
echo x - 5_5e4.c
sed 's/^X//' > 5_5e4.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
static tree* term(istream& input)
{
    tree* left = prim(input);

    for (;;)
	switch (curr_tok.type)
	    {
	    case MUL:
		mult_op *headm = new mult_op;
		headm->left = left;
		get_token(input);	// eat '*'
		headm->right = prim(input);
		left = headm;
		break;

	    case DIV:
		div_op *headd = new div_op;
		headd->left = left;
		get_token(input);	// eat '/'
		headd->right = prim(input);
		left = headd;
		break;

	    default:		// collapse node
		return left;
	    }
}
!EOF!
ls -l 5_5e4.c
echo x - 5_5e5.c
sed 's/^X//' > 5_5e5.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
static tree* prim(istream& input)
{
    switch (curr_tok.type)
	{
	case NUMBER:
	    number_leaf* retn =
		new number_leaf(curr_tok.value);
	    get_token(input);		// skip number
	    return retn;

	case MINUS:
	    unary_minus_op *retm = new unary_minus_op;
	    get_token(input);		// skip '-'
	    retm->left = prim(input);
	    return retm;

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

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

	default:
	    error("unknown type within tree");
	    break;
	}

    // error case
    number_leaf *ret = new number_leaf(0);
    return ret;
}
!EOF!
ls -l 5_5e5.c
echo x - 5_5e_all.c
sed 's/^X//' > 5_5e_all.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 <debug.h>
int error(const char *fmt ...);

char prefix[512] = "....", *endprefix = &prefix[1];
char *incr()
{
    *endprefix++ = '.';
    *endprefix = '\0';
    return prefix+1;
}
char *decr()
{
    *--endprefix = '\0';
    return prefix;
}

char *unctrl(unsigned int c)
{
    static char x[5];
    char *p = x;

    if (c > 0177)
	*p++ = 'M', *p++ = '-', c -= 0200;
    if ((c < 040) || (c == 0177))
	*p++ = '^', *p++ = c ^ 0100;
    else
	*p++ = c;
    *p = '\0';
    return x;
}

#include "5_5A.h"	/* enum exprtype */
#include "5_5E.h"	/* class tree, expr, token */

#include "5_5a0.c"	/* forward declarations */

#include "5_5e5.c"	/* prim() */
#include "5_5e4.c"	/* term() */
#include "5_5e3.c"	/* get_expr() */
#include "5_5a2.c"	/* gettoken() */
#include "5_5e1.c"	/* expandtree, expr::expr() */

#include "5_5f2.c"	/* treeval() */
#include "5_5f1.c"	/* expr::eval() */

#include "main.c"
!EOF!
ls -l 5_5e_all.c
echo x - 5_5f1.c
sed 's/^X//' > 5_5f1.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)
	{
	value = head->eval();
	evaluated++;
	}
    return value;
}
!EOF!
ls -l 5_5f1.c
echo x - 5_5f2.c
sed 's/^X//' > 5_5f2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
void expr:: print()
{
    head->print();
}

!EOF!
ls -l 5_5f2.c
echo x - 5_5x1.c
sed 's/^X//' > 5_5x1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
class expr
{
    // ...
public:
    expr(char*);
    int eval();
    void print();
};
!EOF!
ls -l 5_5x1.c
echo x - 5_5x2.c
sed 's/^X//' > 5_5x2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
expr x("123/4+123*4-3");
cout << "x = " << x.eval() << "\n";
x.print();
!EOF!
ls -l 5_5x2.c
echo x - 5_5x3.c
sed 's/^X//' > 5_5x3.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
infixprint(head->left);
cout << " + ";
infixprint(head->right);
!EOF!
ls -l 5_5x3.c
echo x - 5_5x4.c
sed 's/^X//' > 5_5x4.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
cout << " ( ";
infixprint(head->left);
cout << " + ";
infixprint(head->right);
cout << " ) ";
!EOF!
ls -l 5_5x4.c
echo x - 5_5x5.c
sed 's/^X//' > 5_5x5.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
postfixprint(head->left);
postfixprint(head->right);
cout << " + ";
!EOF!
ls -l 5_5x5.c
echo x - 5_5x6.c
sed 's/^X//' > 5_5x6.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
return treeval(head->left) + treeval(head->right);
!EOF!
ls -l 5_5x6.c
echo x - intalloc.c
sed 's/^X//' > intalloc.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. */
#ifdef NONLOCAL	/* DELETE */
#include <intalloc.h>
#else /* DELETE */
#include "intalloc.h" /* DELETE */
#endif /* DELETE */

int intalloc::get()
{
    for (int i = 0; a->member(i); i++)
	;
    a->insert(i);
    return i;
}
!EOF!
ls -l intalloc.c
echo x - intalloc.h
sed 's/^X//' > intalloc.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. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// intalloc.h
// allocate and deallocate a number
// from an integer set

#ifndef INTALLOC_H
# define INTALLOC_H

#ifdef NONLOCAL		/* DELETE */
#include <intset.h>
#else		/* DELETE */
#include "intset.h"	/* DELETE */
#endif		/* DELETE */

class intalloc
{
    intset *a;

public:
    intalloc(int m, int n) { a = new intset(m, n); }
    ~intalloc() { delete a; }

    int get();
    
    void free(int i)
    {
        a->remove(i);
    }
};
#endif /* INTALLOC_H */
!EOF!
ls -l intalloc.h
echo x - intset.c
sed 's/^X//' > intset.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
extern int error(const char * ...);
#ifdef NONLOCAL	/* DELETE */
#include <intset.h>
#else /* DELETE */
#include "intset.h" /* DELETE */
#endif /* DELETE */

intset::intset(int m, int n)
{
    if (m < 1 || n < m) error("illegal intset size");
    cursize = 0;
    maxsize = m;
    x = new int[maxsize];
}

intset:: ~intset()
{

    delete x;
}

void intset::insert(int t)
{
    if (++cursize > maxsize) error("too many elements in intset");
    int i = cursize - 1;
    x[i] = t;
    while (i > 0 && x[i-1] > x[i])
	{
	int t = x[i];
	x[i] = x[i-1];
	x[i-1] = t;
	i--;
	}
}

int intset::member(int t)
{
    int l = 0;
    int u = cursize - 1;
    while (l <= u)
	{
	int m = (l+u) / 2;
	if (t < x[m]) u = m - 1;
	else if (t > x[m]) l = m + 1;
	else return 1;
	}
    return 0;
}
!EOF!
ls -l intset.c
echo x - intset.h
sed 's/^X//' > intset.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#ifndef INTSET_H
# define INTSET_H
class intset
{
    int cursize, maxsize;
    int *x;
public:
    intset(int m, int n);
    ~intset();
    
    int member(int t);
    void insert(int t);
    void remove(int i);
    
    void iterate(int &i) { i = 0; }
    int ok(int& i) { return i < cursize; }
    int next(int& i) { return x[i++]; }
};
#endif /* INTSET_H */
!EOF!
ls -l intset.h
echo x - intset2.c
sed 's/^X//' > intset2.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. */
#ifdef NONLOCAL	/* DELETE */
#include <intset.h>
#else /* DELETE */
#include "intset.h" /* DELETE */
#endif /* DELETE */

// remove a member from an intset
void intset::remove(int t)
{
    // look for the member
    // using a binary search,
    // just as was done in
    // intset::member()
    int l = 0;
    int u = cursize - 1;

    while (l <= u)
	{
	int m = (l+u) / 2;

	if (t < x[m]) u = m - 1;

	else if (t > x[m]) l = m + 1;

	else	// found it, shift the remaining
	    {	// elements to the left
	    for (int n = m + 1; n < cursize; n++, m++)
		x[m] = x[n];

	    cursize--;
	    return;
	    }
	}

    // not found, do nothing
}
!EOF!
ls -l intset2.c
echo x - junk.c
sed 's/^X//' > junk.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
foo()
{
    int a = 1, b = 2, c = 3, d;
    d = a + b * c;
}
!EOF!
ls -l junk.c
echo x - main.c
sed 's/^X//' > main.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
char *strs[] =
{
    "",
    "1 ",
    "2*3 ",
    "2-3 ",
    "5/2",
    "123/4+123*4-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 main.c
echo x - makefile
sed 's/^X//' > makefile << '!EOF!'
CC= CC -I. -I../../CC
ERROR=  ../../error.a
CFLAGS= -I.
ALLSRC = 5_5A.h 5_5B.h 5_5a0.c 5_5a1.c 5_5a2.c 5_5a3.c 5_5a4.c 5_5a5.c 5_5b1.c 5_5b2.c

all: 5_5a_all 5_5b_all 5_5c_all 5_5d_all 5_5e_all

5_5a_all.o: $(ALLSRC) 5_5a_all.c main.c
	$(CC) -c $(CFLAGS) 5_5a_all.c

5_5a_pr.o: 5_5a_pr.c 5_5A.h 5_5B.h 5_5c1.c
	$(CC) -c $(CFLAGS) 5_5a_pr.c

5_5b_pr.o: 5_5b_pr.c 5_5A.h 5_5B.h 5_5c2.c
	$(CC) -c $(CFLAGS) 5_5b_pr.c

5_5c_pr.o: 5_5c_pr.c 5_5A.h 5_5B.h 5_5c3.c \
	5_5c3_W.c \
	intalloc.h stackalloc.h intset.h
	$(CC) -c $(CFLAGS) 5_5c_pr.c

5_5d_pr.o: 5_5c_pr.c 5_5A.h 5_5B.h 5_5c3.c \
	5_5c3_6.c \
	intalloc.h stackalloc.h intset.h
	-ln -f 5_5c_pr.c 5_5d_pr.c
	$(CC) $(CFLAGS) -DUSE8086 -c 5_5d_pr.c

5_5a_all: 5_5a_all.o 5_5a_pr.o
	$(CC) $(CFLAGS) 5_5a_all.o 5_5a_pr.o -o 5_5a_all $(ERROR)

5_5b_all: 5_5a_all.o 5_5b_pr.o
	$(CC) $(CFLAGS) 5_5a_all.o 5_5b_pr.o -o 5_5b_all $(ERROR)

5_5c_all: 5_5a_all.o 5_5c_pr.o intset.o intset2.o intalloc.o
	$(CC) $(CFLAGS) 5_5a_all.o 5_5c_pr.o intset.o intset2.o intalloc.o -o 5_5c_all $(ERROR)

5_5d_all: 5_5a_all.o 5_5d_pr.o intset.o intset2.o intalloc.o
	$(CC) $(CFLAGS) 5_5a_all.o 5_5d_pr.o intset.o intset2.o intalloc.o -o 5_5d_all $(ERROR)

5_5e_all.o: 5_5A.h 5_5E.h 5_5a0.c 5_5e5.c 5_5e4.c 5_5e3.c 5_5a2.c 5_5e1.c 5_5f2.c 5_5f1.c main.c
	$(CC) -c $(CFLAGS) 5_5e_all.c

5_5e_all: 5_5e_all.o
	$(CC) $(CFLAGS) 5_5e_all.o -o 5_5e_all $(ERROR)

intset.o: intset.c intset.h
	$(CC) -c $(CFLAGS) intset.c

intset2.o: intset2.c intset.h
	$(CC) -c $(CFLAGS) intset2.c

intalloc.o: intalloc.c intalloc.h
	$(CC) -c $(CFLAGS) intalloc.c

CMP= 5_5a.cmp 5_5b.cmp 5_5c.cmp 5_5d.cmp 5_5e.cmp
OUT= 5_5a.out 5_5b.out 5_5c.out 5_5d.out 5_5e.out

5_5a.out: 5_5a_all ;	5_5a_all > 5_5a.out
5_5b.out: 5_5b_all ;	5_5b_all > 5_5b.out
5_5c.out: 5_5c_all ;	5_5c_all > 5_5c.out
5_5d.out: 5_5d_all ;	5_5d_all > 5_5d.out
5_5e.out: 5_5e_all ;	5_5e_all > 5_5e.out

test: all $(OUT) $(CMP)
	cmp 5_5a.out 5_5a.cmp
	cmp 5_5b.out 5_5b.cmp
	cmp 5_5c.out 5_5c.cmp
	cmp 5_5d.out 5_5d.cmp
	cmp 5_5e.out 5_5e.cmp
	echo tests done
!EOF!
ls -l makefile
echo x - stackalloc.h
sed 's/^X//' > stackalloc.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. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// stackalloc.h
// Manage a location on the stack.
// WE32100 version.
// Uses class intalloc to find
// the location.

#ifndef STACKALLOC_H
# define STACKALLOC_H

#ifdef NONLOCAL		/* DELETE */
#include <intalloc.h>
#else		/* DELETE */
#include "intalloc.h"	/* DELETE */
#endif		/* DELETE */
#include <stream.h>

class stackalloc
{
    int loc;
    const intalloc *ia;

public:
    stackalloc(const intalloc *a) :
	ia(a)
    {
	loc = a->get();
    }

    ~stackalloc()
    {
	ia->free(loc);
    }

#ifdef USE8086	/* DELETE */
#include "5_5c3sth6.h"	/* DELETE */
#else	/* DELETE */
    ostream &print(ostream &out)
    {
	out << (loc * 4) << "(%sp)";
	return out;
    }
#endif	/* DELETE */
};
#endif /* STACKALLOC_H */
!EOF!
ls -l stackalloc.h
# The following exit is to ensure that extra garbage 
# after the end of the shar file will be ignored.
exit 0