Вычисление значения бинарного дерева выражений

Question

У меня есть двоичный конструктор дерева, который будет принимать префикс обозначения в строке и в конечном итоге распечатать что-то вроде этого:

|-- * 
    |-- 2 
    |-- + 
     |-- 4 
     |-- + 
      |-- 6 
      |-- 7 

Приставка обозначения этого дерева является: (* 2 (+ 4 (+ 6 7))) Значение должно быть: 2 * 17 = 34. Я понимаю, что стеки используются при вычислении этих деревьев, но я не уверен, как это сделать.

Идея, что у меня есть, состоит в том, что есть два стека. Один для операторов и один для операндов. Когда вводятся два операнда, последний оператор вынимается, а новый операнд помещается туда?

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

Answer 1

Это очень просто:

int eval(tree) { 
    if tree is just a number return that number 
    else { 
     l = eval(tree.left) 
     r = eval(tree.right) 
     return result of operation on l and r 
    } 
} 

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

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

Answer 2

Насколько я понимаю, не обязательно иметь два стека. Если я правильно помню, алгоритм для оценки дерева может быть либо реализован рекурсивно, либо через стек - до тех пор, пока вершина стека является оператором, замените верхнюю часть стека на значение выражения соответствующего отпечатка. Я считаю, что этот подход связан с так называемой «польской записью» этого термина.