1 #include 
      
         2 #include 
       
          3 #include 
        
           4   5 using std::string;  6 using std::vector;  7 using std::stack;  8   9 class Element { 10 public: 11     static Element MakeData(double value_) {
    return Element(DATA, value_, ' ');} 12     static Element MakeOp(char op) {
    return Element(OP, 0.0, op);} 13     bool isData() const { return t == DATA; } 14     bool isOp() const { return t == OP; } 15     char getOp() const { return op;} 16     double getValue() const { return value; } 17     int priority() const { 18         if (isOp()) { 19             if (getOp() == '*' || getOp() == '/') { 20                 return 2; 21             } else if (getOp() == '+' || getOp() == '-') { 22                 return 1; 23             } else if (getOp() == '(' || getOp() == ')') { 24                 return 0; 25             } 26         } 27         return -1; 28     } 29 private: 30     enum Type {DATA, OP}; 31     Type t; 32     double value; 33     char op; 34     Element(Type t_, double value_, char op_) : t(t_), value(value_), op(op_) {} 35  }; 36  37 bool isOp(char c) { 38     return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')'; 39 } 40  41 // 判断当前的 + - 是否为单目操作符 比如 （-3） 42 bool isSign(const string &input, size_t i) { 43     char c = input[i]; 44     if (c == '+' || c == '-') { 45         if (i == 0) { 46             return true; 47         } 48         if (input[i - 1] == '(') { 49             return true; 50         } 51     } 52     return false; 53 } 54  55 vector
         
           str2mid(const string &input) { 56     vector
          
            mid; 57     string data; 58     for (size_t i = 0; i < input.length(); i++) { 59         if (isSign(input, i)) { 60             data += input[i]; 61             continue; 62         } 63         if (isOp(input[i])) { 64             if (data != "") { 65                 mid.push_back(Element::MakeData(std::stod(data))); 66                 data = ""; 67             } 68             mid.push_back(Element::MakeOp(input[i])); 69         } else if (!isspace(input[i])){ 70             data += input[i]; 71         } 72     } 73     if (data != "") { 74         mid.push_back(Element::MakeData(std::stod(data))); 75         data = ""; 76     } 77     return mid; 78 } 79  80 vector
           
             mid2post(const vector
            
              &mid) { 81 stack
             
               s; 82 vector
              
                post; 83 for (auto it = mid.begin(); it != mid.end(); it++) { 84 if (it->isData()) { // 如果是操作数，直接输出 85 post.push_back(*it); 86 } else if (it->isOp() && it->getOp() == '(') { // 如果是'('直接入栈 87 s.push(*it); 88 } else if (it->isOp() && it->getOp() == ')') { // 如果是')'将栈中'('之后的操作符出栈 89 while(!s.empty() && s.top().getOp() != '(') { 90 post.push_back(s.top()); 91 s.pop(); 92 } 93 s.pop(); 94 } else if (it->isOp()) { // 如果是操作符 出栈直到栈顶优先级低于该操作符，其中'('的优先级最低，然后把该操作符入栈 95 while(!s.empty() && s.top().priority() >= it->priority()) { 96 post.push_back(s.top()); 97 s.pop(); 98 } 99 s.push(*it);100 }101 }102 while(!s.empty()) { // 栈中元素全部出栈103 post.push_back(s.top());104 s.pop();105 }106 return post;107 }108 109 double calc_post(const vector
               
                 &post) {110 stack
                
                  s;111 for (auto it = post.begin(); it != post.end(); it++) {112 if (it->isData()) {113 s.push(*it);114 } else if (it->isOp()) {115 double op_2 = s.top().getValue();116 s.pop();117 double op_1 = s.top().getValue();118 s.pop();119 char op = it->getOp();120 if (op == '+') {121 s.push(Element::MakeData(op_1 + op_2));122 } else if (op == '-') {123 s.push(Element::MakeData(op_1 - op_2));124 } else if (op == '*') {125 s.push(Element::MakeData(op_1 * op_2));126 } else if (op == '/') {127 s.push(Element::MakeData(op_1 / op_2));128 }129 }130 }131 return s.top().getValue();132 }133 134 double calc(const std::string &input) {135 return calc_post(mid2post(str2mid(input)));136 }