expr.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;
   }
}
 
Value do_unary(const Token &t, const Value &x)
{
   return -x;
}
 
#include "../../5/NODES/NODE.CPP"
#include "../../5/LINKSTAC/STACK.CPP"
 
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_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;
}
 
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';
}