|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
Добрый день! Есть замечательный сайт, где можно ввести любое алгебраическое выражение и программа может раскрыть скобки или наоборот вынести общий множитель за скобки . Т.е. вводим, к примеру, вот такую строку для раскрытия скобки: (a^2 + 3*a*b + 4*b^2)*(-2*a^2 + 14*b^2) и получаем следующую строку: - 2•a4 - 6•a3•b + 6•a2•b2 + 42•a•b3 + 56•b4 Программа работает просто отлично, но есть одно маленькое ограничение: алгебраическое выражение не должно превышать 256 символов, а мне этого не достаточно. Я часто имею дело с выражениями более 1000 символов, поэтому хочу создать хранимую процедуру в SQL Server’е (здесь вместо массива можно использовать табличную переменную, которую можно и фильтровать, и сортировать, в общем очень и очень даже удобный инструмент). Что я пробовал? Пока что начал с простейшего примера. Выражения с "+" или "–" без скобок беру и обрабатываю вот таким образом. Код: sql 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.
Теперь запускаю процедуру и получаю ответ. Код: sql 1.
Ответ: 49*a^2*b*c - 3*d^3*e Теперь мне надо усложнить задачу: добавить скобки и умножить (или делить) выражения, а в некоторых случаях даже возводить на определенную степень (только на целые числа, рациональные степени не рассматриваю). В интернете много пишут про обратную польскую нотацию (ОПН), но как им пользоваться пока не совсем понял. Приведу вот такой пример с числами (для наглядности): 5+(7-(3+4)*2)*(2+2*2) По идее программа должна плюсовать 3+4 в первую очередь, ну и дальше по алгоритму. Вот как написать это в процедуре? Прочел несколько статей про ОПН. Мне не понятно как же грамотно собрать в стек (я так понимаю отдельный столбец отдельной таблицы) а потом по приоритету выстроить алгоритм. Спасибо заранее за подсказку / наводку и за прочую помощь. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 09:20 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
studieren, С ОПН вам нужно строить дерево, а не стек. Открывающая скобка - создаем дочернюю ноду, закрывающая - возвращаемся на уровень выше. Как-то так. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 10:40 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
studieren В интернете много пишут про обратную польскую нотацию (ОПН), но как им пользоваться пока не совсем понял. Алгоритмы и методы: Обратная польская запись (исходники) studieren, А зачем это вообще ? "Глобальная цель" какая ? Случайно, не вычислить выражение заданное строкой ? (не упростить выражение с параметрами, а именно вычислить) ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 11:19 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
Ennor Tiegael studieren, С ОПН вам нужно строить дерево, а не стек. Открывающая скобка - создаем дочернюю ноду, закрывающая - возвращаемся на уровень выше. Как-то так. Мне не совсем понятно как это на практике выглядит. Вы можете показать самый простейший пример? Мне бы саму идею понять как это реализовать. court ... А зачем это вообще ? "Глобальная цель" какая ? Случайно, не вычислить выражение заданное строкой ? (не упростить выражение с параметрами, а именно вычислить) Для решения некоторых сложных математических задач, а именно Диафантово уравнения. Сейчас вручную решаю в MS Excel. Что же касается Вашей ссылки, то я к сожалению не знаю С++. Подобного рода статей перечитал, но так и не понял как реализовать. К примеру в той же статье пишут, что выражение a + ( b - c ) * d следует превращать на a b c - d * +. Допустим, так. Как теперь программе объяснить из выражения a b c - d * +, что сначала нужно вычислить b - c, потом умножить на d и только потом добавить а? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 13:23 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
Идея ОПЗ для меня более менее понятнее стала после чтения Wikipedia: Обратная польская запись . Там приводится пример: берём запись 3 + 4 * 2 / (1 - 5)^2 и превращаем на 3 4 2 * 1 5 - 2 ^ / +. Если я понял правильно, то полученную запись я читаю заново слева направо. Беру первые 3 символа: 3 4 2, здесь нет знака. Значит пропускаю. Беру следующие 3 символа 4 2 *, здесь есть знак, умножаю и получаю 8, после чего в записе заменяю 4 2 * на 8 и получаю 3 8 1 5 - 2 ^ / +. Опять до первого получения знака читаю слева направа и дохожу до 1 5 -. Получаю -4 и сразу заменяю. Затем по тому же сценарию воздвигаю во 2-степень и т.д. Вот теперь вся логика стала понятнее для меня. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 14:29 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
studieren Идея ОПЗ для меня более менее понятнее стала после чтения Wikipedia: Обратная польская запись . Там приводится пример: берём запись 3 + 4 * 2 / (1 - 5)^2 и превращаем на 3 4 2 * 1 5 - 2 ^ / +. Если я понял правильно, то полученную запись я читаю заново слева направо. Беру первые 3 символа: 3 4 2, здесь нет знака. Значит пропускаю. Беру следующие 3 символа 4 2 *, здесь есть знак, умножаю и получаю 8, после чего в записе заменяю 4 2 * на 8 и получаю 3 8 1 5 - 2 ^ / +. Опять до первого получения знака читаю слева направа и дохожу до 1 5 -. Получаю -4 и сразу заменяю. Затем по тому же сценарию воздвигаю во 2-степень и т.д. Вот теперь вся логика стала понятнее для меня. хорошо что в только целые числа бывают ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 14:42 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
studieren Допустим, так. Как теперь программе объяснить из выражения a b c - d * +, что сначала нужно вычислить b - c, потом умножить на d и только потом добавить а? т.е. вернуть "польскую запись" обратно, к "нормальному" виду и вычислить ? А зачем тогда было вообще к ней, к ОПЗ преобразовывать ?? а вообще, как-то так Код: sql 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.
v((d*(c-b))+a) result5 ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 14:53 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
TaPaK хорошо что в только целые числа бывают Это же всего лишь простой пример для нагладности. На практике не только дробные числа могут быть, но и неизвестные буквенные переменные. Вот там мне придётся решать более сложную проблему. :) Я просто до этого сам принцип ОПЗ не понимал, до меня только дошло. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 14:58 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
court, Спасибо за пример. Я с числами оперировал только для наглядности. На самом же деле я в основном буду работать с алгебраическими выражениями. Чаще буквами, а не числами. Числа у меня будут появляться в основном в качестве коэффициента или показателя степени. Если бы речь шла только о калькуляции, то конечно же я воспользовался бы динамическим запросом. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 15:04 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
Что-то я рано радовался. ОПЗ с числами хорошо работает, но вот как быть с буквами? Пока у меня не получается. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.06.2020, 15:51 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
studieren, Парзер выражений на MSSQL? Это что-то совершенно не от мира сего. БД явно не для этого предназначена. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.06.2020, 09:32 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
обычно инструмент подбирается под задачи, в данном случае больше похоже на натягивание совы на глобус задачи на инструмент (хотя и желание держать всё в пределах одной технологии архитектурно оправданно) кроме того если уж выбран путь с хранимыми процедурами - то на порядок легче и гибче по функциональности будет использовать уже давно интегрированные в MSSQL средства: CLR (C#/VB/C++ ..), а так-же с недавнего времени ML/DS: Python, Java, R (через sp_execute_external_script) где есть достаточно пакетов и для числовой и для символьной математики. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.06.2020, 15:37 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
studieren Идея ОПЗ для меня более менее понятнее стала после чтения Wikipedia: Обратная польская запись . Там приводится пример: берём запись 3 + 4 * 2 / (1 - 5)^2 и превращаем на 3 4 2 * 1 5 - 2 ^ / +. Если я понял правильно, то полученную запись я читаю заново слева направо. Беру первые 3 символа: 3 4 2, здесь нет знака. Значит пропускаю. Беру следующие 3 символа 4 2 *, здесь есть знак, умножаю и получаю 8, после чего в записе заменяю 4 2 * на 8 и получаю 3 8 1 5 - 2 ^ / +. Опять до первого получения знака читаю слева направа и дохожу до 1 5 -. Получаю -4 и сразу заменяю. Затем по тому же сценарию воздвигаю во 2-степень и т.д. Вот теперь вся логика стала понятнее для меня. Как уже написали - дерево надо строить и потом его обходить. Я делал такое. Это лучший вариант. В ваших выражениях есть скобки, операции с приоритетом, потом вы не указали, но еще в вашем случае есть унарные операции. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.06.2020, 08:39 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
Ролг Хупин, Можете показать хотя бы маленький пример? Я что-то не пойму как в данном случае можно построить дерево. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2020, 19:40 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
studieren Ролг Хупин, Можете показать хотя бы маленький пример? Я что-то не пойму как в данном случае можно построить дерево. нефиг делать Типичная ветка: операнд-операция-операнд a+b*c ================= + / \ a * /\ b c и т.д. Но, я никоим орбазом не хотел бы вас сбивать с направления: сделать парсер на T-SQL Без этого ветка станет пресной ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2020, 16:43 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
Здесь от алгебры только название темы, тем более, что означает "алгебраическое выражение" - загадка. Вот тут есть какая-то реализация http://vicking.narod.ru/articles/exprparser.htm вникните, перепишите и просьба: покажите результат здесь, он наверняка будет полезен будущим читателям форума. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2020, 16:55 |
|
Алгебраическое выражение
|
|||
---|---|---|---|
#18+
studieren Идея ОПЗ для меня более менее понятнее стала после чтения Wikipedia: Обратная польская запись . Там приводится пример: берём запись 3 + 4 * 2 / (1 - 5)^2 и превращаем на 3 4 2 * 1 5 - 2 ^ / +. Если я понял правильно, то полученную запись я читаю заново слева направо. Беру первые 3 символа: 3 4 2, здесь нет знака. Значит пропускаю. Беру следующие 3 символа 4 2 *, здесь есть знак, умножаю и получаю 8, после чего в записе заменяю 4 2 * на 8 и получаю 3 8 1 5 - 2 ^ / +. Опять до первого получения знака читаю слева направа и дохожу до 1 5 -. Получаю -4 и сразу заменяю. Затем по тому же сценарию воздвигаю во 2-степень и т.д. Вот теперь вся логика стала понятнее для меня. Попробовал создать ХП, где работает ОПЗ с числовыми выражениями (правда только простые арифметические операции ^ * / + -, другие функции такие как тригонометрические, логарифмические и пр. проигнорировал). Мне необходимо было сначала понять механизм ОПЗ. Код: sql 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.
Вроде как работает. Правда какой-либо баг возможно прозевал. Дальше. Теперь нужно было тоже самое, но только с буквами сочинить ХП. Получилось слишком грамоздка, работает медленовато, да и куча багов. Пока у меня совсем не получается с делением. Тут у меня пока совсем нет идей как решить деление. Код: sql 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.
Хранимка не работает со всеми математическим функциями кроме как арефматическими, воздвигать в степень можно только на натуральное число. Проблема №1. не правильно работает деление Проблема №2. очень и очень не оптимальное решение, слишком грамоздко. Проблема №3. хотелось красиво упорядочивать выражение (в смысле сначала "a" с наибольшей степени, а потом в порядке убывание как принято у математиков, но тоже пока без идей). Примеры: Код: sql 1.
Результат: -2*a*b^3+2*a^3*b+a^4-b^4 А вот так ошибка! Код: sql 1.
4+6*a+3*a^2*b/a+3*a^2*b/b Если есть у кого-то совет как упростить и улучшить, решить проблемы, буду очень признателен. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.07.2020, 19:01 |
|
|
start [/forum/topic.php?fid=46&msg=39968596&tid=1685917]: |
0ms |
get settings: |
11ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
47ms |
get topic data: |
14ms |
get forum data: |
3ms |
get page messages: |
65ms |
get tp. blocked users: |
2ms |
others: | 287ms |
total: | 451ms |
0 / 0 |