С помощью дерева разбора арифметического выражения, как сгенерировать инфиксное выражение как результат в Haskell - PullRequest
Новая
       19

С помощью дерева разбора арифметического выражения, как сгенерировать инфиксное выражение как результат в Haskell

0 голосов
/ 13 марта 2011

Вот определение дерева: data Tree = Leaf Char | Node (Char, Tree, Tree)

Я хочу написать функцию treeToInfix в виде: 

treeToInfix :: Tree -> String

Вот несколько примеров: 

treeToInfix (Node ('*', (Node ('+', (Leaf 'a'), (Leaf 'b'))), (Leaf 'c'))) 
-- =>  "(a+b)*c"

treeToInfix (Node ('-', (Node ('+', (Leaf 'a') ,(Leaf 'b'))), (Leaf 'c')))
-- =>  "a+b-c"

treeToInfix (Node ('-', (Leaf 'c'), (Node ('+', (Leaf 'a') ,(Leaf 'b')))))
-- =>  "c-(a+b)"

treeToInfix (Node ('*', (Node ('/', (Leaf 'a'), (Leaf 'b'))), (Node ('/', (Leaf 'c'), (Leaf 'd'))))) 
-- =>  "a/b*c/d"

treeToInfix (Node ('+', (Node ('-', (Leaf 'a'), (Node ('*', (Leaf 'b'), (Leaf 'c'))))), (Node ('/', (Leaf 'd'), (Leaf 'e'))))) 
-- =>  "a-b*c+d/e"

Мне нужна помощь по алгоритму этой программы.

Ответы [ 2 ]

1 голос
/ 14 марта 2011

Учитывая, что это выглядит как домашнее задание, я просто даю общее представление. Каждый оператор имеет приоритет (и, возможно, ассоциативность). Это можно выразить просто как число. Таким образом, идея состоит в том, чтобы напечатать ассоциативность контекста в качестве дополнительного параметра. Так что ваша функция может выглядеть так: 

treeToInfix :: Tree -> String
treeToInfix tr = treeAux 0 tr


treeAux :: Int -> Tree -> String
treeAux prec (Node ("+",left,right)) = 
  -- TODO:
  --   * let's say precedence of '+' is 5
  --   * generate strings for children (with prec = 5)
  --   * put "+" in between
  --   * if prec > 5, put parantheses around the result
-- Similar for other cases

Вы даже можете реализовать ассоциативность, изменив приоритет, передаваемый рекурсивным вызовам.

0 голосов
/ 14 марта 2011

Ну, если подумать, каждый этап операции должен быть:

  1. генерировать строку для левого операнда
  2. генерировать строку для оператора
  3. сгенерировать строку для правого операнда
  4. склеить их все вместе в правильном порядке

Обратите внимание, что генерация строки для левого и правого операндов - это просто еще одно приложение вашего дерева к функции строки,так что вы можете кодировать это рекурсивно.Ваш базовый случай, который вы не определили рекурсивно, будет состоять в том, как отобразить Leaf.

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

Достаточно ли этого помочь?Я старался не давать вам код на случай, если это домашнее задание.Я также предположил, что вы понимаете рекурсию, так как это ключевой навык в Haskell.Если вы не понимаете рекурсию, дайте мне знать, и я напишу больше.

...