Траверс/преобразование дерева выражений

Question

У меня есть дерево выражений, которое мне нужно пройти и сгенерировать определенную строку. Допустим, у меня есть это дерево

 OR 
    /\ 
    AND C 
/ \ 
A  B 

И я хочу, чтобы преобразовать его в:

(A AND B) OR C 

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

Answer 1

abstract class Expression { 
} 

class Binary extends Expression { 

    final String operator; 
    final Expression left, right; 

    Binary(String operator, Expression left, Expression right) { 
     this.operator = operator; 
     this.left = left; 
     this.right = right; 
    } 

    @Override 
    public String toString() { 
     return String.format("(%s %s %s)", left, operator, right); 
    } 
} 

class Variable extends Expression { 

    final String name; 

    Variable(String name) { 
     this.name = name; 
    } 

    @Override 
    public String toString() { 
     return name; 
    } 
} 

@Test 
public void testExpression() { 
    Expression e = new Binary("OR", new Binary("AND", new Variable("A"), new Variable("B")), new Variable("C")); 
    System.out.println(e); 
    // -> ((A AND B) OR C) 
} 

Answer 2

Самое простое решение печатает избыточные круглые скобки:

Visit(node): 
    Output "(" 
    If node.has_left(): 
    Visit(node.left) 
    Output node.label 
    If node.has_right(): 
    Visit(node.right) 
    Output ")" 

Чтобы исправить избыточную проблему скобку, присваивают каждому оператору лево- и приоритет, так же, как и в операторной старшинства разборе, и передают родителям приоритет узла в посещении. Затем посещение выводит круглые скобки только в том случае, если приоритет посещенного узла ниже, чем переданный по приоритету от родительского узла.