Parsing/RPN to infix conversion: Difference between revisions

Content added Content deleted
(→‎{{header|Haskell}}: Fixed typo which broke compilation. Added test in main(). Applied Hlint, Ormolu.)
Line 1,911: Line 1,911:
This solution is a rough translation of the solution provided on RubyQuiz, as linked above.
This solution is a rough translation of the solution provided on RubyQuiz, as linked above.


⚫
<lang Haskell>data Expression = Const String | Exp Expression String Expression
<lang Haskell>
⚫
data Expression = Const String | Exp Expression String Expression


precedence :: Expression -> Int
precedence :: Expression -> Int
precedence (Const _) = 5
precedence (Const _) = 5
precedence (Exp _ op _)
precedence (Exp _ op _)
| op `elem` ["^"] = 4
| op == "^" = 4
| op `elem` ["*","/"] = 3
| op `elem` ["*", "/"] = 3
| op `elem` ["+","-"] = 2
| op `elem` ["+", "-"] = 2
| otherwise = 0
| otherwise = 0


leftAssoc :: Expression -> Bool
leftAssoc :: Expression -> Bool
leftAssoc (Const _) = False
leftAssoc (Const _) = False
leftAssoc (Exp _ op _) = op `notElem` ["^","*","+"]
leftAssoc (Exp _ op _) = op `notElem` ["^", "*", "+"]


rightAssoc :: Expression -> Bool
rightAssoc :: Expression -> Bool
rightAssoc (Const _) = False
rightAssoc (Const _) = False
rightAssoc (Exp _ op _) = op `elem` ["^"]
rightAssoc (Exp _ op _) = op == "^"


instance Show Expression where
instance Show Expression where
show (Const x) = x
show (Const x) = x
show exp@(Exp l op r) = left++" "++op++" "++right
show exp@(Exp l op r) = left <> " " <> op <> " " <> right
where
where left = if leftNeedParen then "( "++(show l)++" )" else show l
left
right = if rightNeedParen the "( "++(show r)++" )" else show r
leftNeedParen = (leftPrec < opPrec) || ((leftPrec == opPrec) && (rightAssoc exp))
| leftNeedParen = "( " <> show l <> " )"
| otherwise = show l
⚫
rightNeedParen = (rightPrec < opPrec) || ((rightPrec == opPrec) && (leftAssoc exp))
right
⚫
leftPrec = precedence l
rightPrec = precedence r
| rightNeedParen = "( " <> show r <> " )"
opPrec = precedence exp
| otherwise = show r
leftNeedParen =
(leftPrec < opPrec)
|| ((leftPrec == opPrec) && rightAssoc exp)
rightNeedParen =
(rightPrec < opPrec)
⚫
|| ((rightPrec == opPrec) && leftAssoc exp)
⚫
leftPrec = precedence l
rightPrec = precedence r
opPrec = precedence exp


buildExp :: [Expression] -> String -> [Expression]
buildExp :: [Expression] -> String -> [Expression]
buildExp stack x
buildExp stack x
| not.isOp $ x = Const x : stack
| not . isOp $ x = Const x : stack
| otherwise = Exp l x r : rest
| otherwise = Exp l x r : rest
where
where r:l:rest = stack
r : l : rest = stack
isOp = (`elem` ["^","*","/","+","-"])
isOp = (`elem` ["^", "*", "/", "+", "-"])


main = do
main :: IO ()
main =
contents <- getContents
mapM_
mapM_ (print.head.(foldl buildExp []).words) (lines contents)
(print . head . foldl buildExp [] . words)
⚫
</lang>
⚫
[ "3 4 2 * 1 5 - 2 3 ^ ^ / +",

⚫
"1 2 + 3 4 + ^ 5 6 + ^",
Input:
"1 4 + 5 3 + 2 3 * * *",
<pre>
3 4 2 * 1 5 - 2 3 ^ ^ / +
"1 2 * 3 4 * *",
1 2 + 3 4 + ^ 5 6 + ^
"1 2 + 3 4 + +"
⚫
]</lang>
⚫
1 4 + 5 3 + 2 3 * * *
{{Out}}
1 2 * 3 4 * *
1 2 + 3 4 + +
<pre>3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
</pre>

Output:
<pre>
⚫
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
( 1 + 4 ) * ( 5 + 3 ) * 2 * 3
( 1 + 4 ) * ( 5 + 3 ) * 2 * 3
1 * 2 * 3 * 4
1 * 2 * 3 * 4
1 + 2 + 3 + 4
1 + 2 + 3 + 4</pre>
</pre>


=={{header|Icon}} and {{header|Unicon}}==
=={{header|Icon}} and {{header|Unicon}}==
Retrieved from "https://rosettacode.org/wiki/Parsing/RPN_to_infix_conversion"