四則演算の parser を作り，parse tree を指定のフォーマットで出力してちょ．

• 数字，'+'，'-'，'*'，'/'，')'，'(' が使える．
• 負数の扱いは仕様には書いてない．
• Web を使ってもよい．

で，JAVA か C++ を使用してといわれましたが，
数年さわっていないといって，C でごり押ししました(ｗ

で，昔勉強した，コンパイラや，正規表現の記憶を思い出し，なんとかかきました．
400行弱/1日 って，どんな生産性の低さやねん!
自分のへぼさを思い知りました．
あと，負数を扱おうとしたけど，「1*-1」とか難しそうなので，てきとうにごまかしちゃった．
ソース乗っけますので，採点よろぴこ．
結構リファクタリングのしがいがあるソースですが．
実は，木を出力するところの計算に一番頭をつかったという噂も．

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>

#define BUFSIZE     2048
#define INDENT      9
#define INIT_INDENT 6

// the kind of token
typedef enum {
  PLUS = 100, MINUS, MULT, DIV, NUMBER, LPAR, RPAR, EOL,
} tk_kind_t;

// type for token
typedef struct {
  tk_kind_t tkk; // kind of this token
  union {
    int num;
    char op;
  } _u;
} token_t;


// type for node
typedef enum {
  LEAF = 200, INTERNAL,
} node_kind_t;

typedef struct _node {
  token_t tk;
  node_kind_t nkind;
  struct _node *left;
  struct _node *right;
} node_t;


static void get_token(void);
static void syntax_error(token_t t);

static node_t *parse(void);
static node_t *expression(void);
static node_t *term(void);
static node_t *factor(void);

static node_t *make_tree_node(token_t t, node_t *left, node_t *right);
static node_t *make_leaf(token_t t);
static node_t *alloc_node(void);

static void dump_tree(node_t *tree, int indent);
static void free_tree(node_t *tree);

static void dump_token(token_t t);

static token_t cur_token;
static int     cur_ix = 0;
static char    buf[BUFSIZE];

static int min_flag = 0;        /* 先頭の値がマイナスかどうかのフラグ */

////////////////////////////////////////////////////////////////////////////////
// +1*8+3 <-- こんなんは受け付けない。---> syntax error に。
// 1*-1 とかも 受け付けない。---> これは本来ならば、受理されるべき。
// 負の数に関しては、いまいち、仕様がわからないので、
// 中途半端に対応。
// きちんとやろうとすると、get_token() を結構書き直す必要があると思われます。
int main(int argc, char **argv)
{
  node_t *root = NULL;
  printf("input expression OR type C-d to exit.\n");

  while (NULL != (fgets(buf, sizeof(buf), stdin))) {
    root = NULL;
    cur_ix = min_flag = 0;
    
    memset(&cur_token, 0, sizeof(token_t));

    if (NULL == (root = parse())) {
      fprintf(stderr, "parse error\n");
      exit(1);
    }
    /* start printing */
    printf("\n");
    printf(" TOP --->");
    dump_tree(root, INIT_INDENT);
    printf("================================================================================\n");
    free_tree(root);
  }
  return 0;
}


////////////////////////////////////////////////////////////////////////////////
static void get_token(void)
{
  int c, i;

  c = buf[cur_ix++];
  while (isspace(c)) {
    c = buf[cur_ix++];
    if (cur_ix >= BUFSIZE) {
      exit(1);
    }
  }

  if (isdigit(c)) {
    for (i = 0; isdigit(c); ) {
      i = i * 10 + (c - '0');   /* オーバーフロー、アンダーフローは未チェック */
      c = buf[cur_ix++];
    }
    cur_ix--;                   /* 1文字先読みしてしまっているので、押し戻す */
    cur_token.tkk = NUMBER;
    if (min_flag) {
      i = -1 * i;
      min_flag = 0;
    }
    cur_token._u.num = i;    
  }
  else {
    switch (c) {
    case '+':
      cur_token.tkk = PLUS;
      cur_token._u.op = '+';
      break;
    case '-':
      cur_token.tkk = MINUS;
      cur_token._u.op = '-';
      break;
    case '*':
      cur_token.tkk = MULT;
      cur_token._u.op = '*';
      break;
    case '/':
      cur_token.tkk = DIV;
      cur_token._u.op = '/';
      break;
    case '(':
      cur_token.tkk = LPAR;
      cur_token._u.op = '(';
      break;
    case ')':
      cur_token.tkk = RPAR;
      cur_token._u.op = ')';
      break;
    case '\0':
      cur_token.tkk = EOL;
      break;
    default:
      fprintf(stderr, "invalid character:%c\n", c);
      exit(1);
      break;
    }
  }
  return;
}


////////////////////////////////////////////////////////////////////////////////
static void syntax_error(token_t t)
{
  fprintf(stderr, "syntax error:\n");
  fprintf(stderr, "    token.tkk = %d\n", t.tkk);
  exit(1);
          
  return;
}

////////////////////////////////////////////////////////////////////////////////
static node_t *parse(void)
{
  node_t *ret = NULL;
  int c, i;

  /* 先頭がマイナスかどうかのチェック */
  for (i = 0, c = buf[i]; isspace(c); c = buf[++i]) {
    if (i >= BUFSIZE) { exit(1); }
  }
  if ('-' == c) {
    min_flag = 1;
    cur_ix = i + 1;             /* '-' の次から読む */
  }
  get_token();
  ret = expression();
  assert(EOL == cur_token.tkk);
  return ret;
}

////////////////////////////////////////////////////////////////////////////////
static node_t *expression(void)
{
  node_t *ret = NULL;
  token_t tmp;

  ret = term();
  while ((PLUS == cur_token.tkk) || (MINUS == cur_token.tkk)) {
    tmp = cur_token;
    get_token();
    ret = make_tree_node(tmp, ret, term());
  }
  return ret;
}

////////////////////////////////////////////////////////////////////////////////
static node_t *term(void)
{
  node_t *ret = NULL;
  token_t tmp;

  ret = factor();
  while ((MULT == cur_token.tkk) || (DIV == cur_token.tkk)) {
    tmp = cur_token;
    get_token();
    ret = make_tree_node(tmp, ret, factor());
  }
  return ret;
}



////////////////////////////////////////////////////////////////////////////////
// factor ::= NUMBER |
//            '(' expression ')';
static node_t *factor(void)
{
  node_t *ret = NULL;
  if (NUMBER == cur_token.tkk) {
    ret = make_leaf(cur_token);
    get_token();
  }
  else if (LPAR == cur_token.tkk) {
    int c, i;

    /* 先頭がマイナスかどうかのチェック */
    for (i = cur_ix, c = buf[i]; isspace(c); c = buf[++i]) {
      if (i >= BUFSIZE) { exit(1); }
    }
    if ('-' == c) {
      min_flag = 1;
      cur_ix = i + 1;             /* '-' の次から読む */
    }    
    get_token();
    ret = expression();
    if (RPAR != cur_token.tkk) {
      syntax_error(cur_token);           /* exit */
    }
    get_token();
  }
  else {
    syntax_error(cur_token);             /* exit */
  }
  return ret;
}

////////////////////////////////////////////////////////////////////////////////
static void dump_tree(node_t *tree, int indent)
{
  int i, id = indent + INDENT;
 
  assert(NULL != tree);

  if (LEAF == tree->nkind) {
    assert(NUMBER == tree->tk.tkk);
    dump_token(tree->tk);
  }
  else if (INTERNAL == tree->nkind ) {
    dump_token(tree->tk);
    printf("--->");
    dump_tree(tree->left, id);
    for (i = 0; i < id; ++i) {
      printf(" ");
    }
    printf("|\n");
    for (i = 0; i < id; ++i) {
      printf(" ");
    }
    printf("-->");
    dump_tree(tree->right, id);
  }
  return;
}


////////////////////////////////////////////////////////////////////////////////
// for releasing memory allocated for this tree
static void free_tree(node_t *tree)
{
  assert(NULL != tree);
  if (tree->nkind == LEAF) {
    return;                     /* will be released by this parent */
  }
  /* this is internal node */
  /* firstly, handle the left subtree */
  if (tree->left->nkind == LEAF) {
    free(tree->left);
  }
  else {
    free_tree(tree->left);
  }
  /* then, go to the right subtree */
  if (tree->right->nkind == LEAF) {
    free(tree->right);
  }
  else {
    free_tree(tree->right);
  }
  /* at last, free myself */
  free(tree);
  return;
}


////////////////////////////////////////////////////////////////////////////////
static node_t *alloc_node(void)
{
  node_t *ret = NULL;
  if (NULL == (ret = malloc(sizeof(node_t)))) {
    fprintf(stderr, "malloc() failed in alloc_node()\n");
    exit(1);
  }
  return ret;
}


////////////////////////////////////////////////////////////////////////////////
static node_t *make_tree_node(token_t t, node_t *left, node_t *right)
{
  node_t *ret = NULL;

  ret = alloc_node();
  ret->tk = t;
  ret->nkind = INTERNAL;
  ret->left = left;
  ret->right = right;
  return ret;
}

////////////////////////////////////////////////////////////////////////////////
static node_t *make_leaf(token_t t)
{
  node_t *ret = NULL;

  ret = alloc_node();
  ret->tk = t;
  ret->nkind = LEAF;
  ret->left = ret->right = NULL;
  return ret;
}

////////////////////////////////////////////////////////////////////////////////
static void dump_token(token_t t)
{
  switch (t.tkk) {
  case NUMBER:
    printf(" %d \n", t._u.num);
    break;
  case PLUS:
  case MINUS:
  case MULT:
  case DIV:
    printf(" '%c' ", t._u.op);
    break;
/*   case LPAR: */
/*     printf("LPAR: %c\n", t._u.op); */
/*     break; */
/*   case RPAR: */
/*     printf("RPAR: %c\n", t._u.op); */
/*     break; */
  case EOL:
    //printf("EOL reached\n");
    break;
  default:
    fprintf(stderr, "this cannot happen in dump_token()!!\n");
    fprintf(stderr, "tkk=%d\n", t.tkk);
    exit(1);
    break;
  }
  return;
}

11+22*33+44*(77-88) なんて，入力してやると，
以下のように出力されます．

 TOP ---> '+' ---> '+' ---> 11 
                        |
                        --> '*' ---> 22 
                                 |
                                 --> 33 
               |
               --> '*' ---> 44 
                        |
                        --> '-' ---> 77 
                                 |
                                 --> 88 

※2007/04/28，一部修正．