91久久国产视频,亚洲精品乱码久久久久久久久久久久,蜜臀久久99精品久久久久久

hdu3596(逆波蘭表達式求值)

/*************************************/
/*支持數字(而非表達式)前面有正負號   */
/*支持浮點數的+，-，*，/,^ 運算      */
/*************************************/
#include <stdio.h>
#include <memory>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <time.h>
#include <limits>
#include <stack>
using namespace std;
#define N 10005
#define eps 1e-9
#define vType double
struct node{
vType val;
char op;
node(vType _val=0, char _op = ' '):val(_val), op(_op){}
}nodes[N];
char str[N];
inline bool isDigit(char ch){
return ch >= '0' && ch <= '9';
}
map<char, int> ms;
void init(){
ms['('] = 0;
ms['-'] = ms['+'] = 1;
ms['*'] = ms['/'] = 2;
ms['^'] = 3;
}
vType calPoland(node* nodes, int k){
int i, j;
vType a, b;
stack<vType> s;
for(i = 0; i < k; i++){
  if(nodes[i].op == ' '){
   s.push(nodes[i].val);
  }else{
   a = s.top();
   s.pop();
   b = s.top();
   s.pop();
   switch(nodes[i].op){
    case '+':
     s.push(b + a);
     break;
    case '-':
     s.push(b - a);
     break;
    case '*':
     s.push(b * a);
     break;
    case '/':
     if(fabs(a) < eps) throw true;
     s.push(b / a);
     break;
    case '^':
     s.push(pow(b, a));
     break;
   }
  }
}
return s.top();
}
vType poland(char* str){
int i, k, sign;
bool inNum, hasDot; //inNum標記當前是否可以輸入數字, hasDot標記是否已經輸入小數點
stack<char> oper;
for(i = k = 0, sign = 1, inNum = true; str[i]; i++){
  if(isDigit(str[i]) || str[i] == '.'){
   if(inNum){
    vType val;
    double w = 1;
    if(str[i] == '.'){
     hasDot = true;
     val = 0;
    }
    else{
     val = str[i] - '0';
     hasDot = false;
    }
    i++;
    while(isDigit(str[i]) || str[i] == '.'){
     if(str[i] == '.'){
      if(hasDot) throw true;
      hasDot = true;
     }else{
      if(hasDot){
       w *= 0.1;
       val += (str[i] - '0') * w;
      }
      else val = val * 10 + str[i] - '0';
     }
     i++;
    }
    i--;
    nodes[k++] = node(val * sign, ' ');
    sign = 1;
    inNum = false;
   }else throw true;
  }else{
   switch(str[i]){
    case '(':
     oper.push(str[i]);
     break;
    case ')':
     while(!oper.empty() && oper.top() != '('){
      nodes[k++] = node(0, oper.top());
      oper.pop();
     }
     if(oper.empty()) throw true; //沒有與')'匹配的'('
     oper.pop();
     break;
    case '+':
    case '-':
    case '*':
    case '/':
    case '^':
     if(inNum){
      if(str[i] != '+' && str[i] != '-') throw true;
      while(str[i] == '+' || str[i] == '-'){
       if(str[i] == '-') sign *= -1;
       i++;
      }
      i--;
     }else{
      //while(!oper.empty() && ((str[i] != '^' && ms[str[i]] <= ms[oper.top()]) ||
      // ((str[i] == '^' && ms[str[i]] < ms[oper.top()])))){ //如果^是右結合的話就用這個
      while(!oper.empty() && ms[str[i]] <= ms[oper.top()]){
        nodes[k++] = node(0, oper.top());
        oper.pop();
      }
      oper.push(str[i]);
      inNum = true;
     }
     break;
   }
  }
}
while(!oper.empty()){
  nodes[k++] = node(0, oper.top());
  oper.pop();
}
return calPoland(nodes, k);
}
void Cal(char* str){
try{
  vType ans = poland(str);
  printf("%.8lf\n", ans);
}
catch(bool){
  printf("The teacher is so lazy!\n");
}
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
init();
while(~scanf("%s", str)) Cal(str);
return 0;
}

posted on 2011-01-16 19:58 tw 閱讀(717) 評論(0) 編輯收藏引用所屬分類: HDU題解

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: hdu3440(差分約束) hdu3436(數據結構) hdu3433(dp) hdu3434 hdu3596(逆波蘭表達式求值) hdu 3624 （算術表達式求值）

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

hdu3596(逆波蘭表達式求值)

導航

統計

常用鏈接

留言簿

文章分類

文章檔案

搜索

最新評論