午夜久久99,久久久亚洲精品一区二区三区,在线电影一区

haha

hdu3596(逆波蘭表達(dá)式求值)

/*************************************/
/*支持?jǐn)?shù)字(而非表達(dá)式)前面有正負(fù)號   */
/*支持浮點(diǎn)數(shù)的+，-，*，/,^ 運(yùn)算      */
/*************************************/
#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標(biāo)記當(dāng)前是否可以輸入數(shù)字, hasDot標(biāo)記是否已經(jīng)輸入小數(shù)點(diǎn)
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()])))){ //如果^是右結(jié)合的話就用這個
      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 閱讀(729) 評論(0) 編輯收藏引用所屬分類: HDU題解

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: hdu3440(差分約束) hdu3436(數(shù)據(jù)結(jié)構(gòu)) hdu3433(dp) hdu3434 hdu3596(逆波蘭表達(dá)式求值) hdu 3624 （算術(shù)表達(dá)式求值）

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

<

2025年12月

>

日

一

二

三

四

五

六

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

導(dǎo)航

統(tǒng)計(jì)

隨筆 - 0
文章 - 11
評論 - 0
引用 - 0

常用鏈接

留言簿

文章分類

文章檔案

2011年1月 (11)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品