2014
11-27

# Lazy

One of Mr.Lazy’s kids which is called So Lazy and he is a pupil. As we know ‘Like Father, Like Son’,So Lazy and his father–Mr.Lazy is lazy where industriousness is expected.So Lazy is enjoying his summer vacation,and he is so lzay to finish his homework. He nearly forget this.Now,new term is around the corner,he feels more and more anxious day after day. He is so worry to finish his homework,he calculate very fast,and as a lazy man,he may make some mistakes.To accomplish his homework as fast as he can,he asks you (her elder bother Super Lazy) for help to check his homework.It is to say you must calculate all of his homework.As one of the most lazy people in the world.We know that you are industrious while coding,so you can solve this problem by computer program.

Each line,there is one formula of algebra.The formula may include the following operator "+ – * / ^".(X^4 (def) X*X*X*X ),and all the numbers are real number and fit for double.Deviding 0 is illegal. Input end with the end of file.More information in sample.The length of the formula always less than 10000.

Each line,there is one formula of algebra.The formula may include the following operator "+ – * / ^".(X^4 (def) X*X*X*X ),and all the numbers are real number and fit for double.Deviding 0 is illegal. Input end with the end of file.More information in sample.The length of the formula always less than 10000.

(-9)
(2+8)^0.5+9
(+9)+1
3.1+4.5/(3-(2*1.5))
(+9)+89+(12*3.0*0.1/0.45)+.34+1

-9.00000000
12.16227766
10.00000000
The teacher is so lazy!
107.34000000

HintIt is so easy,no trick exists. 

C++语言: hdu 3596
001 #include <cstdio>
002 #include <cstring>
003 #include <sstream>
004 #include <stack>
005 #include <vector>
006 #include <cmath>
007 using namespace std;
008
009 char buf[100000];
010
011 struct Node {
012     char _opt;
013     double _x;
014 } tmp;
015
016 vector<Node> ps;
017
018 void get_stack() {
019     stack<char> cs;
020     istringstream in(buf);
021     char c;
022     int sig = 1;
023     in >> c;
024     if (c == ‘-’)
025         sig = -1;
026     else if (c == ‘+’)
027         sig = 1;
028     else
029         in.putback(c);
030     while (in >> c)
031         switch (c) {
032         case ‘(‘:
033             cs.push(c);
034             in >> c;
035             if (c == ‘-’)
036                 sig = -1;
037             else if (c == ‘+’)
038                 sig = 1;
039             else
040                 in.putback(c);
041             break;
042         case ’0′: case ’1′: case ’2′: case ’3′: case ’4′:
043         case ’5′: case ’6′: case ’7′: case ’8′: case ’9′: case ‘.’:
044             in.putback(c);
045             in >> tmp._x;
046             tmp._opt = 0;
047             tmp._x *= sig;
048             ps.push_back(tmp);
049             sig = 1;
050             break;
051         case ‘+’: case ‘-’:
052             while (!cs.empty() && cs.top() != ‘(‘) {
053                 tmp._opt = cs.top();
054                 ps.push_back(tmp);
055                 cs.pop();
056             }
057             cs.push(c);
058             break;
059         case ‘*’: case ‘/’:
060             while (!cs.empty() && (cs.top() == ‘*’ || cs.top() == ‘/’ || cs.top() == ‘^’)) {
061                 tmp._opt = cs.top();
062                 ps.push_back(tmp);
063                 cs.pop();
064             }
065             cs.push(c);
066             break;
067         case ‘^’:
068             while (!cs.empty() && cs.top() == ‘^’) {
069                 tmp._opt = cs.top();
070                 ps.push_back(tmp);
071                 cs.pop();
072             }
073             cs.push(c);
074             break;
075         case ‘)’:
076             while (cs.top() != ‘(‘) {
077                 tmp._opt = cs.top();
078                 ps.push_back(tmp);
079                 cs.pop();
080             }
081             cs.pop();
082             break;
083         }
084     while (!cs.empty() && cs.top()) {
085         tmp._opt = cs.top();
086         ps.push_back(tmp);
087         cs.pop();
088     }
089 }
090
091 double getres(double x1, double x2, char opt){
092     double r;
093     switch (opt) {
094     case ‘+’: r = x1 + x2; break;
095     case ‘-’: r = x1 - x2; break;
096     case ‘*’: r = x1 * x2; break;
097     case ‘/’:
098         if (fabs(x2) <= 1e-9)
099             throw true;
100         r = x1 / x2; break;
101     case ‘^’:
102         r = pow(x1, x2);
103         break;
104     }
105     return r;
106 }
107
108 double calc() {
109     stack<double> ds;
110     for (vector<Node>::iterator it = ps.begin(); it != ps.end(); ++it) {
111         if (it->_opt == 0)
112             ds.push(it->_x);
113         else {
114             double x2 = ds.top();
115             ds.pop();
116             double x1 = ds.top();
117             ds.pop();
118             ds.push(getres(x1, x2, it->_opt));
119         }
120     }
121     return ds.top();
122 }
123
124 int main(){
125 #ifndef ONLINE_JUDGE
126     freopen(“in.txt”, “r”, stdin);
127     freopen(“out.txt”, “w”, stdout);
128 #endif
129     while (gets(buf)) {
130         ps.clear();
131         get_stack();
132         try {
133             printf(“%.8lf\n, calc());
134         } catch(bool) {
135             puts(“The teacher is so lazy!”);
136         }
137     }
138     return 0;
139 }

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？