Двоичное дерево выражений C ++: как напечатать инфиксное выражение с соответствующими скобками?
Прямо сейчас у меня есть этот простой алгоритм печати, который печатает идеальные скобки. Проблема в том, что круглые скобки не всегда необходимы, и мне нужно выяснить, как не печатать их, когда они не нужны.
Моя текущая функция:
void printIn(Node* t){
if(t!= NULL) {
if(isleafNode(t))
cout << t->element;
else {
cout << "(";
printIn(t->left);
cout << t->data;
printIn(t->right);
cout << ")";
}
}
Проблема здесь в том, что некоторые постфиксные выражения, такие как
2 50 + 8 +
может быть напечатан в инфиксе как 2 + 50 + 8 вместо ((2 + 50) + 8))
Вот диаграмма postfix, чтобы вставить, как это должно выглядеть. Мой просто добавляет круглые скобки вокруг всего снаружи, и ко всему добавлению, несмотря ни на что.
4 50 6 + + 4 + ( 50 + 6 )
4 50 + 6 + 4 + 50 + 6
4 50 + 6 2 * + 4 + 50 + 6 * 2
4 50 6 + + 2 * ( 4 + ( 50 + 6 ) ) * 2
a b + c d e + * * ( a + b ) * ( c * ( d + e ) )
Вот диаграмма того, как мой выглядит:
4 50 6 + + ( 4 + ( 50 + 6 ))
4 50 + 6 + ( ( 4 + 50 ) + 6)
4 50 + 6 2 * + ( ( 4 + 50 ) + ( 6 * 2 ) )
4 50 6 + + 2 * ( ( 4 + ( 50 + 6 ) ) * 2 )
a b + c d e + * * ( ( a + b) * ( c * ( d + e ) ) )
Как я могу исправить свой алгоритм, чтобы убрать лишние скобки?
п
Имейте в виду, у меня есть функция getPrecedence (string), которая возвращает 1 для высокого приоритета (* или /) и 0 для низкого приоритета (+ или -)
Решение
При печати дерева выражений в инфиксной форме вам нужно печатать круглые скобки только вокруг подвыражений (то есть дочерних), где оператор имеет более низкий приоритет, чем оператор основного (то есть родительского) выражения.
В качестве примера возьмем следующее дерево выражений (в постфиксной нотации) и его инфиксную форму.
4 5 6 + 7 * + 4 + (5 + 6) * 7
Обратите внимание, что скобки нужны около 5 + 6, так как оператор подвыражения 5 6 + имеет более низкий приоритет, чем оператор основного выражения 5 6 + 7 *, но он не нужен для подвыражения 5 6 + 7 * поскольку оператор имеет более высокий приоритет, чем оператор основного выражения 4 5 6 + 7 * +
Используя эту информацию, легко изменить алгоритм в вопросе, чтобы избежать скобок, когда они не нужны. Обратите внимание, что, поскольку в дереве нет родительских указателей, проще сделать родительскую проверку, если какой-либо из дочерних элементов нуждается в круглых скобках, чем заставить узел помещать круглые скобки вокруг себя.
Другие решения
Других решений пока нет …