题目：http://codeup.cn/problem.php?cid=100000605&pid=0

这道题一定要重点关注一下！！！看上去很简单的那种，还是有难度的

  1. 题目给出中缀表达式，求计算结果
  2. 这类表达式计算的题目，一般都是要转化为后缀表达式，然后在计算，所以这道题分两步走，先转后缀，再计算
  3. 由于一直是从左往右扫描，因此存储后缀表达式用queue
  4. 如果有（），那么碰到（就压入栈，碰到）就不停推出操作符栈，直到遇到（
  1. while(getline(cin, str), str != "0"){

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<string>
  4. #include<map>
  5. #include<stack>
  6. #include<queue>
  7. using namespace std;
  9. struct node{
  10.     double num;
  11.     char op;
  12.     bool flag;//true 表示操作数 false表示操作符
  13. };
  15. string str;
  16. stack<node> s;//操作符栈
  17. queue<node> q;//后缀表达式序列
  18. map<char, int> op;// 优先级映射
  20. void Change(){
  21.     double num;
  22.     node temp;
  23.     for(int i = 0; i < str.length();){
  24.         if(str[i] >= '0' && str[i] <= '9'){
  25.             temp.flag = true;//此时是操作数
  26.             temp.num = str[i++] - '0';//字符转数字
  27.             while(i < str.length() && str[i] >= '0' && str[i] <= '9'){//当这个数字不止一位的时候
  28.                 temp.num = temp.num * 10 + str[i] - '0';
  29.                 i++;
  30.             }
  31.             q.push(temp);
  32.         } else {//如果是运算符
  33.             temp.flag = false;
  34.             while(!s.empty() && op[str[i]] <= op[s.top().op]){//操作符栈栈顶节点的op符号
  35.                 q.push(s.top());
  36.                 s.pop();
  37.             }
  38.             temp.op = str[i];
  39.             s.push(temp);
  40.             i++;
  41.         }
  42.     }
  43.     while(!s.empty()){
  44.         q.push(s.top());
  45.         s.pop();
  46.     }
  47. }
  48. double Cal(){
  49.     double temp1, temp2;
  50.     node cur, temp;
  51.     while (!q.empty()){
  52.         cur = q.front();//cur是队首元素
  53.         q.pop();
  54.         if(cur.flag == true) s.push(cur);
  55.         else{//队首是数字
  56.             temp2 = s.top().num;//先弹出右边的操作数
  57.             s.pop();
  58.             temp1 = s.top().num;//后弹出的那个是左边的操作数
  59.             s.pop();
  60.             temp.flag = true;//临时记录操作数
  61.             if(cur.op == '+') temp.num = temp1 + temp2;
  62.             else if(cur.op == '-') temp.num = temp1 - temp2;
  63.             else if(cur.op == '*') temp.num = temp1 * temp2;
  64.             else if(cur.op == '/') temp.num = temp1 / temp2;
  65.             s.push(temp);
  66.         }
  67.     }
  68.     return s.top().num;//计算完毕
  69. }
  71. int main(){
  72.     op['+'] = op['-'] = 1;
  73.     op['*'] = op['/'] = 2;
  74.     while(getline(cin, str), str != "0"){
  75.         for(auto it = str.end(); it != str.begin(); it--){
  76.             if(*it == ' ') str.erase(it);
  77.         }
  78.         while(!s.empty()) s.pop();
  79.         Change();
  80.         printf("%.2lf\n",Cal());
  81.     }
  82. }