Калькулятор Haskell - порядок операций

Question

Я очень новичок в Haskell, и мне нужно сделать рабочий калькулятор, что даст ответы на выражения типа: 2 + 3 * (5 + 12) У меня есть что-то, что позволяет вычислить больше или меньше, но у меня проблема с порядком операций. Я понятия не имею, как это сделать. Вот мой код:

import Text.Regex.Posix 
import Data.Maybe 

oblicz :: String -> Double 
oblicz str = eval (Nothing, None) $ map convertToExpression $ (tokenize str) 


eval :: (Maybe Double,Expression)->[Expression]->Double 

eval (Nothing, _) ((Variable v):reszta) = eval (Just v, None) reszta 
eval (Just aktualnyWynik, None) ((Operator o):reszta) = eval ((Just aktualnyWynik), (Operator o)) reszta 



eval (Just aktualnyWynik, (Operator o)) ((Variable v):reszta) = eval (Just $ o aktualnyWynik v , None) reszta 


eval (aktualnyWynik, operator) (LeftParenthesis:reszta) 
    = eval (aktualnyWynik, operator) ((Variable (eval (Nothing, None) reszta)):(getPartAfterParentheses reszta)) 


eval (Just aktualnyWynik, _) [] = aktualnyWynik 
eval (Just aktualnyWynik, _) (RightParenthesis:_) = aktualnyWynik 

data Expression =  Operator (Double->Double->Double) 
        | Variable Double 
        | LeftParenthesis 
        | RightParenthesis 
        | None 

tokenize :: String -> [String] 
tokenize expression = getAllTextMatches(expression =~ "([0-9]+|\\(|\\)|\\+|-|%|/|\\*)" :: AllTextMatches [] String) 

convertToExpression :: String -> Expression     
convertToExpression "-" = Operator (-) 
convertToExpression "+" = Operator (+) 
convertToExpression "*" = Operator (*) 
convertToExpression "/" = Operator (/) 
convertToExpression "(" = LeftParenthesis 
convertToExpression ")" = RightParenthesis 
convertToExpression variable = Variable (read variable) 

getPartAfterParentheses :: [Expression] -> [Expression] 
getPartAfterParentheses [] = [] 
getPartAfterParentheses (RightParenthesis:expressionsList) = expressionsList 
getPartAfterParentheses (LeftParenthesis:expressionsList) = getPartAfterParentheses (getPartAfterParentheses expressionsList) 
getPartAfterParentheses (expression:expressionsList) = getPartAfterParentheses expressionsList 

Я думал, может быть, я мог бы создать два стека - один с номерами и один с операторами. Читая выражение, я мог бы нажимать числа на один стек, а операторы - на другой. Когда это оператор, я бы проверил, есть ли что-то уже в стеке, и если есть проверка, следует ли мне поместить его из стека и выполнить математику или нет - точно так же, как в нотации onp.

К сожалению, как я уже сказал, я ОЧЕНЬ новичок в haskell и понятия не имею, как это писать.

Любые намеки или помощь будет приятно :)

Answer 1

Раздвигая вещи на разных стеков конечно чувствует очень большое prcedural вещь, чтобы сделать, и это вообще не приятно в Haskell. (Стеки могут быть реализованы в виде списков, которые работают довольно хорошо чисто функционально. Даже реальное изменяемое состояние может быть прекрасным, если только в качестве оптимизации, но если одновременно нужно изменить несколько объектов, то это не совсем приятный.)

Предпочтительным способом было бы создать дерево , представляющее выражение.

type DInfix = Double -> Double -> Double -- for readability's sake 

data ExprTree = Op DInfix ExprTree ExprTree 
       | Value Double 

Оценка этого дерева в основном evalTree (Op c t1 t2) = c (evalTree t1) (evalTree t2), т.е. ExprTree->Double сразу.

Чтобы построить дерево вверх, решающий момент: получите ошибки оператора справа. Различные операторы имеют различную фиксацию. Я бы поставил эту информацию в Operator поле:

type Fixity = Int 
data Expression = Operator (Double->Double->Double) Fixity 
       | ... 

, который затем требует, например,

... 
convertToExpression "+" = Operator (+) 6 
convertToExpression "*" = Operator (*) 7 
... 

(Это те, что само по себе ассоциативности и приоритетов Haskell имеет для операторов. Вы можете :i + в GHCi, чтобы увидеть их.)

Тогда вы бы построить дерево.

toExprTree :: [Expression] -> ExprTree 

Очевидные базовый случай:

toExprTree [Variable v] = Value v 

Вы можете продолжить

toExprTree (Variable v : Operator c _ : exprs) = Op c (Value v) (toExprTree exprs) 

Но это на самом деле не так: например, дл 4 * 3 + 2 это дало бы 4 * (3 + 2). Нам действительно нужно привести 4 * вниз к оставшемуся дереву выражений, настолько же глубокому, как и исправления. Таким образом, дерево должно знать об этом также

data ExprTree = Op DInfix Fixity ExprTree ExprTree 
       | Value Double 

mergeOpL :: Double -> DInfix -> Fixity -> ExprTree -> ExprTree 
mergeOpL v c f t@(Op c' f' t' t'') 
    | c > c' = Op c' f' (mergeOpL v c f t') t'' 
mergeOpL v c f t = Op c f (Value v) t 

Что еще предстоит сделать, это обработка скобок. Вам нужно будет взять целое выражение в виде скобок и назначить ему фиксированное значение дерева, скажем tight = 100 :: Fixity.

---

Как примечание: такая токенизации - ручной разбор рабочий процесс является довольно громоздким, независимо от того насколько хорошо функционально вы это делаете. У Haskell есть мощные библиотеки парсер-комбинаторов, такие как parsec, которые отнимают у вас большую часть работы и бухгалтерии.

Answer 2

Что вам нужно для решения этой проблемы - это алгоритм Шунтингового двора Эдсгера Дийстры, как описано в http://www.wcipeg.com/wiki/Shunting_yard_algorithm. Вы можете увидеть мою реализацию at the bottom of this file.

Если вы ограничиваете вашу собственную личность только +, -, *,/вы также можете решить эту проблему, используя обычный прием в большинстве интро компилятор примеров просто разборе в двух различных нетерминалов, Ofter называется term и product к построить правильное дерево. Это становится громоздким, если вам приходится иметь дело с большим количеством операторов или они определены пользователем.