Как удалить скобки в математическом выражении?

Question

[Nulltiton]

Необходимо написать приложение, которому на вход будет поступать математическое выражение с лишними скобками, а удалить необходимо только незначащие скобки.
Например: (((A*B)+C)+(C+D))*E -> (A*B+C+C+D)*E или (A*B*C)*D)+E+F -> A*B*C*D+E+F. Нашел решение, где используются выражения только с + и -, но * и / не затрагивается. Подскажите, как написать подобный алгоритм?

Comments

[Nulltiton]

Написал следующий код, но не всегда выдает верно

exp_str = input('Input math expression: ')
mul_brack = []
div_brack = []
reserve = []
count = 0

#(a+(b-c))+(d+e)*f
#(((A*B)+C)+(C+D))*E
#(A*(B*C)*D)+E+F
#(A+B)*(C+D)/(E-F)


exp = list(exp_str)

for i in range(len(exp)):
    if exp[i] == '*':
        mul_brack.append(i)
    elif exp[i] == '/':
        div_brack.append(i)

for i in range(len(exp)):
    for j in range(len(mul_brack)):
        if i == mul_brack[j]:
            if exp[i-1] == ')':
                reserve.append(i-1)
                for k in range(i-1, 0, -1):
                    if exp[k] == '(':
                        reserve.append(k)
                        break

            elif exp[i+1] == '(':
                reserve.append(i+1)
                for k in range(i+1, len(exp)):
                    if exp[k] == ')':
                        reserve.append(k)
                        break
        
    for j in range(len(div_brack)):
        if i == div_brack[j]:
            if exp[i-1] == ')':
                reserve.append(i-1)
                for k in range(i-1, 0, -1):
                    if exp[k] == '(':
                        reserve.append(k)
                        break

            elif exp[i+1] == '(':
                reserve.append(i+1)
                for k in range(i+1, len(exp)):
                    if exp[k] == ')':
                        reserve.append(k)
                        break

#for i in range(len(exp)):
i = 0
while i != len(exp):
    if i == len(exp):
        break
    if exp[i] == '(' or exp[i] == ')':
        for j in range(len(reserve)):
            if i == reserve[j]:
                count += 1
        if count == 0:
            del exp[i]
            for j in range(len(reserve)):
                reserve[j] -= 1
            i = 0
        else:
            i += 1
        count = 0


    else:
        i += 1
for i in exp:
    print(i, end='')

(((A*B)+C)+(C+D))*E и (A+B)*(C+D)/(E-F) выдает неверно

[Nulltiton]

Заранее поясню, что писал быстро и код не рефакторил от слова совсем

Answer 1

[Wataru]

Самое надежное - распарсить выражение, построить Абстрактное Синтаксическое Дерево (это бинарное дерево, где вершина - операция, а два ребенка - операнды, которые могут быть или числом, или выражением).

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

Так, если вершина "+", то скобки ставить вообще не надо. Если вершина "*", то надо ставить скобки вокруг ребенка, если там операция "+" или "-". Если вершина "-", то надо ставить скобки справа, если там "+" или "-". Если вершина "/", то надо ставить скобки вокруг левого сына, если там "+" или "-". Вокруг правого сына скобки надо ставить если не число. Подумайте аккуратно, может я какие-то правила упустил.

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

Парсинг - очень заезженная тема. Гуглите. Самый простой алгоритм - квадртатичный - проходитесь по строке и ищите самую левую операцию с самым большим приоритетом вне скобок (ведя счетчик открытых скобок). Если такой нет, то можно опустить скобки по краям. Если их нет, то это число (или перменная). Если нашли операцию, то рекурсивно разбирайте две подстроки слева и справа.

Comments

[Alexandroppolus]

Надо порисовать на бумаге кучу случаев и аккуратно их разобрать.

они сводятся к таким правилам:
1) для левого поддерева нужны скобки, если у операции левого поддерева ниже приоритет, чем у текущей ноды (для листовой ноды считаем, что приоритет самый высокий)
2) для правого - как для левого, а так же, при равенстве приоритетов, если операция в левом поддереве неассоциативна.

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

[mayton2019]

Задача интересная. Она - балансирует на грани "сделать, не делая полноценный парсер грамматик"

Приходит на ум - конвертруть ее в ПОЛИЗ а потом обратно с восстановлением скобочек. Здесь
я хитро так расчитываю что польская технология поможет мне скипнуть скобочки за раз.

[Wataru]

mayton2019,

Она - балансирует на грани "сделать, не делая полноценный парсер грамматик"

Ну нет, для парсинга такого ограниченного арифметического выражения не надо полноценного парсера грамматик.

[mayton2019]

Я вот такую штуку нарисовал. И чего-то в голове крутится Lisp с его списками.

Вот. Смотреть на нее надо слегка шею свернув влево.

"+" -- "+"-- "D"
 |      |
 |     "C"
 |
"+"-- "C"
 |
"*"-- "B"
 |
"A

[Wataru]

mayton2019, Это называется Абстрактное синтаксическое дерево. В общем случае - да, надо грамматику парсить, но если у вас только арифметические операции и скобки, то разбирается элементарным алгоритмом за O(n^2), или чуть более хитрым за O(n).