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 阅读(697) 评论(0)  编辑 收藏 引用 所属分类: HDU题解


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

文章分类

文章档案

搜索

最新评论