polish.cpp

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

int Token::priority()
{

   if (kind() == operand) return -1;
   if (kind() == leftparen) return -1;
   if (kind() == rightparen) return -1;
   if (kind() == end_expression) return -1;
   switch (value[0]) {
   case '+': return 4;
   case '-': return 4;
   case '*': return 5;
   case '/': return 5;
   case '%': return 5;
   case '~': return 6;
   }
   return -1;
}
 
Value get_value(Token &t)
{
   Value answer = 0;
   char *p = t.value;
   while (*p != 0) answer = 10 * answer + *(p++) - '0';
   return answer;
}
 
Value do_binary(Token &t, Value &x, 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(Token &t, Value &x)
{
   if (t.value[0] == '-') return -x;
   return x;
}
 
#include "../../4/NODES/NODE.CPP"
#include "../../4/LINKSTAC/STACK.CPP"
 
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;
}
 
Error_code Expression::recursive_evaluate(Value &result, Token &final)
{
   while (true) {
      if (get_token(final) == fail) return fail;
      switch (final.kind()) {
      case binaryop:
      case end_expression:
         return success;

      case rightunaryop:
      case unaryop:
         result = do_unary(final, result);
         break;

      case operand:
         Value second_arg = get_value(final);
         if (recursive_evaluate(second_arg, final) == fail) return fail;
         if (final.kind() != binaryop) return fail;
         result = do_binary(final, result, second_arg);
         break;
      }
   }
}
 

Error_code Expression::evaluate_postfix(Value &result)
{
   Token t;
   Error_code outcome;
   if (get_token(t) == fail || t.kind() != operand) outcome = fail;
   else {
      result = get_value(t);
      outcome = recursive_evaluate(result, t);
      if (outcome == success && t.kind() != end_expression)
         outcome = fail;
   }
   return outcome;
}
 
Error_code Expression::evaluate_prefix(Value &result)
{
   Token t;
   Value x, y;
   if (get_token(t) == fail) return fail;
   switch (t.kind()) {
   case unaryop:
      if (evaluate_prefix(x) == fail) return fail;
      else result = do_unary(t, x);
      break;

   case binaryop:
      if (evaluate_prefix(x) == fail) return fail;
      if (evaluate_prefix(y) == fail) return fail;
      else result = do_binary(t, x, y);
      break;

   case operand:
      result = get_value(t);
      break;
   }
   return success;
}
 
Token_type Token::kind()
{
   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;
   if (value[0] == '(') return leftparen;
   if (value[0] == ')') return rightparen;
   else return end_expression;
}
 
void Expression::put_token(char *result) {
   strcat(value, result);
   strcat(value, " ");
   count += 1 + strlen(result);
}
 
void Expression::put_token(Token &result) {
   strcat(value, result.value);
   strcat(value, " ");
   count += 1 + strlen(result.value);
}
 
Error_code Expression::get_token(Token &result) {
   while (start < count) {
      char c = value[start];
      if ('0' <= c && c <= '9') {
         int i = 0;
         char *p = 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 == ';' || c == '(' || c == ')') {
         start++;
         char *p = 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';
}