计算表达式

＃i nclude
＃i nclude
typedef double elemType;
＃i nclude "LinkAccess.c"

/* 计算由str所指向字符串的后缀表达式（逆波兰式）的值 */
double compute(char *str)
{
 struct sNode *s;  /* 用s栈存储操作数和中间计算结果，元素类型为double */
 double x, y;   /* x, y用于保存浮点数 */
 int i = 0;    /* i用于扫描后缀表达式 */
 typedef double elemType;
 initStack(&s);
 /* 扫描后缀表达式中的每个字符，并进行相应处理 */
 while(str[i]){
     if(str[i] == ' '){   /* 扫描到空格字符不做任何处理 */
         i++;
   continue;
     }
  switch(str[i]){
      case '+':
    x = pop(&s) + pop(&s);
    i++;
    break;
   case '-':
    x = pop(&s);  /* 弹出减数 */
    x = pop(&s) - x;
       i++;
    break;
   case '*':
    x = pop(&s) * pop(&s);
    i++;
    break;
   case '/':
    x= pop(&s);  /* 弹出除数 */
    if(x != 0.0){
        x = pop(&s) / x;
    }else{
        printf("除数为0！\n");
     exit(1);
    }
    i++;
    break;
   default:  /* 扫描到的是浮点数字符串，生成对应的浮点数 */
    x = 0;  /* x保存扫描到的整数部分的值 */
    while(str[i] >= 48 && str[i] <= 57){
        x = x * 10 + str[i] - 48;
     i++;
    }
    if(str[i] == '.'){
        double j = 10.0;  /* j作为相应小数位的权值 */
     i++;
     y = 0;
     while(str[i] >= 48 && str[i] <= 57){
         y = y + (str[i] - 48) / j;
      i++;
      j *= 10;
     }
     x += y;  /* 把小数部分合并到整数部分x中 */
    }
  }
  push(&s, x);  /* 把扫描转换后或进行相应运算后得到的浮点数压入栈s中 */
 }
 /* 若计算结束后栈为空则中止运算 */
 if(emptyStack(&s)){
     printf("后缀表达式错误！\n");
  exit(1);
 }
 /* 若栈中只有一个元素，则它就是该后缀表达式的值，否则出错 */
 x = pop(&s);
 if(emptyStack(&s)){
     return x;
 }else{
     printf("后缀表达式错误！\n");
  exit(1);
 }
}

/* 返回运算符op所对应的优先级数值 */
int precedence(char op)
{
 switch(op){
     case '+':
  case '-':
   return 1;
  case '*':
  case '/':
   return 2;
  case '(':
  case :
  default:
   return 0;
 }
}

/* 将s1所指向的中缀表达式转换为s2所指向的后缀表达式 */
char *change(char *s1, char *s2)
{
 struct sNode *r;  /* 栈r用于暂存运算符 */
 int i = 0, j = 0;  /* i, j分别用于扫描s1和指示s2串中相应字符的位置 */
 char ch;    /* ch用于暂存扫描s1得到的字符 */
 typedef char elemType;
 initStack(&r);
 push(&r, );   /* 给栈底放入字符，它具有最低的优先级0 */
 ch = s1[i];    /* ch初值为s1中的第一个字符 */
 /* 依次处理中缀表达式中的每个字符 */
 while(ch != '\0'){
  if(ch == ' '){    /* 扫描到空格字符不做任何处理 */
      ch = s1[++i];
  }else if(ch == '('){  /* 对于左括号直接进栈 */
      push(&r, ch);
   ch = s1[++i];
  }else if(ch == ')'){/* 对于右括号，使括号内的仍停留在栈中的运算符依次出栈并写入到s2中 */
      while(peek(&r) != '('){
          s2[j++] = pop(&r);
      }
   pop(&r);  /* 删除栈顶的左括号 */
   ch = s1[++i];
  }else if(ch == '+' || ch == '-' || ch == '*' || ch == '/'){
  /* 对于四则运行符，使暂存在栈顶的不低于ch优先级的运行符依次出栈并写入到s2中 */
   char w = peek(&r);
   while(precedence(w) >= precedence(ch)){
       s2[j++] = w;
    pop(&r);
    w = peek(&r);
   }
   push(&r, ch);
   ch = s1[++i];
   s2[j++] = ' ';/* 把放入s2中的每个运算符后面接着放入一个空格字符 */
  }else{  /* 此处必然为数字或小数点，否则中缀表达式错误 */
      if((ch < '0' || ch > '9') && ch != '.'){
          printf("中缀表达式错误！\n");
    exit(1);
      }
   /* 把一个数值中的每一位依次写入到s2串中 */
   while((ch >= '0' && ch <= '9') || ch == '.'){
    s2[j++] = ch;
    ch = s1[++i];
   }
   s2[j++] = ' ';/* 把放入s2中的每个数值后面接着放入一个空格字符 */
  }
 }
 /* 把存在栈中的运算符依次退栈并写入到s2串中 */
 ch = pop(&r);  
 while(ch != ){
     if(ch == '('){
   printf("表达式错误！\n");
   exit(1);
     }else{
         s2[j] = ch;
   ch = pop(&r);
     }
 }
 s2[j++] = '\0';  /* 在后缀表达式的末尾放入字符串结束符 */
 return s2;
}

int main(int argc, char* argv[])
{
 char *a = "((12 + 34 + 5 / 2) * 2)";
 char *b = "";
 printf("%s\n", a);
 b = change(a, b);
 printf("%s\n", b);
 printf("%f\n", compute(b));
 system("pause");
 return 0;
}