list - Haskell中后缀形式的中缀
问题描述
我是 Haskell 的初学者,我有点不知道用什么来使这个程序工作。我要做的是得到一个这样的字符串:“a+(b/c)”<with letters, not numbers> 并将其转换为它的后缀形式,就像这样:“abc/+”。
问题还说我不能使用以下词:“words, putStr, putStrLn, readLn, print”
首先,我设法将字母与符号分开,然后将它们组合在一起:
isLetter :: String -> String
isLetter [] = []
isLetter (a:as) | a `elem` "abcdefghijklmnopqrstuvwxyz" = a : isLetter as
| otherwise = isLetter as
isOperator :: String -> String
isOperator [] = []
isOperator (a:as) | a `elem` "+-*/^" = a : isOperator as
| otherwise = isOperator as
onp :: String -> String
onp [] = []
onp str = isLetter str ++ isOperator str
问题在于它只是将运算符放在字母之后,而不是在意它实际应该遵循的顺序。
所以我对如何转换它进行了一些研究,我认为我应该首先检查哪个是运算符,哪个是字母,并且根据将中缀转换为后缀的规则,我会将它们放在另一个字符串中。所以我创建了两个函数来判断它是字母还是运算符。
这是一团糟,但它是这样的:
isLetHelp :: Char -> Bool
isLetHelp ch | ch `elem` "abcdefghijklmnopqrstuvwxyz" = True
| otherwise = False
isOpHelp :: Char -> Bool
isOpHelp a | a `elem` "()+-*/^" = True
| otherwise = False
isOperator :: String -> String
isOperator [] = []
isOperator (a:as) | a `elem` "+-*/^" = a : isOperator as
| otherwise = isOperator as
getSymbol :: String -> String
getSymbol [] = []
getSymbol (a:as) | isOpHelp == True = isOperator
| isLetHelp == True = a : getSymbol as
最后一个函数“getSymbol”将负责获取符号并以正确的方式组织它们,但我不知道该怎么做。
解决方案
从您的示例中不清楚a+(b/c)
,但我假设您需要考虑运算符优先级,以便a+b/c
解析为a+(b/c)
(not (a+b)/c
),因此也计算为abc/+
(not ab+c/
)。
可能有更简单或更惯用的方法来解决这个问题,但作为一项教育任务,这是学习使用基本递归函数的好方法。以这种方式解决此任务有两种主要方法:
前者更灵活,最终成为惯用的 Haskell 解决方案的基础(使用解析器组合器),但分流场算法在这里具有明显的优势,它是一种更简单的算法,专门用于中缀/后缀转换任务。
我要做的是勾勒并描述实现的结构,以帮助您摆脱一般方法的束缚,并为您提供填写细节的任务。
该算法维护两个状态,一组运算符和一个输出队列。我们可以将两者都表示为字符列表:
type ShuntingYardState = ([Char], [Char])
要将元素压入堆栈或将元素排入输出中,您需要将:
其放在列表的前面;要从堆栈中弹出一个元素,您可以使用模式匹配。输出队列严格来说是结果的累加器;我们从不退出它。
要将中缀表达式字符串转换为后缀,请从空运算符堆栈和空输出队列的初始状态开始此算法:
expression :: String -> String
expression input = shuntingYard ([], []) input
该算法本身有五个主要情况和一个错误情况供您处理:
shuntingYard
:: ShuntingYardState
-> String
-> String
shuntingYard
state@(operatorStack, outputQueue)
(current : rest)
-- 1. A variable term: push it to the output and proceed.
| isVariable current
= shuntingYard (variable current state) rest
-- 2. An operator: process operator precedence and proceed.
| isOperator current
= shuntingYard (operator current state) rest
-- 3. A left parenthesis: push it onto the operator stack.
| current == '('
= shuntingYard (leftParenthesis state) rest
-- 4. A right parenthesis: process grouping and proceed.
| current == ')'
= shuntingYard (rightParenthesis state) rest
-- 5. An unrecognized token: raise an error.
| otherwise
= error $ "unrecognized input: " ++ show rest
-- 6. No more input: finalize the result.
shuntingYard state []
= endOfInput state
您需要填写实现上述每个案例的函数的定义,以粗体标记。以下是它们的签名和对其功能的描述。
标识一个变量标记,例如您的
isLetHelp
:isVariable :: Char -> Bool
标识操作符标记(不是括号),例如
isOpHelp
:isOperator :: Char -> Bool
将变量推送到输出队列:
variable :: Char -> ShuntingYardState -> ShuntingYardState
处理运算符。这个函数有两种情况,如下图所示。在第一种情况下,它将运算符从运算符堆栈移动到输出队列,只要它们具有比当前标记更高的优先级(对于像这样的右关联运算符
^
),或者更高或相等的优先级(对于像和这样的左关联运算符) )。在第二种情况下,它只是将当前操作符标记推送到操作符堆栈。*
-
operator :: Char -> ShuntingYardState -> ShuntingYardState operator current (op : operatorStack, outputQueue) | op /= '(' , … -- Compare precedence & associativity. = operator … -- Repeat. operator current (operatorStack, outputQueue) = … -- Push the operator and return.
通过将左括号推送到运算符堆栈来处理它。
leftParenthesis :: ShuntingYardState -> ShuntingYardState
处理右括号同样有两种情况:只要还有运算符,就将它们移动到输出;如果没有,则期望匹配的左括号,否则会引发错误。
rightParenthesis :: ShuntingYardState -> ShuntingYardState rightParenthesis (op : operatorStack, outputQueue) | op /= '(' = rightParenthesis … -- Move operator to output. | otherwise = … -- Reached matching left parenthesis; return. rightParenthesis ([], outputQueue) = … -- Mismatched right parenthesis; error.
最后,当到达输入结束时,有三种情况。如果运算符堆栈为空,则可以将队列转换为最终输出字符串。否则,如果还有算子,则一一移动到输出;如果任何括号仍然存在,则它们缺少匹配的右括号,因此这是一个错误。
endOfInput :: ShuntingYardState -> String endOfInput ([], outputQueue) = … -- Success! Return the final result. endOfInput (op : operatorStack, outputQueue) | op == '(' = … -- Mismatched left parenthesis; error. | otherwise = … -- Operator remaining; move to output and repeat.
推荐阅读
- c# - .Net Core 3.1 Entity Framework:在一对多关系中同时插入
- excel - 有没有办法在使用 VBA 从 excel 导出后保持表格格式?
- angular - 在 PrimeNg 中验证最小大小的文件上传
- python - 如何将从 tesseract 提取的文本转换为 pandas 数据框
- linux - 如何在每个星期五的奇数周和偶数周指导我的 cron 运行工作?
- flutter - setState() 或 markNeedsBuild() 在构建期间调用,使用 FutureBuilder 中的 Provider 和 Flutter 中的 StreamBuilder
- docker - Docker 未在 Windows 10 上启动
- r - 如何使用加权采样连接数据?
- php - 在 Discord 中更改我的机器人发送的消息内容
- clipboard - Windows 10 剪贴板历史记录不适用于 VMWare VDI