Разбор математических выражений

@Morak · Регистрация: 24.10.2010

Студворк — интернет-сервис помощи студентам

Добрый день, нуждаюсь в вашей помощи. Написал код программы для решения определённого уравнения методом половинного деления. Необходимо доработать код, чтобы можно было вводить и само уравнение с клавиатуры.
Задание (В данной работе необходимо учесть, что программа должна подходить для решения не только приведенного в условии задачи уравнения и заданных для него интервалов, но для других уравнений данного класса. Для отладки рекомендуется использовать квадратное уравнение, корни которого определены аналитическим способом.)

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
#include <iostream>
#include <cmath>
#include <locale.h>
using namespace std;
float f(float X)
{   
    return pow(2,X*X+1)+X*X-4;
}
bool BinarySearch(float A, float B, float E, float &res)
{
    if(f(A)*f(B)>0)
        return false;
    float X = (B+A)/2;
    while (fabs(f(X)) > E)
    {
        if (f(A)*f(X) < 0)
            B=X;
        else
            A=X;
        X=(B+A)/2;
    }
    res=X;
    return true;
}
int main()
{
    setlocale(LC_ALL,"Russian");
    float res, a, b, e;
    cout <<"Введите положение точки А, B, точность Е через <пробел> :"<<endl;
    cin>>a>>b>>e;
    if(BinarySearch(a, b, e, res)==true)
        cout<<"Корень уравнения x="<<res<<endl;
    else
        cout<<"So sad, try again"<<endl;
    return 0;
 
}

@taras atavin · 24.10.2010, 09:50

Сообщение от Morak

Необходимо доработать код, чтобы можно было вводить и само уравнение с клавиатуры.

Тогда название темы не удачно, её надо обозвать "модуль разбора математических выражений", так как именно эту подзадачу ты и поставил. О декомпозиции слышал? Программой называется запись алгоритма на понятном компьютеру, в том числе посредством машинного перевода, языке. А алгоритмом последовательность операций для получения требуемого результата, то есть способ решения задачи. Отсюда любая программа решает какую нибудь задачу. Исключений нет. Даже если программа - компьютерная игра, то "развлечь пользователя" - тоже задача. Сложные же задачи делятся на подзадачи, это деление называется декомпозицией. В программе каждую подзадачу решает подпрограмма. И если ты одну часть своей задачи уже решил сам, то нафиг перед помощниками ставить задачу глобально? Тебе нужна подпрограмма, которая по значению аргумента и введённому с клавиатуры выражению будет считать его значение, это и есть модуль разбора. Какие требования к нему предъявляются? Требуется ли разбор только полиномов? Арифметические выражения со скобками? Выражения, содержащие функции и арифметические операции? Требуется ли поддерживать степень? А унарный минус? Унарный плюс?

@Morak · 24.10.2010, 10:00 **[ТС]**

Спасибо за столь грамотный ответ и поправки моих косяков, данное задание написано ниже и пример самого уравнения, если вы не заметили. Обратился на форум, потому что сам не представляю как это сделать.

Сообщение от Morak

но для других уравнений данного класса. Для отладки рекомендуется использовать квадратное уравнение, корни которого определены аналитическим способом.

пример уравнения: (2,X*X+1)+X*X-4.

@taras atavin · 24.10.2010, 11:06

Предлагаю через суффиксную нотацию:
1. Считаем элементы исходного выражения, за исключением скобок.
В выражении:
(2*x^2+1)+x^2-4 элементами будут: 2, *, x, ^, 2, +, 1, +, x, ^, 2, - 4. Всего 13.
2. Создаём массив элементов такого размера.
3. Заполняем его в прямом порядке:
2, *, x, ^, 2, +, 1, +, x, ^, 2, - 4.
4. С операторами ассоциируем базовые приоритеты:
2, *, x, ^, 2, +, 1, +, x, ^, 2, - 4.
2 3 1 1 3 1
5. После каждой открывающейся скобки повышаем приоритеты на 3 до следующей закрывающей:
2, *, x, ^, 2, +, 1, +, x, ^, 2, - 4.
5 6 4 1 3 1
6. Все операторы проталкиваем вперёд на 1 шаг:
2, x, *, 2, ^, 1, +, x, +, 2, ^, 4, -
5 6 4 1 3 1
7. В цикле по операторам от первого до предпоследнего проталкиваем каждый оператор, находящийся перед оператором с большим приоритетом вперёд, пока следующий за ним не будет иметь меньший приоритет:
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
6 5 4 3 1 1
8. Готово.
Теперь расчёт. Пусть x=3, Понадобится стек, сначала он пуст. Красным крашу до текущей позиции.
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
константу в стек:
2
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
значение переменной в стек:
2
3
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
константу в стек:
2
3
2
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
извлекаем два элемента, возводим один в степень другого и результат помещаем в стек:
2
9
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
извлекаем два элемента и помещаем в стек их произведение:
18
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
константу в стек:
18
1
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
извлекаем два элемента и сумму помещаем в стек:
19
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
значение переменой в стек:
19
3
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
константу в стек:
19
3
2
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
извлекаем два элемента, возводим один в степень второго, результат помещаем в стек:
19
9
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
извлекаем два элемента, их сумму помещаем в стек:
28
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
константу в стек:
28
4
2, x, 2, ^,*, 1, +, x, 2, ^, +, 4, -
извлекаем два элемента, вычитаем один из другого, результат помещаем в стек:
24
Достигнут конец выражения, извлекаем элемент стека и возвращаем в качестве значения выражения.

@Morak · 24.10.2010, 14:44 **[ТС]**

Cпасибо большое, попробую воспроизвести на С++

Добавлено через 17 минут

Сообщение от Morak

Cпасибо большое, попробую воспроизвести на С++

Хотя со стеками пока не знаком

(( придётся повозиться.

Добавлено через 44 минуты

Сообщение от Morak

Cпасибо большое, попробую воспроизвести на С++

Добавлено через 17 минут

Хотя со стеками пока не знаком

(( придётся повозиться.

Это как-нибудь проще реализовать можно? )))) что-то у меня не получается

Добавлено через 2 часа 25 минут
Ну подскажите ещё кто-нибудь.

@taras atavin · 25.10.2010, 06:43

Ещё можно рекурсивно через дерево подвыражений:
выражение
(2*x^2+1)+x^2-4
есть сумма подвыражений:
2*x^2+1
и
x^2-4
подвыражение 2*x^2+1
есть сумма подвыражений
2*x^2
и
1
подвыражение
x^2-4
есть разность подвыражений
x^2
и
4
подвыражение
2*x^2
есть произведение подвыражений
2
и
x^2,
подвыражение
1
есть отдельный элемент
подвыражение
x^2
есть подвыражение
x
в степени подвыражения
2
подвыражение
4
есть отдельный член
подвыражение
x
есть отдельный член.
Читай "Теорию и практику C++" Герберта Шилдта. Но по-моему этот способ сложней формализовать для машины, хотя вручную большинство именно так и делает.

Добавлено через 1 час 11 минут

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
double SubstringToDouble (char *s, char *e)
{
 double Result;
 double m;
 boolean f;
 char *p;
 Result=0.0;
 m=1.0;
 f=true;
 for (p=s; p<e; ++p)
 {
  switch (*p)
  {
   case '0':
   case '1':
   case '2':
   case '3':
   case '4':
   case '5':
   case '6':
   case '7':
   case '8':
   case '9':
    if (f)
    {
     Result*=10.0;
    }
    else
    {
     m/=10.0;
    }
    Result+=m*((*p)-'0');
   break;
   case ',':
    f=false;
   break;
  }
 } 
 return Result;
}
enum TItemCind {ticConstant, ticX, ticOperator, ticNoTranslate};
struct TOperatorItem
{
 char Cind;
 int   Rrioritet;
};
union TItemParametr
{
 double Value;
 TOperatorItem Operator;
};
struct TItem
{
 TItemCind Cind;
 TItemParametr Parametr;
};
double Calc (char *s, double x)
{
 int n;
 TItem *Suf;
 TItem *Temp;
 TItem *i;
 double x1;
 double x2;
 TItemCind Cind;
 TItemCind Old;
 char *p;
 char *Start; 
 int     Base;
 TItem *End;
 TItem *Next;
 TDoubleStack Stac;
 for (n=0,p=s, Old=ticNoTranslate;*p!=0;++p)
 {
  Cind=ticNoTranslate;
  switch (*p)
  {
   case '0':
   case '1':
   case '2':
   case '3':
   case '4':
   case '5':
   case '6':
   case '7':
   case '8':
   case '9':
   case ',': Cind:=ticConstant;
   break;
   case '+':
   case '-':
   case '*':
   case '/':
   case '^':Cind=ticOperator;
   break;
   case 'x':
   case 'X':cind=ticX;
   break;
  }
  if (Cind!=Old)
  {
   +n;
  }
  Cind=Old;
 }
 Suf=new TItem [n];
 for (Base=0, n=0, p=s, Start=s, i=Suf, Old=ticNoTranslate; *p!=0; ++p)
 {
  Cind=ticNoTranslate;
  switch (*p)
  {
   case '0':
   case '1':
   case '2':
   case '3':
   case '4':
   case '5':
   case '6':
   case '7':
   case '8':
   case '9':
   case ',': Cind:=ticConstant;
   break;
   case '+':
   case '-':
   case '*':
   case '/':
   case '^':Cind=ticOperator;
   break;
   case 'x':
   case 'X':cind=ticX;
   break;
   case '(':base+=3;
   case ')':base-=3;
  }
  if (cind!=Old)
  {
   i->Cind=old;
   switch (Old)
   {
    case ticConstant:
     i->Parametr.Value=SubStringToDouble(Strart,*p);
    break;
    case ticOperator:
     switch(*Old)
     {
      case '+':
       i->Parametr.Operator='+';
       i->Parametr.Prioritet=Base+1;
      break;
      case '-':
       i->Parametr.Operator='-';
       i->Parametr.Prioritet=Base+1;
      break;
      case '*':
       i->Parametr.Operator='*';
       i->Parametr.Prioritet=Base+2;
      break;
      case '/':
       i->Parametr.Operator='/';
       i->Parametr.Prioritet=Base+2;
      break;
      case '^':
       i->Parametr.Operator='^';
       i->Parametr.Prioritet=Base+3;
     break;
    }
   }
   ++i;
   Start=p;
  }
  Old=Cind;
 }
 End=Suf+n;
 for (i=End; i<End; --i)
 {
   if (i->Cind==ticOperator)
   {
    Temp=i;
    *i=*(i-1);
    *(i-1)=Temp;
   }
 }
 for (i=Suf; i<End; ++i)
 {
   if (i->Cind==ticOperator)
   {
    for (Next=i+1; Next<End; ++Next)
    {
     if (Next-Cind==ticOperator)
     {
      if (Next->Parametr.Prioritet>i->Parametr.Prioritet)
      {
        break;
      }
     }
     if (Next->Parametr.Prioritet>i->Parametr.Prioritet)
     {
      for (; i<Next; ++i)
      {
       Temp=*i;
       *i=*(i+1);
       *(i+1)=Temp; 
       }
      }
      i=Next+1;
     }
    }
   }
 }
 Stac.Clear();
 for (i=Suf; i<End; ++i)
 {
  switch (i->Cind)
  {
   case ticConstant:
    Stac.Push(i->Parametr->Value);
   break;
   case ticX:
    Stac.Push(x);
   break;
   case ticOperator:
    switch (i->Parametr.Operator)
    {
     case '+':
      x2=Stac.Pop();
      x1=Stac.Pop();
      Stack.Push(x1+x2);
     break; 
     case '-':
      x2=Stac.Pop();
      x1=Stac.Pop();
      Stack.Push(x1-x2);
     break;
     case '*':
      x2=Stac.Pop();
      x1=Stac.Pop();
      Stack.Push(x1*x2);
     break;
     case '/':
      x2=Stac.Pop();
      x1=Stac.Pop();
      Stack.Push(x1/x2);
     break;
     case '^':
      x2=Stac.Pop();
      x1=Stac.Pop();
      Stack.Push(x1^x2);
     break;   
    }
   break;
  }
 }
 retuern Stac.Pop(); 
}

Попробуй отладить это и сделай класс стека.

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 11.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 10.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	24.10.2010, 11:06
	Предлагаю через суффиксную нотацию: 1. Считаем элементы исходного выражения, за исключением скобок. В выражении: (2x^2+1)+x^2-4 элементами будут: 2, , x, ^, 2, +, 1, +, x, ^, 2, - 4. Всего 13. 2. Создаём массив элементов такого размера. 3. Заполняем его в прямом порядке: 2, , x, ^, 2, +, 1, +, x, ^, 2, - 4. 4. С операторами ассоциируем базовые приоритеты: 2, , x, ^, 2, +, 1, +, x, ^, 2, - 4. 2 3 1 1 3 1 5. После каждой открывающейся скобки повышаем приоритеты на 3 до следующей закрывающей: 2, , x, ^, 2, +, 1, +, x, ^, 2, - 4. 5 6 4 1 3 1 6. Все операторы проталкиваем вперёд на 1 шаг: 2, x, , 2, ^, 1, +, x, +, 2, ^, 4, - 5 6 4 1 3 1 7. В цикле по операторам от первого до предпоследнего проталкиваем каждый оператор, находящийся перед оператором с большим приоритетом вперёд, пока следующий за ним не будет иметь меньший приоритет: 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - 6 5 4 3 1 1 8. Готово. Теперь расчёт. Пусть x=3, Понадобится стек, сначала он пуст. Красным крашу до текущей позиции. 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - константу в стек: 2 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - значение переменной в стек: 2 3 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - константу в стек: 2 3 2 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - извлекаем два элемента, возводим один в степень другого и результат помещаем в стек: 2 9 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - извлекаем два элемента и помещаем в стек их произведение: 18 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - константу в стек: 18 1 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - извлекаем два элемента и сумму помещаем в стек: 19 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - значение переменой в стек: 19 3 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - константу в стек: 19 3 2 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - извлекаем два элемента, возводим один в степень второго, результат помещаем в стек: 19 9 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - извлекаем два элемента, их сумму помещаем в стек: 28 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - константу в стек: 28 4 2, x, 2, ^,, 1, +, x, 2, ^, +, 4, - извлекаем два элемента, вычитаем один из другого, результат помещаем в стек: 24 Достигнут конец выражения, извлекаем элемент стека и возвращаем в качестве значения выражения. 1