POJ 1400 - Complicated Expressions

http://poj.org/problem?id=1400

概要

括弧と四則演算からなる式が与えられるので，それをできるだけ括弧が少ない形にして出力する．

• すべての二項演算子は左結合．つまり，(a-b)-c は a-b-c に変換する
• 優先順位は () が最も高く，次に * と /，最後に + と - である．
• * と + に関しては結合則を満たすとする．つまり，a+(b+c) は a+b+c に変換する
• その他の法則を使ってはならない．例えば a-(b-c) を a-b+c に変換してはならない

制約

• 式は250文字以下
• 入力中に空白は存在しない

解法

LL(1) で構文解析して，いわゆるプリティプリンタを実装すればいい．

時間制限が厳しいと思う… 出力するときに string を繋げていくのはもちろんダメで， ノード用のメモリを実行時に malloc で確保するのもダメだった．

出力はその都度行い，ノード用のメモリはグローバルに用意しておいて free list の要領で割り当てていくようにした…

  1 #include <stdio.h>
  2 
  3 typedef struct expr_tag
  4 {
  5   char v;
  6   struct expr_tag *lhs, *rhs;
  7 } expr;
  8 
  9 static expr store[300];
 10 expr *freelist;
 11 
 12 expr *var(char c)
 13 {
 14   expr *e = freelist++;
 15   e->v = c;
 16   e->lhs = e->rhs = NULL;
 17   return e;
 18 }
 19 
 20 expr *binop(char op, expr *l, expr *r)
 21 {
 22   expr *e = freelist++;
 23   e->v = op;
 24   e->lhs = l;
 25   e->rhs = r;
 26   return e;
 27 }
 28 
 29 void ppr(expr *e, int level)
 30 {
 31   if (!e->lhs) {
 32     putchar(e->v);
 33   } else {
 34     int llv, rlv;
 35     switch (e->v) {
 36       case '*':
 37         llv = rlv = 4;  break;
 38       case '/':
 39         llv = 4;  rlv = 5;  break;
 40       case '+':
 41         llv = rlv = 1;  break;
 42       case '-':
 43         llv = 1;  rlv = 2;  break;
 44     }
 45 
 46     if (level > llv) {
 47       putchar('(');
 48     }
 49     ppr(e->lhs, llv);
 50     putchar(e->v);
 51     ppr(e->rhs, rlv);
 52     if (level > llv) {
 53       putchar(')');
 54     }
 55   }
 56 }
 57 
 58 expr *parse_expr();
 59 expr *parse_factor()
 60 {
 61   const char c = getchar();
 62   if (c == '(') {
 63     expr *e = parse_expr();
 64     (void)getchar();
 65     return e;
 66   } else {
 67     expr *e = var(c);
 68     return e;
 69   }
 70 }
 71 
 72 expr *parse_term()
 73 {
 74   expr *l = parse_factor();
 75   char c = getchar();
 76   while (c != '\n' && (c == '*' || c == '/')) {
 77     expr *r = parse_factor();
 78     l = binop(c, l, r);
 79     c = getchar();
 80   }
 81   ungetc(c, stdin);
 82   return l;
 83 }
 84 
 85 expr *parse_expr()
 86 {
 87   expr *l = parse_term();
 88   char c = getchar();
 89   while (c != '\n' && (c == '+' || c == '-')) {
 90     expr *r = parse_term();
 91     l = binop(c, l, r);
 92     c = getchar();
 93   }
 94   ungetc(c, stdin);
 95   return l;
 96 }
 97 
 98 int main()
 99 {
100   int N;
101   scanf("%d", &N);
102   (void)getchar();
103   while (N-- > 0) {
104     freelist = store;
105     expr *e = parse_expr();
106     ppr(e, 0);
107     (void)getchar();
108     putchar('\n');
109   }
110   return 0;
111 }