// algo3-6.cpp 表達式求值（輸入、輸出和中間結果均只能是0～9）
 typedef char SElemType;
 #include"c1.h"
 #include"c3-1.h"
 #include"bo3-1.cpp"

 SElemType Precede(SElemType t1,SElemType t2)
 { // 根據教科書表3.1，判斷兩符號的優先關系
   SElemType f;
   switch(t2)
   {
     case '+':
     case '-':if(t1=='('||t1=='#')
                f='<';
              else
                f='>';
              break;
     case '*':
     case '/':if(t1=='*'||t1=='/'||t1==')')
                f='>';
              else
                f='<';
              break;
     case '(':if(t1==')')
              {
                printf("ERROR1\n");
                exit(ERROR);
              }
              else
                f='<';
              break;
     case ')':switch(t1)
              {
		case '(':f='=';
			 break;
		case '#':printf("ERROR2\n");
			 exit(ERROR);
		default: f='>';
	      }
	      break;
     case '#':switch(t1)
	      {
		case '#':f='=';
			 break;
		case '(':printf("ERROR3\n");
			 exit(ERROR);
		default: f='>';
              }
   }
   return f;
 }

 Status In(SElemType c)
 { // 判斷c是否為運算符
   switch(c)
   {
     case'+':
     case'-':
     case'*':
     case'/':
     case'(':
     case')':
     case'#':return TRUE;
     default:return FALSE;
   }
 }

 SElemType Operate(SElemType a,SElemType theta,SElemType b)
 {
   SElemType c;
   a=a-48;
   b=b-48;
   switch(theta)
   {
     case'+':c=a+b+48;
             break;
     case'-':c=a-b+48;
             break;
     case'*':c=a*b+48;
             break;
     case'/':c=a/b+48;
   }
   return c;
 }

 SElemType EvaluateExpression() // 算法3.4
 { // 算術表達式求值的算符優先算法。設OPTR和OPND分別為運算符棧和運算數棧
   SqStack OPTR,OPND;
   SElemType a,b,c,x,theta;
   InitStack(OPTR);
   Push(OPTR,'#');
   InitStack(OPND);
   c=getchar();
   GetTop(OPTR,x);
   while(c!='#'||x!='#')
   {
     if(In(c)) // 是7種運算符之一
       switch(Precede(x,c))
       {
         case'<':Push(OPTR,c); // 棧頂元素優先權低
                 c=getchar();
                 break;
         case'=':Pop(OPTR,x); // 脫括號并接收下一字符
                 c=getchar();
                 break;
         case'>':Pop(OPTR,theta); // 退棧并將運算結果入棧
		 Pop(OPND,b);
                 Pop(OPND,a);
                 Push(OPND,Operate(a,theta,b));
                 break;
       }
     else if(c>='0'&&c<='9') // c是操作數
     {
       Push(OPND,c);
       c=getchar();
     }
     else // c是非法字符
     {
       printf("ERROR4\n");
       exit(ERROR);
     }
     GetTop(OPTR,x);
   }
   GetTop(OPND,x);
   return x;
 }

 void main()
 {
   printf("請輸入算術表達式（中間值及最終結果要在0～9之間），并以#結束\n");
   printf("%c\n",EvaluateExpression());
 }