OOC:en:3.9 Infix Output

来自 ChinaUnix Wiki

Perhaps the highlight of processing arithmetic expressions is to print them with a minimal number of parentheses. This is usually a bit tricky, depending on who is responsible for emitting the parentheses. In addition to the operator name used for postfix output we add two numbers to the struct Type:

   struct Type { 
       const char * name; /* node’s name */ 
       char rank, rpar; 
       void * (* new) (va_list ap); 
       void (* exec) (const void * tree, int rank, int par); 
       void (* delete) (void * tree); 
   }; 

.rank is the precedence of the operator, starting with 1 for addition. .rpar is set for operators such as subtraction, which require their right operand to be enclosed in parentheses if it uses an operator of equal precedence. As an example consider

   $ infix 
   1+(2 — 3) 
       1+2—3 
   1 — (2 — 3) 
       1 — (2 — 3) 

This demonstrates that we have the following initialization:

   static struct Type _Add = {"+", 1, 0, mkBin, doBin, freeBin}; 
   static struct Type _Sub = {"—", 1, 1, mkBin, doBin, freeBin}; 

The tricky part is for a binary node to decide if it must surround itself with parentheses. A binary node such as an addition is given the precedence of its superior and a flag indicating whether parentheses are needed in the case of equal precedence. doBin() decides if it will use parentheses:

   static void doBin (const void * tree, int rank, int par) 
   { const struct Type * type = * (struct Type **) tree; 
     par = type —> rank < rank 
             || (par && type —> rank == rank); 
     if (par) putchar(’(’); 

If our node has less precedence than its superior, or if we are asked to put up parentheses on equal precedence, we print parentheses. In any case, if our description has .rpar set, we require only of our right operand that it put up extra parentheses:

       exec(((struct Bin *) tree) —> left, type —> rank, 0); 
       printf(" %s ", type —> name); 
       exec(((struct Bin *) tree) —> right, 
               type —> rank, type —> rpar); 
       if (par) putchar(’)’); 
   } 

The remaining printing routines are significantly simpler to write.