Отображение выражения postfix / prefix в виде дерева разбора с использованием C / C ++

Question

Я успешно преобразовал инфиксное выражение в постфиксное выражение, а также смог оценить постфиксное выражение, но я столкнулся с проблемой при создании дерева разбора для того же с C / C ++

Мой вывод:

           enter the expression string a+b*c
           the expression is correct
           the postfix expression is - abc *+
           enter the value of a-1
           enter the value of b-2
           enter the value of c-3
           the postfix expression is -abc*+
           result= 7

Мне также необходимо отобразить: Синтаксическое дерево

               +          
             /   \                                
          *       a                               
         /   \                                               
        b     c       

Любой отзыв будет очень полезен в моем проекте.

Спасибо в Adv.

@ LD: Спасибо за вашу постоянную помощь. Мне нужен псевдокод в turbo C. Я не знаю Ruby.

Answer 1

Гораздо проще "нарисовать" их следующим образом:

+
  a
  *
    b
    c

Или, если вы хотите использовать простую графику символов (я изменил операторы + и * на Add и Mul, чтобы избежать столкновения с графикой):

Add
+-- a
+-- Mul
    +-- b
    +-- c

Хитрость для этого - нарисовать поддерево отдельно (например, дерево mul), а затем нарисовать его с помощьюподходящие префиксы при рисовании внешнего дерева.

Фактически, если вы знакомы с потоковыми буферами C ++, вы можете создать потоковый буфер с префиксами, который обрабатывает префиксы, и просто распечатать внутреннее дерево.

Большая разница по сравнению с предложенным вами стилем заключается в том, что ваш стиль просто не масштабируется.Если, например, у верхнего оператора будет два больших поддерева, они были бы очень сильно отделены друг от друга.

РЕДАКТИРОВАТЬ: Можно нарисовать немного более сложное деревокак это:

Add
+---Sub
|    +---Div
|    |    +---p
|    |    +---q
|    +---y
+---Mul
     +---b
     +---c

РЕДАКТИРОВАТЬ: По запросу, здесь приходит некоторый псевдокод (который, кстати, приемлем для интерпретатора Ruby).Однако вы должны использовать подходящую структуру данных C ++ для представления дерева.

# Return the drawn tree as an array of lines.
#
# node ::= string
# node ::= [string, node, node]
def render_tree(node, prefix0 = "", prefix = "")
  if (node.is_a?(String))
    puts prefix0 + node         # Value
  else
    puts prefix0 + node[0]      # Operator
    render_tree(node[1], prefix  + "+---", prefix + "|    ")
    render_tree(node[2], prefix  + "+---", prefix + "     ")
  end
end
render_tree(["Add", ["Sub", ["Div", "p", "q"], "y"], ["Mul", "b", "c"]])