Калькулятор Алгоритм - использование итерации вместо рекурсии в двоичном дереве поиска

Question

Я видел подходы к тому, как итерации через двоичные деревья и найти сумму всех узлов, за исключением того, что я оцениваю входы выражений для калькулятора. Узлы расположены в правильном порядке в соответствии с порядком операций, а узлы - либо operators, либо operands. Я думаю, что recursion медленнее, чем итерация для этого, поэтому я хотел выяснить, как пройти через двоичное дерево и найти результат выражения, введенного без recursion.

Пример дерева:

 + 
    *  /
3 4 4 2 

Рекурсивный метод, который я до сих пор (я использовал перечисление для оператора):

public static float evaluate(BETNode root) 
{ 
    if (root == null) 
    { 
     throw new IllegalArgumentException("Error: Root is null!"); 
    } 

    if (root.getType() == BETNodeType.OPERAND) 
    { 
     return root.getOperand(); 
    } 

    float leftValue = evaluate(root.getLeft()); 
    float rightValue = evaluate(root.getRight()); 

    switch (root.getOperator()) 
    { 
     case '+': 
      return leftValue + rightValue; 

     case '-': 
      return leftValue - rightValue; 

     case '*': 
      return leftValue * rightValue; 

     case '/': 
      return leftValue/rightValue; 
    } 

    throw new IllegalArgumentException("Error."); 
} 

Answer 1

Как я уже говорил в моем комментарии выше, если ты iterative post-order traversal, вы получите узлы в следующем порядке:

3, 4, *, 4, 2, /, +.

От этого вам просто понадобится стек для оценки выражения.

Push 3 
Push 4 
Push (pop() * pop()) 

Push 4 
Push 2 
Push (pop()/pop()) 
Push (pop() + pop()) 
//Result 

Также интересно было бы Shunting Yard Algorithm, который делает оценку из выражения инфиксной.