# alech's solution

## to Bracket Push in the PureScript Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Given a string containing brackets [], braces {} and parentheses (), verify that all the pairs are matched and nested correctly.

Ginna Baker

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### Main.purs

module Test.Main where

import Prelude

import Effect (Effect)
import Test.Unit.Assert as Assert
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Main (runTest)
import BracketPush (isPaired)

main :: Effect Unit
main = runTest suites

suites :: TestSuite
suites = do
suite "BracketPush.isPaired" do

test "paired square brackets" $Assert.equal true (isPaired "[]") test "empty string"$
Assert.equal true
(isPaired "")

test "unpaired brackets" $Assert.equal false (isPaired "[[") test "wrong ordered brackets"$
Assert.equal false
(isPaired "}{")

test "paired with whitespace" $Assert.equal true (isPaired "{ }") test "simple nested brackets"$
Assert.equal true
(isPaired "{[]}")

test "several paired brackets" $Assert.equal true (isPaired "{}[]") test "paired and nested brackets"$
Assert.equal true
(isPaired "([{}({}[])])")

test "unopened closing brackets" $Assert.equal false (isPaired "{[)][]}") test "unpaired and nested brackets"$
Assert.equal false
(isPaired "([{])")

test "paired and wrong nested brackets" $Assert.equal false (isPaired "[({]})") test "math expression"$
Assert.equal true
(isPaired "(((185 + 223.85) * 15) - 543)/2")

test "complex latex expression" $Assert.equal true (isPaired "\\left(\\begin{array}{cc} \\frac{1}{3} & x\\\\ \\mathrm{e}^{x} &... x^2 \\end{array}\\right)") module BracketPush ( isPaired ) where import Prelude import Data.Array (elem, findIndex, scanl) import Data.Maybe (Maybe(..), isJust, maybe) import Data.String (splitAt, toCharArray, uncons) isPaired β· String β Boolean isPaired s = case uncons s of Nothing β -- empty string is paired true Just { head, tail } β if head elem closingChars then false else if head elem openingChars then -- we have to find a closing "opposite" if hasClosingParen head tail then -- if we found one, everything "inside" has to be paired -- and also everything after it. -- e.g. "[inner]rest" isPaired (inner head tail) && isPaired (rest head tail) else false else isPaired tail -- nothing to see here, continue where openingChars β· Array Char openingChars = ['[', '{', '('] closingChars β· Array Char closingChars = map opposite openingChars opposite β· Char β Char opposite '[' = ']' opposite '{' = '}' opposite '(' = ')' opposite c = c -- would have liked to curry even more, but -- hasClosingParen = isJust <<< opposingParenIndex does not work (!?) hasClosingParen β· Char β String β Boolean hasClosingParen h = isJust <<< opposingParenIndex h -- search for the index of the opposing character for h in t, -- taking nesting into account, e.g. -- opposingParenIndex '[' "[[{}]foobar]baz" β 11 opposingParenIndex β· Char β String β Maybe Int opposingParenIndex h t = findIndex (_ == 0) (scanl (parenCount h) 1$ toCharArray t)
where
parenCount β· Char β Int β Char β Int
parenCount c a ch
| ch == c            = a + 1
| ch == (opposite c) = a - 1
| otherwise          = a

-- extract the part inside from string consisting of head and tail
-- e.g. inner '[' "foobar]" β "foobar"
inner β· Char β String β String
inner h t =
maybe "" (\r β r.before) $(\i β splitAt i t) =<< opposingParenIndex h t -- extract the part after pair from string consisting of head and tail -- e.g. inner '[' "foobar]baz" β "baz" rest β· Char β String β String rest h t = maybe "" (\r β r.after)$ (\i β splitAt (i+1) t) =<< opposingParenIndex h t