前缀和后缀运算符

February 22, 2019

前缀运算符

假设函数 ff33 个参数,gg22 个,hh11 个,那么

f 1 g 2 h g h 3 4 5f~1~g~2~h~g~h~3~4~5

有如下唯一的语法树:

(f 1 (g 2 (h (g (h 3) 4))) 5)(f~1~(g~2~(h~(g~(h~3)~4)))~5)

维持一个栈,记录已构造好的节点 Done Node 和等待节点的运算符 Wait Operator,每次新运算符入栈为等待状态。每次新运算元入栈后 tryGen 尝试构造,如果一个等待运算符“上面”刚好有它所需数量的 Done Node,那么它们出栈构造出一个新的 Done Node 再入栈,像消除游戏一样继续循环这个过程。

Haskell 实现如下,

import Data.Char(isDigit)

type Operator = Char
type Digit = Char
data Node = Node Operator [Node] | Leaf Digit

data StackItem = Wait Operator | Done Node

instance Show Node where
  show (Node op nodes) = "(" ++ [op] ++ (concat $ map show nodes) ++ ")"
  show (Leaf d) = [d]

parse :: String -> Node
parse str = runParse [] str
  where
    runParse :: [StackItem] -> String -> Node
    runParse stack (currChar:restString)
      | isDigit currChar = runParse (tryGen ((Done (Leaf currChar)):stack)) restString
      | otherwise = runParse ((Wait currChar):stack) restString
      where
        tryGen :: [StackItem] -> [StackItem]
        tryGen ((Done n3):(Done n2):(Done n1):(Wait 'f'):rs) = tryGen (Done (Node 'f' [n1,n2,n3]):rs)
        tryGen ((Done n2):(Done n1):(Wait 'g'):rs) = tryGen (Done (Node 'g' [n1,n2]):rs)
        tryGen ((Done n1):(Wait 'h'):rs) = tryGen (Done (Node 'h' [n1]):rs)
        tryGen stack = stack
    runParse [Done resultNode] [] = resultNode
    runParse _ _ = error "parse error"

输出

parse "f1g2hgh345"
-- (f1(g2(h(g(h3)4)))5)

后缀运算符

后缀运算符的表达式

1 2 h g 3 h 4 h 5 g f1~2~h~g~3~h~4~h~5~g~f

构造出唯一的语法树:

((1 (2 h) g) (3 h) ((4 h) 5 g) f)((1~(2~h)~g)~(3~h)~((4~h)~5~g)~f)

此时的情况则更加简单:栈中只用保留已构造好的节点,每次遇到新的运算元入栈,每次遇到新的运算符则栈中一定有相应数量的已构造好节点 Node,否则出错。实现如下,

parse' :: String -> Node
parse' str = runParse [] str
  where
    runParse :: [Node] -> String -> Node
    runParse stack (currChar:restString)
      | isDigit currChar = runParse ((Leaf currChar):(stack)) restString
      | otherwise = runParse (genNewNode currChar stack) restString
        where
          genNewNode :: Char -> [Node] -> [Node]
          genNewNode 'f' (n3:n2:n1:rs) = (Node 'f' [n1,n2,n3]):rs
          genNewNode 'g' (n2:n1:rs) = (Node 'g' [n1,n2]):rs
          genNewNode 'h' (n1:rs) = (Node 'h' [n1]):rs
          genNewNode _ _ = error "parse error"
    runParse [node] [] = node
    runParse _ _ = error "parse error"

输出

parse' "12hg3h4h5gf"
-- (f(g1(h2))(h3)(g(h4)5))