基于c语言的数据结构之栈应用（二）四则运算表达式的应用

issue：测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。假设没有非法表达式。当一行只有0输入结束，相应的结果不要输出。（2006年浙江大学软件工程研究生机试题）

/**
算法概述：
1，设立两个堆栈，一个用来保存运算符，另一个用来保存数字
2，在表达式首尾添加标记运算符，该运算符的优先级最低
3，从左至右依次遍历字符串，遍历运算符，将于运算符栈栈顶元素进行比较，若运算符栈顶运算符优先级小于该运算符或者此时运算符栈为空
则将该运算符压入栈中。遍历字符串中的下一个元素。
4，若运算符栈顶运算符优先级大于该运算符，则弹出该栈顶运算符，再从数字栈中一次弹出两个栈顶数字，完成弹出的运算符对应的运算得到
结果后，再将该结果压入数字栈中，重复比较栈顶运算符与当前遍历到的运算符优先级，重复步骤
5，若遍历到数字则直接压入数字栈。
6，若运算符堆栈中仅存有两个运算符且栈顶元素为我们人为添加的标记运算符，那么表达式运算结束，此时数字栈中唯一的数字即为表达式的值。
*/
#include<stdio.h>
#include<stack>
using namespace std;
char str[220];//保存表达式字符串
int mat[][5]={//优先级矩阵，若mat[i][j]==1,则表示i号运算符优先级大于j号
 //运算符，运算符编码规则为+为1号，-为2号，*为3号，/为4号，我们认为添加在表达式
 //首尾的标记运算符为0号
 1,0,0,0,0,//0
 1,0,0,0,0,//1
 1,0,0,0,0,//2
 1,1,1,0,0,//3
 1,1,1,0,0,//4
//  0 1 2 3 4
};
stack<int> op;//运算符栈，保存运算符编号
stack<double> in;//数字栈，运算结果可能存在浮点数，所以保存元素为double
void getOp(bool &reto,int &retn,int &i){//获得表达式中下一个元素函数，若函数运行结束时，引用变量reto为true,则表示该元素为一个运算符，其编号保运在引用
 //变量retn中；否则，表示该元素为一个数字其值保存在引用变量retn中，引用变量i表示遍历到字符串的下标
 if(i==0&&op.empty()==true){//此时遍历字符串的第一个字符，且运算符栈为空，我们人为添加编号为0的标记字符
  reto=true;
  retn=0;
  return;
 }
 if(str[i]==0){//若此时遍历字符为空字符，则表示字符串已经被遍历完
 reto=true;
 retn=0;
 return;
 }
 if(str[i]>='0'&&str[i]<='9'){//若当前字符为数字
 reto=false;//返回为数字
 }
 else{//否则返回为运算符
 reto=true;
 if(str[i]=='+'){
 retn=1;
 }
 else if(str[i]=='-'){
 retn=2;
 }
 else if(str[i]=='*'){
 retn=3;
 }
 else if(str[i]=='/'){
 retn=4;
 }
 i+=2;//i自增，跳过该运算符和其后面的空格
 return;
 }
 retn=0;  //返回结果为数字
 for(;str[i]!=' '&&str[i]!=0;i++){//若字符串未遍历完且不为空格，则依次遍历其后数字，计算当前连续数字字符表示的数值
 retn*=10;
 retn+=str[i]-'0';
 }
 if(str[i]==' ')//如果字符串未空格，则表示字符串未被遍历完
 {
    i++;
 }
 return;
}
int main(){
    while(gets(str)){//输入字符串，当其位于文件尾时，gets返回0;
 if(str[0]=='0'&&str[1]==0)break;//若输入只有一个0，则退出
 bool retop;int retnum;//定义函数所需要的引用变量
 int idx=0;//定义遍历到的字符串的下标，初始变量值为0
 while(!op.empty()) op.pop();
 while(!in.empty()) in.pop();//如果两个栈不是空的，则清空数字栈和运算符栈
 while(true){//循环变脸表达式字符串
      getOp(retop,retnum,idx);//获取表达式中的下一个元素
   if(retop==false){
   //如果该元素为数字
    in.push((double)retnum);//压入数字栈中
   }
   else{
       double tmp;
    if(op.empty()==true||mat[retnum][op.top()]==1){
       op.push(retnum);
    }//若运算符堆栈为空或者当前遍历到的运算符优先级大于栈顶运算符将该运算符压入运算符堆栈
    else{
     while(mat[retnum][op.top()==0]){
     //只要当前运算符优先级小于栈顶元素运算符，则重复循环
      int ret=op.top();
      op.pop();
      double b=in.top();
      in.pop();
      double a=in.top();
      in.pop();
      if(ret==1) tmp=a+b;
      else if(ret==2) tmp=a-b;
      else if(ret==3) tmp=a*b;
      else tmp=a/b;
      in.push(tmp);//将结果压入运算符堆栈
     }
     op.push(retnum);//将当前运算符压入栈中
    }
   }
  if(op.size()==2&&op.top()==0)break;//若运算符堆栈只有两个元素，且栈顶元素为标记运算符，则表示表达式求值结束
  
 }
 printf("%.2f\n",in.top());//输出数字栈中唯一的数字即为答案
 }
  return 0;
}