expr.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 268 行

Expression::Expression()
{
   current_term = 0;
}

Expression::Expression(const Expression &original)
{
   terms = original.terms;
   current_term = original.current_term;
}
 
int Expression::size()
{
   return terms.size();
}
 
void Expression::write()
{
   Token t;
   for (int i = 0; i < terms.size(); i++) {
      terms.retrieve(i, t);
      cout << (t.name()).c_str() << " ";
   }
   cout << endl;
}
 
void Expression::rewind()
{
   current_term = 0;
}
 
Error_code Expression::get_token(Token &next)
/* 
 
Post: The Token next records the current_term of the Expression,
      current_term is incremented,
      and an error code of success is returned, or if there is no
      such term a code of fail is returned.
Uses: Class List.
 
*/

{
   if (terms.retrieve(current_term, next) != success) return fail;
   current_term++;
   return success;
}
 
void Expression::put_token(const Token &next)
{
   terms.insert(terms.size(), next);
}
 
void Expression::read()
/* 
Post: A line of text, entered by the user, is split up into
      tokens and stored in the Expression.
Uses: Classes String, Token, and List.
*/
 
{
   String input, word;
   int term_count = 0;
   int x;
   cout << "Enter an infix expression giving a function of x:" 
        << endl;
   input = read_in(cin, x);
   add_spaces(input);                //  Tokens are now words of input.

   bool leading = true;
   for (int i = 0; get_word(input, i, word) != fail; i++) {  
                                     //  Process next token
      if (leading)
         if (word == "+") continue;                   //  unary +
         else if (word == "-") word = "~";            //  unary -

      Token current = word;                      //  Cast word to Token.
      terms.insert(term_count++, current);
      Token_type type = current.kind();
      if (type == leftparen || type == unaryop || type == binaryop)
         leading = true;
      else
         leading = false;
   }
}
 
void Expression::clear()
{
   terms.clear();
   current_term = 0;
}
 
Expression Expression::infix_to_postfix()
{
   Expression answer;
   Token t;
   Stack<Token> s;

   while (get_token(t) != fail) {
      switch (t.kind()) {
      case rightunaryop:
      case operand:
         answer.put_token(t);
         break;

      case leftparen:
         s.push(t);
         break;

      case rightparen:
         s.top(t);
         while (t.kind() != leftparen) {
            answer.put_token(t);
            s.pop();
            s.top(t);
         }
         s.pop();
         break;

      case unaryop:
      case binaryop:
         Token stored;
         bool end_right = false;
         do {
            if (s.empty()) end_right = true;
            else {
               s.top(stored);
               if (stored.kind() == leftparen) end_right = true;
               else if (stored.priority() < t.priority()) end_right = true;
               else if (t.priority() == 6 && stored.priority() == 6)
                  end_right = true;
               else answer.put_token(stored);
               if (!end_right) s.pop();
            }
         } while (!end_right);

         s.push(t);
         break;
      }
   }
   while (!s.empty()) {
      s.top(t);
      answer.put_token(t);
      s.pop();
   }
   answer.put_token(( Token ) (( String ) ";"));
   return answer;
}
 
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 subexpresssion
      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 rightunaryop:
         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;
}
 
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::valid_infix()
/* 
 
Post: A code of success or fail is returned according
      to whether the Expression is a valid or invalid infix sequence.
Uses: Class Token.
 
*/

{
   Token current;
   bool leading = true;
   int paren_count = 0;

   while (get_token(current) != fail) {
      Token_type type = current.kind();
      if (type == rightparen || type == binaryop || type == rightunaryop) {
         if (leading) return fail;
      }
      else if (!leading) return fail;

      if (type == leftparen) paren_count++;
      else if (type == rightparen) {
         paren_count--;
         if (paren_count < 0) return fail;
      }

      if (type == binaryop || type == unaryop || type == leftparen)
         leading = true;
      else leading = false;
   }

   if (leading)  return fail;  //  An expected final operand is missing.
   if (paren_count > 0)  return fail;  //  Right parentheses are missing.
   rewind();
   return success;
}