post.cpp

数据结构与程序设计教材源码 数据结构与程序设计教材源码

 
Value get_value(const Token &t)
{
   Value answer = 0;
   char *p = (char *) t.value;
   if (p == NULL) return answer;
   while (*p != 0) answer = 10 * answer + *(p++) - '0';
   return answer;
}
 
Value do_binary(const Token &t, const Value &x, const Value &y)
{
   switch (t.value[0]) {
   case '+': return x + y;
   case '-': return x - y;
   case '*': return x * y;
   case '/': return x / y;
   case '%': return x % y;
   }
   return x;
}
 
Value do_unary(const Token &t, const Value &x)
{
   if (t.value[0] == '-') return -x;
   return x;
}
 
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 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;
}
 
Token::Token()
{
   value[0] = '\0';
}
 
void Token::clear()
{
   value[0] = '\0';
}
 
Token::~Token()
{
   value[0] = '\0';
}
 
Token_type Token::kind()
{
   if (value[0] == '\0') return end_expression;
   if ('0' <= value[0] && value[0] <= '9') return operand;
   if (value[0] == '-' && value[1] != 0) return operand;
   if (value[0] == '~') return unaryop;
   if (value[0] == '+') return binaryop;
   if (value[0] == '-') return binaryop;
   if (value[0] == '*') return binaryop;
   if (value[0] == '/') return binaryop;
   if (value[0] == '%') return binaryop;
   else return end_expression;
}
 
Error_code Expression::get_token(Token &result) {
   result.clear();
   if (value[0] == '\0') return fail;
   while (start < count) {
      char c = value[start];
      if ('0' <= c && c <= '9') {
         int i = 0;
         char *p = (char *) result.value;
         p[i] = c;
         while ('0' <= (c = value[++start]) && c <= '9')
            if (i < 18) p[++i] = c;
         if (i < 19) p[++i] = '\0';
         else p[19] = '\0';
         return success;
      }
      else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '~' || c == ';') {
         start++;
         char *p = (char *) result.value;
         p[0] = c; p[1] = '\0';
         return success;
      }
      else start++;
   }
   return fail;
}
 
void Expression::read() {
   clear();
   while (1) {
      char c;
      c = value[count++] = cin.get();
      if (c == ';') break;
   }
   value[count] = '\0';
}