xxxasdfghjk999のブログ

iroiro

2分木を利用したコンソールで動く電卓

備忘録プログラミング

前回の続きで、電卓が完成しました！

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.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;

node* setup_node()
{
  node* p;
  p = (node*)malloc(sizeof(struct tree_tag));
  p->right = NULL;
  p->left = NULL;
  return p;
}
char enzns1[8] ="+-";
char enzns2[8] ="*/^";
void ExpansionNode(node *p)
{
  int i=0,j,k=0,flag=-1;
  blacket_cut(p->formula);
  //項に分割
  for(i=0;i<strlen(p->formula);i++){
    if(p->formula[i] == '('){
      k++;
      flag=i;
    }else if(p->formula[i] ==')'){
      k--;
    }
    if(k==0)
      flag = -1;
    if(flag ==  -1 && strchr(enzns1,p->formula[i])){
          p->id = p->formula[i];
          p->t=symbol;
          k=0;
          j = i;
          if(p->id == '-')
            for(;p->formula[i];i++){
              if(p->formula[i] == '('){
                k++;
              }else if(p->formula[i] == ')')
                k--;
              if(k!=0)
                continue;
              if(p->formula[i] == '+')
                p->formula[i] = '-';
              else if(p->formula[i] == '-')
                p->formula[i] = '+';
            }
          node *right,*left;
          right = setup_node();
          left = setup_node();
          p->right = right;
          p->left = left;
          strcpy(right->formula,&p->formula[j+1]);
          p->formula[j] = '\0';
          strcpy(left->formula,p->formula);
          ExpansionNode(p->right);
          ExpansionNode(p->left);
          return;
    }

  }
  //初めの括弧で分割
  i=0;
  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];
    j = i;
    i++;
    if(p->id == '-')
      for(;p->formula[i];i++){
         if(p->formula[i] == '('){
             k++;
         }else if(p->formula[i] == ')')
             k--;
        if(k!=0)
          continue;
         if(p->formula[i] == '+')
          p->formula[i] = '-';
         else if(p->formula[i] == '-')
          p->formula[i] = '+';
            }
    node *right,*left;
    right = setup_node();
    left = setup_node();
    p->right = right;
    p->left = left;
    strcpy(right->formula,&(p->formula[j+2]));
    p->formula[j+1] = '\0';
    strcpy(left->formula,p->formula);
    ExpansionNode(p->right);
    ExpansionNode(p->left);
    return;
  }else{
    //初め以外の括弧で分割
    for(i=0;i<strlen(p->formula);i++)
      if(p->formula[i] == '('){
        p->t = symbol;
        p->id = p->formula[i-1];
        j = i;
        if(p->id == '-')
          for(;p->formula[i];i++){
            if(p->formula[i] == '('){
              k++;
            }else if(p->formula[i] == ')')
              k--;
            if(k!=0)
              continue;
            if(p->formula[i] == '+')
              p->formula[i] = '-';
            else if(p->formula[i] == '-')
              p->formula[i] = '+';
          }
        node *right,*left;
        right = setup_node();
        left = setup_node();
        p->right = right;
        p->left = left;
        strcpy(right->formula,&p->formula[j]);
        p->formula[j-1] = '\0';
        strcpy(left->formula,p->formula);
        ExpansionNode(p->right);
        ExpansionNode(p->left);
        return;
      }
    //優先順位1の演算子で分割
    for(i=0;i<strlen(p->formula);i++)
      if(strchr(enzns1,p->formula[i])){
        p->t = symbol;
        p->id = p->formula[i];
        j = i;

        if(p->id == '-')
          for(;p->formula[i];i++){
            if(p->formula[i] == '+')
              p->formula[i] = '-';
            else if(p->formula[i] == '-')
              p->formula[i] = '+';
          }

        node *right,*left;
        right = setup_node();
        left = setup_node();
        p->right = right;
        p->left = left;
        strcpy(right->formula,&p->formula[j+1]);
        p->formula[j] = '\0';
        strcpy(left->formula,p->formula);
        ExpansionNode(p->right);
        ExpansionNode(p->left);
        return;
      }
    //優先順位2の演算子で分割
      for(i=0;i<strlen(p->formula);i++)
        if(strchr(enzns2,p->formula[i])){
          p->t = symbol;
          p->id = p->formula[i];
          node *right,*left;
          right = setup_node();
          left = setup_node();
          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;
        }
      if(p->formula[0]){
        //演算子、括弧が存在しないとき
        p->t = value;
        p->id = atoi(p->formula);
        return;
      }else{
        //formulaが空のとき(単項演算子に対する処理)
        p->t = value;
        p->id = 0;
        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)
{
  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(")");

}

int calc(node *p)
{
  switch(p->t){
  case value:
    return p->id;
    break;
  case symbol:
    switch(p->id){
    case '+':
      return calc(p->left)+calc(p->right);
      break;
    case '-':
      return calc(p->left)-calc(p->right);
      break;
    case '*':
      return calc(p->left)*calc(p->right);
      break;
    case '/':
      if(calc(p->right)==0){
        fprintf(stderr,"error : divided by zero\n");
        exit(1);
      }
      return calc(p->left)/calc(p->right);
      break;
    case '^':
      return (int)pow((double)calc(p->left),(double)calc(p->right));
      break;
    }
    break;
  }

}

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");
  printf("result = %d",calc(&root));

}

実行例

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

めちゃくちゃ長いコードになってしまいました...
規模の大きいプログラム開発には慣れておらず、分岐に似たような記述がつらなっています＠＠
前回との差異を見ていきます
まず、ノードの初期化の部分をサブルーチン化しました

node* setup_node()
{
  node* p;
  p = (node*)malloc(sizeof(struct tree_tag));
  p->right = NULL;
  p->left = NULL;
  return p;
}

ここは同じような記述がたくさんあったので、サブルーチン化するとだいぶすっきりしました

あと目玉の計算部分です

int calc(node *p)
{
  switch(p->t){
  case value:
    return p->id;
    break;
  case symbol:
    switch(p->id){
    case '+':
      return calc(p->left)+calc(p->right);
      break;
    case '-':
      return calc(p->left)-calc(p->right);
      break;
    case '*':
      return calc(p->left)*calc(p->right);
      break;
    case '/':
      if(calc(p->right)==0){
        fprintf(stderr,"error : divided by zero\n");
        exit(1);
      }
      return calc(p->left)/calc(p->right);
      break;
    case '^':
      return (int)pow((double)calc(p->left),(double)calc(p->right));
      break;
    }
    break;
  }

}

この部分は二分木の分割がきちんとできていればそんなに難しいコードも必要なく、シンプルにできました。
関数ポインタで実装しようと思っていましたが、面倒なのでやめました...
C言語備え付けの+-/*を使っています
べき乗はmath.hのpowを使いました

さらに演算子を優先順位で分けてenzns1とenzsn2に分割しました
しかし、マイナスの符号で分割する際に、例えば66-66+66といった式を-で分割する
際、コードの性質上、(66)-(66+66)と計算されることになってしまいます。
これを解消するために、やや強引ですがマイナスのシンボルを検出したときは、その符号の後ろのプラスとマイナスをすべて反転させるようにしました（括弧の中を除く）。苦し紛れですが、きっちり機能しました。
その他括弧の処理などを少しいじり、無事電卓は完成しました
自己参照ポインタの部分に式を代入したりして再帰呼び出しする部分は一つにまとめることができそうなのですが、goto文を使うぐらいしか実現の方法が思いつかず、結局すべての分岐に同じようなことを書いています

構文解析ってのは大変ですね