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

将东西插入不同的堆栈确实感觉是一件非常程序化的事情，而这在 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 本身对运算符的固定性。您可以在 GHCi 中 :i + 来查看它们。)

然后你就可以构建树。

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 ，这会减轻您的大部分工作和簿记工作。