Haskell 后缀形式的中缀

Question

我是 Haskell 的初学者，我有点不知道使用什么来使这个程序工作。我要做的是得到一个像这样的字符串：“a+(b/c)” 并将它变成它的后缀形式，就像这样：“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' 将负责获取符号并以正确的方式组织它们，但我不知道该怎么做。

Answer 1

您的示例 a+(b/c) 并不清楚，但我假设您需要考虑运算符优先级，以便 a+b/c 解析为 a+(b/c)（而不是 (a+b)/c），因此也计算为 abc/+（不是 ab+c/）。

也许有更简单或更惯用的方法来解决这个问题，但作为一项教育任务，这是了解仅使用基本递归函数的好方法。以这种方式解决这个任务主要有两种方法：

Recursive descent parsing
中的shunting yard algorithm，就是专门用于中缀转后缀的

前者更灵活，最终成为惯用 Haskell 解决方案的基础（使用解析器组合器），但调车场算法在这里具有明显的优势，因为它是一种更简单的算法专门用于 infix/postfix 转换任务。

我要做的是勾画和描述实现的结构，帮助你摆脱一般方法的束缚，并给你填写的任务详情。

该算法维护两个状态，一个 stack 运算符和一个 queue 输出。我们可以将两者表示为字符列表：

type ShuntingYardState = ([Char], [Char])

要将一个元素压入堆栈或将一个元素排入输出队列，您需要将它 : cons : 到列表的前面；要从堆栈中弹出一个元素，您可以使用模式匹配。输出队列严格来说是结果的累加器；我们永远不会从它出队。

要将中缀表达式字符串转换为后缀，您可以使用空运算符堆栈和空输出队列的初始状态启动此算法：

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.

  | <strong>isVariable</strong> current
  = shuntingYard (<strong>variable</strong> current state) rest

-- 2. An operator: process operator precedence and proceed.

  | <strong>isOperator</strong> current
  = shuntingYard (<strong>operator</strong> current state) rest

-- 3. A left parenthesis: push it onto the operator stack.

  | current == '('
  = shuntingYard (<strong>leftParenthesis</strong> state) rest

-- 4. A right parenthesis: process grouping and proceed.

  | current == ')'
  = shuntingYard (<strong>rightParenthesis</strong> state) rest

-- 5. An unrecognized token: raise an error.

  | otherwise
  = error $ "unrecognized input: " ++ show rest

-- 6. No more input: finalize the result.
shuntingYard state []
  = <strong>endOfInput</strong> state

您需要填写实现上述每个案例的函数定义，以粗体标出。这是他们的签名和他们的功能描述。

标识一个变量标记，比如你的isLetHelp:
```
isVariable :: Char -> Bool
```
标识一个运算符标记（不是括号），就像你的 isOpHelp:
```
isOperator :: Char -> Bool
```

将变量推送到输出队列：

variable :: Char -> ShuntingYardState -> ShuntingYardState

处理运算符。此功能有两种情况，如下所示。在第一种情况下，它会将运算符从运算符堆栈移动到输出队列，只要它们具有比当前标记更大的优先级（对于 right-associative 运算符，如 ^)，或 大于或等于 优先级（对于 左关联 运算符，如 * 和-)。在第二种情况下，它只是将当前的运算符令牌推送到运算符堆栈。
```
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
```

处理一个右括号同样有两种情况：只要还有剩余的运算符，就把它们移到输出；如果有 none，则需要一个匹配的左括号，否则会引发错误。

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.

Haskell 后缀形式的中缀

Infix to Postfix form in Haskell

algorithm

haskell

list

infix-notation

postfix-notation