3

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

На вход подается строка вида: "9+2-(4*2)"

Результат:

  1. 4*2 = 8
  2. 9+2 = 11
  3. 11-8 = 3

Стоит отметить, что нужен именно "школьный" порядок действий, то есть такой, какому нас обучают в начальных классах. Именно поэтому первое действие не сложение, а умножение. Важно, чтобы парсер был устойчив к выражениям, что называется "из головы" Читал про алгоритм польской обратной записи, но так и не понял, как всё-таки оформить в таком виде, как я описал. Задачи просто вычислить выражение не стоит, обойтись без использования eval (разве что, только для простых действий), главное это разобрать сложное выражение на простые действия.

1
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – A K
    30 июн 2020 в 20:35

1 ответ 1

4

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

т.е. выражение

(1+2*3)*((3+3*3)*2)+3
разбилось бы на 
A*B+3
где 
A = 1+2*3
B = (3+3*3)*2
B затем будет разбито на B1*2, где
B1 = 3+3*3

затем получившиеся  строки обрабатывал бы в порядке приоритетов математических операций
и записывал бы в следующую структуру (Операция,N1,N2) 
например строка 1+2*3 в итоге вылилась бы
A=[+, 1, (*, 2, 3)]
буду чередовать скобки, что бы не запутаться 
B1 = [+, 3, (*, 3, 3)]
B = (*, B1, 2)

а итоговое выражение получается таким:
A * B + 3 = [+, (*, A, B), 3]
= [+, (*, [+, 1, (*, 2, 3)], (*, [+, 3, (*, 3, 3)], 2)), 3]

По сути мы таким образом построили бинарное дерево операций, в которой операция является узлом
а операторы N1 и N2 являются ветками

При желании потом, можно оптимизировать эту структуру, например 2 * 2 * 2 = ( *, [ *, 2, 2], 2) = можно привести к виду (*, 2, 2, 2)

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.