//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :3  (3_2)                   *
//*PROGRAM          :表達式求值                 *
//*CONTENT          :堆棧的應用                 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <conio.h>
#define MAX 10       //定義堆棧最大容量
void push_opnd(char);//操作數堆棧入棧操作
float pop_opnd();    //操作數堆棧出棧操作
void push_optr(char);//操作符堆棧入棧操作
char pop_optr();     //操作符堆棧出棧操作
char relation(char,char);//比較兩個操作符的優先級
float operate(float,char,float);//運算
float opnd[MAX];      //操作數堆棧
char optr[MAX];       //操作符堆棧
int topd=0;           //棧頂指針初始化
int top=0;
char symb[30];        //表達式字符串
void main()
{int i=0;
 char sy;
 float a,b;
// textbackground(3);   //設定屏幕顏色
 //textcolor(15);
 //clrscr();
 //---------------------程序解說-----------------------
 printf("本程序實現表達式求值的操作。可以進行加減乘除運算。\n");
 printf("這是堆棧應用的一個例子\n");
 //----------------------------------------------------
 printf("請輸入表達式(以#結束):\n例如: 3*(3+2)/5#\n");
 push_optr('#');
 gets(symb);         //輸入表達式，以#為結束符
 while((symb[i]!='#')||(optr[top]!='#'))
 {if((symb[i]!='+')&&(symb[i]!='-')&&(symb[i]!='*')&&(symb[i]!='/')
	 &&(symb[i]!='(')&&(symb[i]!=')')&&(symb[i]!='#')&&(symb[i]!=' '))
     {push_opnd(symb[i]);i++;}           //如果當前字符不是操作符，則入操作數棧，字符串指針加一
  else  switch(relation(optr[top],symb[i]))  //若是操作符，比較其和操作符棧的棧頂元素的優先級
	   {case '<':push_optr(symb[i]);i++;break;  //若棧頂元素優先級低，則當前字符入棧，指針加一
	    case '=':sy=pop_optr();i++; break;      //若優先級相等，必為兩個配對的括號，退棧，指針加一
	    case '>':sy=pop_optr();b=pop_opnd();    //若優先級高，則棧頂元素退棧，進行運算
		     a=pop_opnd();
		     topd=topd+1;
		     opnd[topd]=operate(a,sy,b);     //把運算結果入棧
		     break;
	    case ' ':printf("語法錯誤!\n");exit(0);
	   }
  }
  printf("運算結果=%1.2f\n",opnd[topd]);
  printf("程序結束，按任意鍵退出!\n");
  getch();
}
void push_opnd(char ch)
{int ch_i;
 ch_i=ch-'0';   //把字符換算成數字，并入操作數棧
 topd++;
 opnd[topd]=ch_i;
}
float pop_opnd() 
{//操作數棧出棧
topd=topd-1;
 return opnd[topd+1];
}
void push_optr(char ch)
{//操作符入棧
 top++;
 optr[top]=ch;
}
char pop_optr()  
{//操作數出棧
 top--;
 return optr[top+1];
}
char relation(char sym1,char sym2)  
{//比較兩個操作符的優先級
 int i;
 char chl[2];
 int ind[2];
 char re[7][7]={'>','>','<','<','<','>','>',
		'>','>','<','<','<','>','>',
		'>','>','>','>','<','>','>',
		'>','>','>','>','<','>','>',
		'<','<','<','<','<','=',' ',
		'>','>','>','>',' ','>','>',
		'<','<','<','<','<',' ','='};
 chl[0]=sym1;
 chl[1]=sym2;
 for(i=0;i<=1;i++)
    {switch(chl[i])
      {case '+':ind[i]=0;break;
       case '-':ind[i]=1;break;
       case '*':ind[i]=2;break;
       case '/':ind[i]=3;break;
       case '(':ind[i]=4;break;
       case ')':ind[i]=5;break;
       case '#':ind[i]=6;break;
       default:printf("Error!\n");return('0');
      }
    }
 return(re[ind[0]][ind[1]]);
}
float operate(float a,char sym,float b)  
{//進行運算
 float re;
 switch(sym)
    {case '+':re=a+b;break;
     case '-':re=a-b;break;
     case '*':re=a*b;break;
     case '/':re=a/b;break;
     default:printf("Error!\n");return(0);
    }
 return re;
}