栈与队列的应用——计算表达式的值-白红宇

栈与队列的应用——计算表达式的值

阅读量：4216 次

发布时间：2019-05-26

本文共 1394 字，大约阅读时间需要 4 分钟。

在这里插入图片描述

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        using namespace std;struct node{ double num; char op; bool flag;};string str;stack
         
           s;queue
          
            q;map
           
             op;void Change(){ // 中缀转后缀 node temp; for(int i = 0; i < str.length();) { if(str[i] >= '0' && str[i] <= '9') { // 处理数字 temp.flag = true; temp.num = str[i++] - '0'; while(i < str.length() && str[i] >= '0' && str[i] <= '9') { temp.num = temp.num * 10 + str[i] - '0'; i++; } q.push(temp); } else{ // 处理操作符 temp.flag = false; while(!s.empty() && op[str[i]] <= op[s.top().op]) { q.push(s.top()); s.pop(); } temp.op = str[i]; s.push(temp); i++; } } while(!s.empty()) { q.push(s.top()); s.pop(); }}double Cal(){ // 计算后缀表达式的值 double temp1, temp2; node cur, temp; while(!q.empty()) { cur = q.front(); q.pop(); if(cur.flag == true) s.push(cur); else{ temp2 = s.top().num; s.pop(); temp1 = s.top().num; s.pop(); temp.flag = true; if(cur.op == '+') temp.num = temp1 + temp2; else if(cur.op == '-') temp.num = temp1 - temp2; else if(cur.op == '*') temp.num = temp1 * temp2; else temp.num = temp1 / temp2; s.push(temp); } } return s.top().num;}int main(){ op['+'] = 1; op['-'] = 1; op['*'] = 2; op['/'] = 2; getline(cin,str); for(string::iterator it = str.end(); it != str.begin(); it--) { if(*it == ' ') str.erase(it); } while(!s.empty()) s.pop(); Change(); printf("%.2f\n", Cal()); return 0;}