Infix to Postfix form in Haskell

Question

I'm a beginner in Haskell and i'm kind of lost on what to use to make this program work. What i have to do is get a String like this: "a+(b/c)" <with letters, not numbers> and turn it into its postfix form, which would be like this: "abc/+".

The question also says that i can't use the following words: "words, putStr, putStrLn, readLn, print"

First thing i managed to separate the letters from the symbols, and get them together afterwards:

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

The problem is that it just puts the operators after the letters, not minding the order that it should actually follow.

So i did a little research on how to transform it and i thought that i should first check which is an operator and which is a letter and, based on the rules of transforming infix to postfix, i would be putting them together in another string. So i created two functions that would tell whether it's a letter or an operator.

It's a mess, but it is like this:

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

This last function 'getSymbol' would be responsible to get the symbols and organize them the right way, but i have no clue how to do it.

Answer 1

It’s not clear from your example a+(b/c), but I assume you need to account for operator precedence, so that a+b/c parses as a+(b/c) (not (a+b)/c), and thus also evaluates to abc/+ (not ab+c/).

There are perhaps simpler or more idiomatic ways of going about this, but as an educational task this is a good way to learn about working with just basic recursive functions. There are two main ways to solve this task this way:

• Recursive descent parsing

• The shunting yard algorithm, which is specifically for converting infix to postfix

The former is more flexible and ultimately the basis of what an idiomatic Haskell solution would look like (using parser combinators), but the shunting yard algorithm has the distinct advantage here of being a simpler algorithm specifically for this task of infix/postfix conversion.

What I’ll do is sketch out and describe the structure of the implementation, to help you get unstuck on the general method, and give you the task of filling in the details.

The algorithm maintains two pieces of state, a stack of operators, and a queue of output. We can represent both as a list of characters:

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

To push an element to the stack or enqueue an element in the output, you’ll cons : it onto the front of the list; to pop an element from the stack, you can use pattern matching. The output queue is strictly an accumulator for results; we never dequeue from it.

To convert an infix expression string to postfix, you start this algorithm with the initial state of an empty operator stack and empty output queue:

expression :: String -> String
expression input = shuntingYard ([], []) input

The algorithm itself has five main cases and one error case for you to handle:

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

You need to fill in the definitions of the functions implementing each case above, marked in bold. Here are their signatures and a description of their function.

• Identifies a variable token, like your isLetHelp:

  isVariable :: Char -> Bool
  

• Identifies an operator token (not a parenthesis), like your isOpHelp:

  isOperator :: Char -> Bool
  

• Pushes a variable to the output queue:

  variable :: Char -> ShuntingYardState -> ShuntingYardState
  

• Processes an operator. This function has two cases, sketched below. In the first case, it moves operators from the operator stack to the output queue as long as they have either greater precedence than the current token (for right-associative operators like ^), or greater or equal precedence (for left-associative operators like * and -). In the second case, it simply pushes the current operator token to the operator stack.

  operator :: Char -> ShuntingYardState -> ShuntingYardState
  
  operator current (op : operatorStack, outputQueue)
    | op /= '('
    , …           -- Compare precedence & associativity.
    = operator …  -- Repeat.
  
  operator current (operatorStack, outputQueue)
    = …  -- Push the operator and return.
  

• Processes a left parenthesis by pushing it to the operator stack.

  leftParenthesis :: ShuntingYardState -> ShuntingYardState
  

• Processing a right parenthesis likewise has two cases: as long as there are operators remaining, move them to the output; if there are none, then expect a matching left parenthesis, or else raise an error.

  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.
  

• Finally, when reaching the end of input, there are three cases. If the operator stack is empty, you can convert the queue to the final output string. Otherwise, if there are operators remaining, move them one by one to the output; if any parentheses remain, they’re missing matching right parentheses, so this is an 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.