...被输入给坑了 应该先把所有的空格删掉再玩  还有就是测试点里好像根本就没有关于后结合的事情...不过后结合也很简单 控制一下优先级的判断即可.

中缀表达式的处理核心就是两个堆栈的维护

一个是 操作符栈

一个是 操作数栈

只有当 当前正在处理的操作符的优先级大于(不考虑后结合时) 栈顶操作符的时候, 才进行计算.(或者出现右括号时 一直计算到左括号出现)

代码比较长 用了struct来存储token 比较清晰.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;struct Token{ enum token_type { NUMBER = 1, OP=2 }type; long long number; string op; int priority;};vector
             
               tokens;//语法单元集合stack
              
                number_stack;//操作数栈stack
               
                 op_stack; //运算符栈bool init(){ string input;//todo expression getline(cin,input); string xpr = ""; for (int i = 0; i < input.length(); ++i) { if(input[i]!=' ') xpr+=input[i]; } Token tmp; for (int i = 0; i < xpr.length(); ++i) { switch(xpr[i]){ case ' ': continue; break; case '+': tmp.type = Token::OP; tmp.op = "+"; tmp.priority = 1; break; case '-': //两种情况 if(i>=1 and (xpr[i-1]==')' or isdigit(xpr[i-1])))//作为减号使用 { tmp.type = Token::OP; tmp.op = "-"; tmp.priority = 1; }else{ //作为负号使用(取反运算) tmp.type = Token::OP; tmp.op = "$";//特殊标记 tmp.priority = 10;//优先级最高 单元运算符 取反 } break; case '*': tmp.type = Token::OP; tmp.op = "*"; tmp.priority = 2; break; case '/': tmp.type = Token::OP; tmp.op = "/"; tmp.priority = 2; break; case '^':// tmp.type = Token::OP; tmp.op = "^"; tmp.priority = 3; //if(tokens.size()>=2 and tokens[tokens.size()-2].op=="^") // tmp.priority = tokens.back().priority + 1; break; case '(': tmp.type = Token::OP; tmp.op = "("; tmp.priority = 0; break; case ')': tmp.type = Token::OP; tmp.op = ")"; tmp.priority = 4; break; default: //是数字了 string num = ""; while( i < xpr.length() and isdigit(xpr[i])) num += xpr[i++]; //由于循环外侧还有一个i++ 所以这里要-1 --i; stringstream ss; ss<
                
                 >tmp.number; tmp.type = Token::NUMBER; tmp.op = ""; break; } tokens.push_back(tmp); } return true;}//进行计算bool calc(Token op){ long long a , b; if((op.op=="$" and number_stack.empty()) or (op.op!="$" and number_stack.size()<2)) return false; if(op.op == "$"){ a = number_stack.top();number_stack.pop(); number_stack.push(-1*a); }else if(op.op=="+"){ a = number_stack.top();number_stack.pop(); b = number_stack.top();number_stack.pop(); number_stack.push(b+a); }else if(op.op=="-"){ a = number_stack.top();number_stack.pop(); b = number_stack.top();number_stack.pop(); number_stack.push(b-a); }else if(op.op=="*"){ a = number_stack.top();number_stack.pop(); b = number_stack.top();number_stack.pop(); number_stack.push(b*a); }else if(op.op=="/"){ a = number_stack.top();number_stack.pop(); b = number_stack.top();number_stack.pop(); if(a==0) //除零错 return false; number_stack.push(b/a); }else if(op.op=="^"){ //右结合稍后处理 a = number_stack.top();number_stack.pop(); b = number_stack.top();number_stack.pop(); number_stack.push((long long)pow(b, a)); } return true;}bool build(){ for (int i = 0; i < tokens.size() ; ++i) { if(tokens[i].type == Token::OP){ //是操作符 if(tokens[i].op=="("){ op_stack.push(tokens[i]); }else if(tokens[i].op==")"){ // 一直pop 直到找到了左括号//如果没有一直没有遇到左括号则报错 while( !op_stack.empty() and op_stack.top().op != "("){ if(!calc(op_stack.top())) return false; op_stack.pop(); } //处理一下左括号 if(op_stack.empty()) return false; if(op_stack.top().op == "(") op_stack.pop(); }else{ // + - * / $ if(op_stack.empty()) op_stack.push(tokens[i]); else{ int top_pr = op_stack.top().priority; int cur_pr = tokens[i].priority; //如果当前的运算符的优先级 比 栈顶优先级高的话 if( cur_pr > top_pr or (tokens[i].op =="^" and op_stack.top().op=="^")){ op_stack.push(tokens[i]); }else{ while(cur_pr <= top_pr){ //如果当前运算符的优先级比栈顶的优先级低或者等于的时候 就不断计算 if(!calc(op_stack.top())) return false; op_stack.pop(); if(op_stack.empty()) break; top_pr = op_stack.top().priority; } //现在可以把正在处理的运算符入栈了 op_stack.push(tokens[i]); } } } }else if(tokens[i].type==Token::NUMBER){ //是操作数 number_stack.push(tokens[i].number); } } //进行运算 while (!op_stack.empty()){ if(op_stack.top().op=="(") return false; if(!calc(op_stack.top())) return false; op_stack.pop(); } return (number_stack.size()==1);}void print(){ for (int i = 0; i