13.cpp

《数据结构与程序设计》书本所有源代码！！！！

/* Program extracts from Chapter 13 of
   "Data Structures and Program Design in C++"
   by Robert L. Kruse and Alexander J. Ryba
   Copyright (C) 1999 by Prentice-Hall, Inc.  All rights reserved.
   Extracts from this file may be used in the construction of other programs,
   but this code will not compile or execute as given here. */


// Section 13.3:

Error_code Expression::evaluate_prefix(Value &result)
/*  Outline of a method to perform prefix evaluation of an Expression.
    The details depend on further decisions about the implementation of
    expressions and values.*/
{
   if (the Expression is empty) return fail;
   else {
      remove the first symbol from the Expression, and
         store the value of the symbol as t;
      if (t is a unary operation) {
        Value the_argument;
        if (evaluate_prefix(the_argument) == fail) return fail;
        else result = the value of operation t applied to the_argument;
      }
      else if (t is a binary operation) {
        Value first_argument, second_argument;
        if (evaluate_prefix(first_argument) == fail) return fail;
        if (evaluate_prefix(second_argument) == fail) return fail;
        result  = the value of operation t
                      applied to first_argument and second_argument;
      }
      else              //  t is a numerical operand.
        result = the value of t;
   }
   return success;
}


class Expression {
public:
   Error_code evaluate_prefix(Value &result);
   Error_code get_token(Token &result);
   //  Add other methods.
private:
   //  Add data members to store an expression.
};


enum Token_type {
   operand, unaryop, binaryop    //  Add any other legitimate token types.
};


Value do_unary(const Token &operation, const Value &the_argument);
Value do_binary(const Token &operation,
                const Value &first_argument, const Value &second_argument);
Value get_value(const Token &operand);


Error_code Expression::evaluate_prefix(Value &result)
/*
Post: If the Expression does not begin with a legal prefix expression, a code
      of fail is returned.  Otherwise a code of success is returned, and
      the Expression is evaluated, giving the Value result.  The initial
      tokens that are evaluated are removed from the Expression.
*/
{
   Token t;
   Value the_argument, first_argument, second_argument;
   if (get_token(t) == fail) return fail;
   switch (t.kind()) {
   case unaryop:
      if (evaluate_prefix(the_argument) == fail) return fail;
      else result = do_unary(t, the_argument);
      break;
   case binaryop:
      if (evaluate_prefix(first_argument) == fail) return fail;
      if (evaluate_prefix(second_argument) == fail) return fail;
      else result = do_binary(t, first_argument, second_argument);
      break;
   case operand:
      result = get_value(t);
      break;
   }
   return success;
}


typedef Value Stack_entry;   //  Set the type of entry to use in stacks.

Error_code Expression::evaluate_postfix(Value &result)
/*
Post: The tokens in Expression up to the first end_expression symbol are
      removed.  If these tokens do not represent a legal postfix expression, a
      code of fail is returned.   Otherwise a code of success is returned,
      and the removed sequence of tokens is evaluated to give Value result.
*/
{
   Token t;             //  Current operator or operand
   Stack operands;      //  Holds values until operators are seen
   Value the_argument, first_argument, second_argument;
   do {
      if (get_token(t) == fail) return fail;   //  No end_expression token
      switch (t.kind()) {
      case unaryop:
         if (operands.empty()) return fail;
         operands.top(the_argument);
         operands.pop();
         operands.push(do_unary(t, the_argument));
         break;
      case binaryop:
         if (operands.empty()) return fail;
         operands.top(second_argument);
         operands.pop();
         if (operands.empty()) return fail;
         operands.top(first_argument);
         operands.pop();
         operands.push(do_binary(t, first_argument, second_argument));
         break;
      case operand:
         operands.push(get_value(t));
         break;
      case end_expression:
         break;
      }
   } while (t.kind() != end_expression);
   if (operands.empty()) return fail;
   operands.top(result);
   operands.pop();
   if (!operands.empty()) return fail;  //  surplus operands detected
   return success;
}


Error_code Expression::evaluate_postfix(Value &result)
/*
Post: The tokens in Expression up to the first end_expression symbol are
      removed.  If these tokens do not represent a legal postfix expression, a
      code of fail is returned.   Otherwise a code of success is returned,
      and the removed sequence of tokens is evaluated to give Value result.
*/
{
   Token first_token, final_token;
   Error_code outcome;
   if (get_token(first_token) == fail || first_token.kind() != operand)
      outcome = fail;
   else {
      outcome = recursive_evaluate(first_token, result, final_token);
      if (outcome == success && final_token.kind() != end_expression)
         outcome = fail;
   }
   return outcome;
}


Error_code Expression::recursive_evaluate(const Token &first_token,
                                          Value &result, Token &final_token)
/*
Pre:  Token first_token is an operand.
Post: If the first_token can be combined with initial tokens of
      the Expression to yield a legal postfix expression followed
      by either an end_expression symbol or a binary operator,
      a code of success is returned, the legal postfix subexpression
      is evaluated, recorded in result, and the terminating Token is
      recorded as final_token.  Otherwise a code of fail is returned.
      The initial tokens of Expression are removed.
Uses: Methods of classes Token and Expression, including
      recursive_evaluate and functions do_unary, do_binary,
      and get_value.
*/
{
   Value first_segment = get_value(first_token),
         next_segment;
   Error_code outcome;
   Token current_token;
   Token_type current_type;
   do {
      outcome = get_token(current_token);
      if (outcome != fail) {
         switch (current_type = current_token.kind()) {
         case binaryop:          //  Binary operations terminate subexpressions.
         case end_expression:    //  Treat subexpression terminators together.
            result = first_segment;
            final_token = current_token;
            break;
         case unaryop:
            first_segment = do_unary(current_token, first_segment);
            break;
         case operand:
            outcome = recursive_evaluate(current_token,
                                         next_segment, final_token);
            if (outcome == success && final_token.kind() != binaryop)
               outcome = fail;
            else

               first_segment = do_binary(final_token, first_segment,
                                         next_segment);
            break;
         }
      }
   } while (outcome == success && current_type != end_expression &&
                                  current_type != binaryop);
   return outcome;
}




// Section 13.4:

Expression Expression::infix_to_postfix()
/*
Pre:  The Expression stores a valid infix expression.
Post: A postfix expression that translates the infix expression is returned.
*/
{
   Expression answer;
   Token current, prior;
   Stack delayed_operations;
   while (get_token(current) != fail) {
      switch (current.kind()) {
      case operand:
         answer.put_token(current);
         break;
      case leftparen:
         delayed_operations.push(current);
         break;
      case rightparen:
         delayed_operations.top(prior);
         while (prior.kind() != leftparen) {
            answer.put_token(prior);
            delayed_operations.pop();
            delayed_operations.top(prior);
         }
         delayed_operations.pop();
         break;
      case unaryop:
      case binaryop:               //  Treat all operators together.
         bool end_right = false;   //  End of right operand reached?

         do {
            if (delayed_operations.empty()) end_right = true;
            else {
               delayed_operations.top(prior);
               if (prior.kind() == leftparen) end_right = true;
               else if (prior.priority() < current.priority()) end_right = true;
               else if (current.priority() == 6) end_right = true;
               else answer.put_token(prior);
               if (!end_right) delayed_operations.pop();
            }
         } while (!end_right);

         delayed_operations.push(current);
         break;
      }
   }
   while (!delayed_operations.empty()) {
      delayed_operations.top(prior);
      answer.put_token(prior);
      delayed_operations.pop();
   }
   answer.put_token(";");
   return answer;
}




// Section 13.5:

int main()
/*
Pre:  None
Post: Acts as a menu-driven graphing program.
Uses: Classes Expression and Plot,
      and functions introduction, get_command,
      and do_command.
*/
{
   introduction();
   Expression infix;      //  Infix expression from user
   Expression postfix;    //  Postfix translation
   Plot graph;
   char ch;
   while ((ch = get_command()) != 'q')
      do_command(ch, infix, postfix, graph);
}


void do_command(char c, Expression &infix, Expression &postfix, Plot &graph)
/*
Pre:  None
Post: Performs the user command represented by char c on the
      Expression infix, the Expression postfix, and the Plot graph.
Uses: Classes Token, Expression and Plot.
*/
{
   switch (c) {
   case 'r':      //  Read an infix expression from the user.
      infix.clear();
      infix.read();
      if (infix.valid_infix() == success) postfix = infix.infix_to_postfix();
      else cout << "Warning: Bad expression ignored. " << endl;
      break;
   case 'w':      //  Write the current expression.
      infix.write();
      postfix.write();
      break;
   case 'g':      //  Graph the current postfix expression.
      if (postfix.size() <= 0)
         cout << "Enter a valid expression before graphing!" << endl;
      else {
         graph.clear();
         graph.find_points(postfix);
         graph.draw();
      }
      break;
   case 'l':    //  Set the graph limits.
      if (graph.set_limits() != success)
         cout << "Warning: Invalid limits" << endl;
      break;
   case 'p':    //  Print the graph parameters.
      Token::print_parameters();
      break;
   case 'n':    //  Set new graph parameters.
      Token::set_parameters();
      break;
   case 'h':    //  Give help to user.
      help();
      break;
   }
}


struct Token_record {
   String name;
   double value;
   int priority;
   Token_type kind;
};


struct Lexicon {
   Lexicon();
   int hash(const String &x) const;
   void set_standard_tokens();  //  Set up the predefined tokens.
   int count;                   //  Number of records in the Lexicon
   int index_code[hash_size];   //  Declare the hash table.
   Token_record token_data[hash_size];
};


class Token {
public:
//  Add methods here.
private:
   int code;
   static Lexicon symbol_table;
   static List<int> parameters;
};

List<int> Token::parameters;   //  Allocate storage for static Token members.
Lexicon Token::symbol_table;


class Expression {
public:
//  Add method prototypes.
private:
   List<Token> terms;
   int current_term;
//  Add auxiliary function prototypes.
};


class Token {
public:
   Token() {}
   Token (const String &x);
   Token_type kind() const;
   int priority() const;
   double value() const;
   String name() const;
   int code_number() const;
   static void set_parameters();
   static void print_parameters();
   static void set_x(double x_val);

private:
   int code;
   static Lexicon symbol_table;
   static List<int> parameters;
};


Token_type Token::kind() const
{