Форум программистов, компьютерный форум CyberForum.ru

Программа упрощения полиномов - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Цикл for http://www.cyberforum.ru/cpp-beginners/thread341464.html
Как записать for (i=0; i<n; i++) if (i!=t) ... Надо записать что-то типа for (i=0, i!=t; i<n; i++)
C++ Для чего нужны вложенные структуры? Скажите пожалуйста для чего нужны вложенные структуры и где их используют? http://www.cyberforum.ru/cpp-beginners/thread341415.html
C++ Sleep внутри мьютекса
Может ли это как-то вешать программу, если да то почему?
stdio C++
Всем привет) Народ помогите пожалуйста.. я хочу набивать руку решая и отправляя задачи сюда ******** ) но там надо считывать исходные данные из input.txt и записывать в output.txt.. я знаю тока то что ето можно сделать с помошью библиотеки stdio... переделайте пожалуйста код етой програмы чтобы переменные считывались с input.txt и записывались в output.txt ...так понятнее будет)))) и...
C++ Кэширование рекурсии http://www.cyberforum.ru/cpp-beginners/thread341386.html
Доброго времени суток. Есть задача. Ириска весит X грамм, мандарин – Y грамм, пряник – Z грамм. Требуется написать программу, которая определит, сколько различных вариантов подарков весом ровно W грамм может сделать Дед Мороз. Сделать хотелось именно рекурсией(с циклами тривиально слишком), но я наткнулся на подводный камень - значения вычислялись по несколько раз и это приводило к...
C++ чтение строки а не не ниче)) подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
13.08.2011, 17:42     Программа упрощения полиномов
Можно методом рекурсивного спуска сделать:
C++
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
/////////////////////////////////////////////////////////////////////////////////////////
//  На вход программы из текстового файла поступает выражение вида:
//  p^2*(2*p^2+11*p-1)*(3*p+1)-4*p*(p+6)+12*p*(3*p^2-6*p+1)+8
//  на выходе нужно представить полином в нормальном виде (для данного случая будет):
//  6*p^5+35*p^4+44*p^3-77*p^2-12*p+8
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <functional>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef int                 T_num;
typedef std::vector<T_num>  T_polynom_val;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_polynom
{
    T_polynom_val  polynom_val_;
    //-----------------------------------------------------------------------------------
public:
    T_polynom(T_num  scalar_val = 0)
    {
        set_scalar(scalar_val);
    }
    //-----------------------------------------------------------------------------------
    const  T_polynom&  operator+= (const T_polynom&  polynom)
    {    
        T_polynom  right_polynom(polynom);
        to_increase_degree_if_is_less                ( right_polynom.get_degree() );      
        right_polynom.to_increase_degree_if_is_less  ( get_degree()               );
        
        std::transform
            (
                polynom_val_.begin(), polynom_val_.end(),
                right_polynom.polynom_val_.begin(),
                polynom_val_.begin(),
                std::plus<T_polynom_val::value_type>()
            );
 
        return  *this;
    }
    //-----------------------------------------------------------------------------------
    const  T_polynom&  operator*= (const T_polynom&  polynom)
    {
        T_polynom  res_polynom;
        res_polynom.to_increase_degree_if_is_less( get_degree() + polynom.get_degree() );
        for(size_t  i = 0; i < polynom_val_.size(); ++i)
        {
            for(size_t  j = 0; j < polynom.polynom_val_.size(); ++j)
            {
                res_polynom.polynom_val_[i + j] += polynom_val_[i] * polynom.polynom_val_[j];
            }        
        }
        polynom_val_ = res_polynom.polynom_val_;
        return  *this;
    }
    //-----------------------------------------------------------------------------------
    void  set_scalar(T_num  scalar_val)
    {
        polynom_val_ = T_polynom_val(1, scalar_val);
    }
    //-----------------------------------------------------------------------------------
    void  set_x_with_degree(int  degree_val)
    {
        polynom_val_ = T_polynom_val(degree_val + 1);
        polynom_val_[degree_val] = 1;
    }
    //-----------------------------------------------------------------------------------
    const  T_polynom&  operator-= (const T_polynom&  polynom)
    {
        T_polynom  minus_polynom(polynom);
        minus_polynom.operator *=(-1);
        return operator+=(minus_polynom);
    }
    //-----------------------------------------------------------------------------------
    int  get_degree() const
    {
        return  polynom_val_.size() - 1;
    }
    //-----------------------------------------------------------------------------------
    T_num  operator[] (int  ind) const
    {
        return  polynom_val_[ind];
    }
    //-----------------------------------------------------------------------------------
    void  to_increase_degree_if_is_less(int  degree_val)
    {
        if(get_degree() < degree_val)        
        {
            polynom_val_.resize(degree_val + 1);
        }       
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
class T_calculator
{
    enum
    {
        LEFT_PARENTHESIS   = '(',
        RIGHT_PARENTHESIS  = ')',               
        
        PLUS_SIGN          = '+',
        MINUS_SIGN         = '-',        
 
        ASTERISK           = '*',
 
        P_SYMB             = 'p',
        POW_SYMB           = '^',
        FINISH_SYMB        = '$'
    };
public:
    T_calculator();    
private:
    //-----------------------------------------------------------------------------------   
    void  remove_spaces             (T_str&  s);
    bool  calc_expr                 (const T_str&  s_inp, T_str&  s_out, T_polynom&  res); 
    bool  calc_summand              (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_line_of_summand      (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_factor               (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_line_of_factor       (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_add_summand          (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_subtract_summand     (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_mult_to_factor       (const T_str&  s_inp, T_str&  s_out, T_polynom&  res); 
    bool  calc_minus_factor         (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_expr_in_brackets     (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_p_expr               (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);
    bool  calc_scalar               (const T_str&  s_inp, T_str&  s_out, T_polynom&  res);    
    bool  calc_num                  (const T_str&  s_inp, T_str&  s_out, T_num&      res);   
 
    bool  calc_plus                 (const T_str&  s_inp, T_str&  s_out);
    bool  calc_asterisk             (const T_str&  s_inp, T_str&  s_out);
    bool  calc_minus                (const T_str&  s_inp, T_str&  s_out);
    bool  calc_left_parenthesis     (const T_str&  s_inp, T_str&  s_out);
    bool  calc_right_parenthesis    (const T_str&  s_inp, T_str&  s_out);
    bool  calc_p_symb               (const T_str&  s_inp, T_str&  s_out);
    bool  calc_pow_symb           (const T_str&  s_inp, T_str&  s_out);
 
    bool  calc_symb                 (const char c, const T_str&  s_inp, T_str&  s_out);
 
    T_str  get_polynom_str          (const T_polynom&  res);
};
/////////////////////////////////////////////////////////////////////////////////////////
void  T_calculator::remove_spaces(T_str&  s)
{    
    for(;;)
    {
        T_str::size_type  pos = s.find_first_of(" \t");   
        if(pos == T_str::npos)
        {
            break;
        }
        s = s.erase(pos, 1);
    }    
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_expr
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{    
    return     calc_summand         (s_inp, s_out, res)
            && calc_line_of_summand (s_out, s_out, res);            
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_summand
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{    
    return     calc_factor         (s_inp, s_out, res)
            && calc_line_of_factor (s_out, s_out, res);   
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_line_of_summand
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{   
    switch(s_inp[0])
    {
    case PLUS_SIGN:
        return     calc_add_summand      (s_inp, s_out, res)
                && calc_line_of_summand  (s_out, s_out, res);
    case MINUS_SIGN:
        return     calc_subtract_summand (s_inp, s_out, res)
                && calc_line_of_summand  (s_out, s_out, res);
    default:
        return  true;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_add_summand
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{    
    T_polynom  res_summand;
    bool       bool_res =     calc_plus    (s_inp, s_out)
                           && calc_summand (s_out, s_out, res_summand);
    res += res_summand;
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_line_of_factor
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{
    switch(s_inp[0])
    {
    case ASTERISK:
        return     calc_mult_to_factor  (s_inp, s_out, res)
                && calc_line_of_factor  (s_out, s_out, res);
    default:
        return  true;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_mult_to_factor
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{    
    T_polynom  res_factor;
    bool   bool_res =     calc_asterisk (s_inp, s_out)
                       && calc_factor   (s_out, s_out, res_factor);
    res *= res_factor;
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_asterisk(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(ASTERISK, s_inp, s_out);
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_symb(const char c, const T_str&  s_inp, T_str&  s_out)
{    
    bool  res = (s_inp[0] == c);
    if(res)
    {        
        s_out = s_inp.substr(1);
    }
    return res;    
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_factor
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{    
    switch(s_inp[0])
    {
    case MINUS_SIGN:
        return  calc_minus_factor           (s_inp, s_out, res);
    case LEFT_PARENTHESIS:
        return  calc_expr_in_brackets       (s_inp, s_out, res);
    case P_SYMB:
        return  calc_p_expr                 (s_inp, s_out, res);
    default:
        return  calc_scalar                 (s_inp, s_out, res);
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_minus_factor
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{    
    bool   bool_res =    calc_minus  (s_inp, s_out)
                      && calc_factor (s_out, s_out, res);
    res *= -1;
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_expr_in_brackets
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{
    return     calc_left_parenthesis  (s_inp, s_out)
            && calc_expr              (s_out, s_out, res)
            && calc_right_parenthesis (s_out, s_out);
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_p_expr
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{
    bool  bool_res = calc_p_symb(s_inp, s_out);
    if(bool_res)
    {
        int  p_degree_val = 1;
        if( calc_pow_symb(s_out, s_out) )
        {
            bool_res = calc_num(s_out, s_out, p_degree_val);
            if(bool_res)
            {
                res.set_x_with_degree(p_degree_val);
            }
        }
        else
        {
            res.set_x_with_degree(p_degree_val);            
        }
    }
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_scalar
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{
    T_num  num_val   = 0;
    bool   bool_res  = calc_num(s_inp, s_out, num_val);
    if(bool_res)
    {
        res.set_scalar(num_val);
    }
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_minus(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(MINUS_SIGN, s_inp, s_out);
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_left_parenthesis(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(LEFT_PARENTHESIS, s_inp, s_out);
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_right_parenthesis(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(RIGHT_PARENTHESIS, s_inp, s_out);
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_p_symb(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(P_SYMB, s_inp, s_out);
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_pow_symb(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(POW_SYMB, s_inp, s_out);
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_num
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_num&        res
    )
{
    std::istringstream  sin(s_inp);    
    bool  bool_res = ((sin >> res) != 0);
    sin >> s_out;
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_subtract_summand
    (
        const T_str&  s_inp, 
        T_str&        s_out, 
        T_polynom&    res
    )
{    
    T_polynom  res_summand;
    bool   bool_res =     calc_minus   (s_inp, s_out)
                       && calc_summand (s_out, s_out, res_summand);
    res -= res_summand;
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_calculator::calc_plus(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(PLUS_SIGN, s_inp, s_out);
}
/////////////////////////////////////////////////////////////////////////////////////////
T_str  T_calculator::get_polynom_str(const T_polynom&  polynom)
{    
    T_str  res_str;
    for(int  i = polynom.get_degree(); i >= 0; --i)
    {
        std::ostringstream  sout;
        if(polynom[i] > 0)
        {
            sout << '+';
        }
 
        if(     polynom[i] == -1
            &&  i > 0           )
        {
            sout << '-';
        }
 
        if(    (   polynom[i]
                || i == 0 && res_str.empty() )
            &&
               (   abs(polynom[i]) != 1
                || i == 0 )
          )
        {
            sout << polynom[i]; 
            if(i > 0)
            {
                sout << '*';
            }
        }
 
        if(   polynom[i]
           && i > 0     )
        {
            sout << 'p';
            if(i != 1)
            {
                sout << '^'
                     << i;
            }
        }   
        res_str += sout.str();    
    }
    if(   !res_str.empty()
       && res_str[0] == '+')
    {
        res_str = res_str.substr(1);    
    }
    return  res_str;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_calculator::T_calculator()
{                      
    std::cout << "-> ";
    T_str  s_inp;
    std::getline(std::cin, s_inp);
    if(s_inp.empty()) exit(0);
    remove_spaces(s_inp);
    T_str      s_out; 
    T_polynom  res;
    if(    calc_expr(s_inp += FINISH_SYMB, s_out, res)
        && s_out == T_str(1, FINISH_SYMB)   )
    {
        std::cout << "Результирующий полином: "
                  << std::endl
                  << get_polynom_str(res);               
    }
    else
    {
        std::cout << "Выражение некорректно.";
    }
 
    std::cout << std::endl
              << std::endl
              << std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{ 
    std::locale::global(std::locale(""));
    for(;;)
    { 
        T_calculator  calculator;        
    }   
}
 
Текущее время: 06:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru