list - 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 解决方案的基础(使用解析器组合器)，但调车码算法在这里具有明显的优势，它是一种更简单的算法，专门用于中缀/后缀转换任务。
我要做的是勾勒和描述实现的结构，以帮助您摆脱一般方法的束缚，并给您填写细节的任务。
该算法维护两个状态，一个运算符堆栈和一个输出队列。我们可以将两者表示为字符列表:

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

您需要填写实现上述每种情况的函数的定义，以粗体标记。以下是它们的签名和对其功能的描述。

标识可变 token ，例如您的 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.