POJ 2252 - Equation Solver

http://poj.org/problem?id=2252

概要

与えられた EBNF に従った一次方程式が与えられるので，その解を答える．

ただし，解が無いときは「No solution.」と答え，解が無数にあるときは「Infinitely many solutions.」と答える．

制約

解法

構文解析しながら，一次式の加算・減算・乗算をするだけ．

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 struct expr
 6 {
 7   int x, c;
 8   expr(int a, int b) : x(a), c(b) {}
 9   static expr var(int a) { return expr(a, 0); }
10   static expr lit(int a) { return expr(0, a); }
11 
12   expr& operator+=(const expr& e) { x += e.x; c += e.c; return *this;}
13   expr& operator-=(const expr& e) { x -= e.x; c -= e.c; return *this;}
14   expr& operator*=(const expr& e) { x = x*e.c + e.x*c; c = c * e.c; return *this; }
15 };
16 
17 typedef string::const_iterator Iterator;
18 
19 expr parse_expr(Iterator& it, const Iterator& last);
20 
21 expr parse_factor(Iterator& it, const Iterator& last)
22 {
23   if (*it == '(') {
24     ++it;
25     const expr e = parse_expr(it, last);
26     ++it;
27     return e;
28   } else if (*it == 'x') {
29     ++it;
30     return expr::var(1);
31   } else if (isdigit(*it)) {
32     int n = 0;
33     while (it != last && isdigit(*it)) {
34       n = 10*n + *it-'0';
35       ++it;
36     }
37     return expr::lit(n);
38   } else {
39     throw "parse error";
40   }
41 }
42 
43 expr parse_term(Iterator& it, const Iterator& last)
44 {
45   expr l = parse_factor(it, last);
46   while (it != last && (*it == '*')) {
47     ++it;
48     const expr r = parse_factor(it, last);
49     l *= r;
50   }
51   return l;
52 }
53 
54 expr parse_expr(Iterator& it, const Iterator& last)
55 {
56   expr l = parse_term(it, last);
57   while (it != last && (*it == '+' || *it == '-')) {
58     const char op = *it;
59     ++it;
60     const expr r = parse_term(it, last);
61     if (op == '+') {
62       l += r;
63     } else {
64       l -= r;
65     }
66   }
67   return l;
68 }
69 
70 int main()
71 {
72   string line;
73   for (int Ti = 1; getline(cin, line); Ti++) {
74     Iterator it = line.begin(), last = line.end();
75     expr l = parse_expr(it, last);
76     if (it == last || *it != '=') {
77       throw "parse_error";
78     }
79     ++it;
80     const expr r = parse_expr(it, last);
81     l -= r;
82     printf("Equation #%d\n", Ti);
83     if (l.x == 0) {
84       if (l.c == 0) {
85         puts("Infinitely many solutions.");
86       } else {
87         puts("No solution.");
88       }
89     } else {
90       printf("x = %.6f\n", double(-l.c)/l.x);
91     }
92     putchar('\n');
93   }
94   return 0;
95 }
poj/2252.cc