haskell: RPN计算器

Question

我想开发一种堆栈管理系统。列表从空[]开始，用户可以输入数字，它们将被添加到列表中，以及二元操作，该操作将从列表中获取前两个数字并执行操作，然后将其放回列表中。例如：

[] : 3
[3] : 4
[4,3] : +
[7] : c
[] : 123
[123] : 3
[3,123] : *
[369] :

我不知道如何处理来自控制台的输入。我有一段不完整的代码：

import System.Environment   
import System.Directory  
import System.IO  
import Data.List  

stack = []

add1 :: [Int] -> [Int]
add1 [] = []
add1 [x] = [x]
add1 [x,y] = [(x+y)]
add1 x:(y:xs) = (x+y) : (xs : []) 

--sub :: [Int] -> [Int]
--sub [] = []
--sub x:(y:xs) = (x-y) : xs 

--mul :: [Int] -> [Int]
--mul [] = []
--mul x:(y:xs) = (x*y) : xs 

--div :: [Int] -> [Int]
--div [] = []
--div x:(y:xs) = (x/y) : xs 

c :: [Int] -> [Int]
c = []

push :: [Int] -> a -> [Int]
push [] a = [a]
push (x:xs) a = a : (x:xs)

dispatch :: [(String, Int -> IO ())]
dispatch =  [ ("+", add)
       --     , ("-", sub)
       --     , ("*", mul)
       --     , ("/", div)
            ]

xcl = do
    print stack
    answer <- readLine

但我甚至不知道我是否在朝着正确的方向前进。任何帮助都是最好的。谢谢。

Answer 1

您走在正确的道路上；让我们看看我建议对您的代码所做的一些更改。

您的add1函数非常接近，但您有两个小问题-第一个是您提供的模式匹配:为了在语法上正确，您需要将整个匹配放在括号中。第二个是第二个cons (冒号)。cons的类型是a -> [a] -> [a]，因此它可以很好地使用(x+y)作为第一个参数；但是，因为xs已经有了[Int]类型，所以不需要提供: []。

add1 (x:y:xs) = (x+y) : xs

接下来，因为您完全是在处理Int和Int列表，所以在这个上下文中使用某种类型的a没有意义。

push :: [Int] -> Int -> [Int]

最后是你的主力函数。由于Haskell中缺少循环结构，因此创建用户输入循环(也称为REPL)的方法是通过递归。正因为如此，接受一个参数是有意义的。让我们将其作为您的[Int]堆栈。从标准输入中将一行作为字符串读取的函数是getLine，它的类型为IO String。最后，您实际上必须处理该输入。为简单起见，我只是将该逻辑包含在xcl的case语句中，但也可以使用dispatch或类似的函数(实际上，如果您的RPN计算器变得更复杂，这将有其优点)。每种情况的操作都应该通过修改后的堆栈递归到xcl“循环”中。当你退出时，它应该直接退出--这是return的一个很好的用处。

xcl :: [Int] -> IO ()
xcl st = do
    print st
    answer <- getLine
    case answer of
      "q" -> return ()
      "c" -> xcl ([] ::[Int])
      "+" -> xcl $ add1 st
      x -> xcl $ push st $ read x

实际上，您可以更进一步并防止异常-当用户传入一些非函数、非数字字符串时会发生什么？上面的代码将失败，并出现"no parse“异常。最好的解决方法是使用reads代替read，正如this answer中所讨论的那样。reads要么返回一个只有一个条目的列表-一个包含已解析数字和剩余字符串的元组，要么返回一个空列表(表示读取失败)。例如：

      x -> case (reads x) of
        [(num,_)] -> xcl $ push st num
        _ -> xcl st

Answer 2

xcl stack = do
    print stack
    answer <- getLine
    case lookup answer dispatch of
        Just function -> -- we have a function, apply it to the top of the stack
        Nothing -> -- if we have a number, parse it and push it onto the stack
                   -- if not, issue an error

1. stack不能是顶级常量，因为我们想要操作它。因此，我们将其设为xcl的参数。
2. 使用getLine读取一行文本，因为我们不知道要将其解释为运算符名还是数字。

Answer 3

阅读此http://learnyouahaskell.com/functionally-solving-problems#reverse-polish-notation-calculator。这可能是有帮助的。