/* 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:  NonePost: 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:  NonePost: 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{