九度 1408 寻找表达式 (中缀转后缀)-白红宇

九度 1408 寻找表达式 (中缀转后缀)

阅读量：6869 次

发布时间：2019-06-26

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

总结

1. '_' 运算符不是 a*10 + b, 而是 a*(10 or 100) + b

2. char * 与 string 的相互转化

char* = string.c_str()

string = char*

3. 中缀表达式转后者表达式参考:http://www.cnblogs.com/xinsheng/p/3591781.html

4. 通用的中缀转后缀, 用 string 存数据比较好

代码未通过九度测试

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               using namespace std;string ops[3] = {" ", "+", "-"};map
               
                 priority;vector
                
                 
                   > resVec;int n;string i2s(int i) { char s[20]; sprintf(s, "%d", i); string str = s; return str;}int s2i(string &str) { int tmp(atoi(str.c_str())); return tmp;}int calculate(vector
                  
                    &vec) { vector
                   
                     pos; deque
                    
                      stack; for(int i = 0; i < vec.size(); i ++) { if(priority.count(vec[i]) == 0){ // is number pos.push_back(vec[i]); continue; } while(!stack.empty()) { string lastOp = stack.back(); if(priority[vec[i]]> priority[lastOp]) { stack.push_back(vec[i]); break; }else { pos.push_back(lastOp); stack.pop_back(); } } // is operator if(stack.empty()) { stack.push_back(vec[i]); continue; } } while(!stack.empty()) { pos.push_back(stack.back()); stack.pop_back(); } stack.clear(); for(int i = 0; i < pos.size(); i ++) { if(priority.count(pos[i]) == 0) { stack.push_back(pos[i]); }else { string sec = stack.back(); stack.pop_back(); string fir = stack.back(); stack.pop_back(); if(pos[i] == "+") { int ret = s2i(fir) + s2i(sec); stack.push_back(i2s(ret)); }else if(pos[i] == "-") { int ret = s2i(fir) - s2i(sec); stack.push_back(i2s(ret)); }else { int ret = s2i(fir)*pow(10, sec.size()) + s2i(sec); stack.push_back(i2s(ret)); } } } return s2i(stack.back());}void dfs(int i, vector
                     
                       &party) { if(i == n) { party.push_back(i2s(n)); int val = calculate(party); if(val == 0) resVec.push_back(party); party.pop_back(); return; } party.push_back(i2s(i)); for(int j = 0; j < 3; j ++) { party.push_back(ops[j]); dfs(i+1, party); party.pop_back(); } party.pop_back();}int main() { //freopen("C:\\Users\\vincent\\Dropbox\\workplacce\\joj\\test.txt", "r", stdin); priority["+"] = 1; priority["-"] = 1; priority[" "] = 2; while(scanf("%d", &n) != EOF) { vector
                      
                        temp; dfs(1, temp); for(int i = 0; i < resVec.size(); i ++) { for(int j = 0; j < resVec[i].size(); j ++) { cout << resVec[i][j]; } cout << endl; } } return 0;}