二分木を利用した構文解析

二分木が熱い！
数式の構文解析をするための二分木構造をつくってみました
まだ書きかけですが...

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

void blacket_cut(char[]);
enum type{value,symbol};
typedef struct tree_tag{
  struct tree_tag *right;
  struct tree_tag *left;
  enum type t;
  int id;
  char formula[80];
}node;
char enzns[8] ="+-*/^";
void ExpansionNode(node *p)
{
  int i=0,j,k;
  blacket_cut(p->formula);
  if(p->formula[0] == '('){
    k=1;
    while(k!=0){
      i++;
      if(p->formula[i] == '(')
        k++;
      else if(p->formula[i] == ')')
        k--;
    }
    p->t=symbol;
    p->id = p->formula[i+1];
    node *right,*left;
    right = (node*)malloc(sizeof(struct tree_tag));
    right->right = NULL;
    right->left = NULL;
    left = (node*)malloc(sizeof(struct tree_tag));
    left->right = NULL;
    left->left = NULL;
    p->right = right;
    p->left = left;
    strcpy(right->formula,&(p->formula[i+2]));
    p->formula[i+1] = '\0';
    strcpy(left->formula,p->formula);
    ExpansionNode(p->right);
    ExpansionNode(p->left);
    return;
  }else{
    for(i=0;i<strlen(p->formula);i++){
      if(strchr(enzns,p->formula[i])){
        p->t = symbol;
        p->id = p->formula[i];
        p->t=symbol;
        node *right,*left;
        right = (node*)malloc(sizeof(struct tree_tag));
        right->right = NULL;
        right->left = NULL;
        left = (node*)malloc(sizeof(struct tree_tag));
        left->right = NULL;
        left->left = NULL;
        p->right = right;
        p->left = left;
        strcpy(right->formula,&p->formula[i+1]);
        p->formula[i] = '\0';
        strcpy(left->formula,p->formula);
        ExpansionNode(p->right);
        ExpansionNode(p->left);
        return;
    }

  }
    p->t = value;
    p->id = atoi(p->formula);
    return;
  }
}
void simplize(char shiki[])
{
  int i,k,len=strlen(shiki);
  for(i=0;i<len;i++)
    if(shiki[i] == ' '){
      for(k=i;shiki[k+1];k++)
        shiki[k] = shiki[k+1];
      shiki[k] = '\0';
      i--;
    }
  blacket_cut(shiki);
}

void blacket_cut(char shiki[])
{
  if(shiki[0] == '(' && shiki[strlen(shiki)-1] == ')'){
    int i,k=1;
    for(i=1;i<strlen(shiki);i++){
      if(shiki[i] == '(')
        k++;
      else if(shiki[i] == ')')
        k--;
      if(k==0)
        break;
    }
    if(i == (strlen(shiki) -1)){
    shiki[strlen(shiki)-1] = '\0';
    for(i=0;shiki[i+1];i++)
      shiki[i] = shiki[i+1];
    shiki[i] = '\0';
    blacket_cut(shiki);
    }
  }else
    return;
  return;
}

void tansaku(node *p)
{
  if(p->left != NULL)
    tansaku(p->left);
  switch(p->t){
  case symbol:
    printf("%c",p->id);
    break;
  case value:
    printf("%d",p->id);
    break;
  }
  if(p->right != NULL)
    tansaku(p->right);

}

int main()
{
  char shiki[256];
  fgets(shiki,256,stdin);
  shiki[strlen(shiki)-1] = '\0';
  simplize(shiki);
  node root;
  strcpy(root.formula,shiki);
  printf("通りがけ走査 : ");
  ExpansionNode(&root);
  tansaku(&root);
  printf("\n");

}

実行結果

((66*7+99/7)*(66+22-4+0))
通りがけ走査 : 66*7+99/7*66+22-4+0

かなり行き当たりばったりで作っているのでサブルーチン化できそうな改善点がたくさんあります^^;
標準入力から数式を持ってきて、simplizeという関数でスペースをすべて詰めています。
その数式を構造体ノードのformulaに突っ込んでExpansionNodeを実行。
括弧を削るためのblaket_cutなどを用いながらExpansionNodeを再帰的に実行して葉の部分に数値が集まります。
作られた木に対して、通りがけ走査を実施し、それぞれの要素を印字していきます。
なんの工夫もなく走査しているので、実行結果をみてみると、入力された結果に対して括弧がぬけています。
そこで走査の部分をこのように改変してみました

void tansaku(node *p)
{
  printf("(");
  if(p->left != NULL)
    tansaku(p->left);
  switch(p->t){
  case symbol:
    printf("%c",p->id);
    break;
  case value:
    printf("%d",p->id);
    break;
  }
  if(p->right != NULL)
    tansaku(p->right);
  printf(")");

}

実行結果

((66*7+99/7)*(66+22-4+0))
通りがけ走査 : (((66)*((7)+((99)/(7))))*((66)+((22)-((4)+(0)))))

ｳｰﾝ括弧をつけた部分は演算順序が守られているけど、それ以外はめちゃくちゃになってしまっています
演算の優先順位についても考慮する必要がありそうです
これを利用してコンソール上で動く電卓のようなものを作ろうと思っています