4
\$\begingroup\$

I solved this stack problem in Swift. Looking for any feedback on my code:

enter image description here

import Foundation
/// Returns an integer read from one line of standard input.
func readInteger() -> Int {
    guard let line = readLine() else {
        fatalError("Unexpected end of input")
    }
    guard let i = Int(line) else {
        fatalError("Invalid integer in input")
    }
    return i
}

/// Returns an array of Characters
func readStrings() -> [Character] {
    guard let line = readLine() else {
        fatalError("Unexpected end of input")
    }
    return line.characters.map{ $0 }
}

// checks if all brackets are balanced
func balancedBrackets() {
    let sequences = readInteger()
    // outloop loops through each sequence line
    outerLoop: for _ in 0..<sequences {
        // create a stack (array in this case)
        var stack = [Character]()
        // each line of sequence
        let sequence = readStrings()
        // edgeCase is when there are only opening brackets in stack and didn't reach case } ] )
        var edgeCase = false
        // inner loop loops through each bracket character
        innerLoop: for bracket in sequence {
            switch bracket {
            // if opening brackets, append and set edgeCase
            case "{", "[", "(":
                stack.append(bracket)
            // case closing brackets
            case "}", "]", ")":
                // checks for empty stack or if the bracket pairs arent matching
                if stack.isEmpty || (bracket == "}" && stack.last != "{") || (bracket == "]" && stack.last != "[") || (bracket == ")" && stack.last != "(")  {
                    edgeCase = true
                    print("NO")
                    // append closing bracket so YES doesn't print when breaking
                    stack.append(bracket)
                    // break out of checking anymore brackets
                    break innerLoop
                }
                stack.removeLast()
            default:
                fatalError("unknown bracket found")
            }
        }
        // if empty
        if stack.isEmpty {
            print("YES")
        } else if !edgeCase { // stack has opening brackets and hasn't reach if statement in case } ] )
            print("NO")
        }
    }
}

balancedBrackets()
\$\endgroup\$
7
\$\begingroup\$

readStrings() is better named readCharacters() because that is what it does. I prefer Array(...) instead of .map { $0 } to convert a sequence into an array, but that is a matter of taste:

/// Reads one line from standard input and returns the result
/// as an array of characters.
func readCharacters() -> [Character] {
    guard let line = readLine() else {
        fatalError("Unexpected end of input")
    }
    return Array(line.characters)
}

My main point of criticism is that the logic in your main function is far too complicated. The outerLoop: label is not used. The inner loop is confusing, and comments like

    // append closing bracket so YES doesn't print when breaking

    // stack has opening brackets and hasn't reach if statement in case } ] )

clearly indicate a code smell. The problem is that you have one single function doing all the work.

It immediately becomes simpler if you separate the I/O from the actual computations (which is generally a good idea):

func isBalanced(sequence: [Character]) -> Bool {
    // ... return `true` or `false` ...
}

func balancedBrackets() {
    let numSequences = readInteger()
    for _ in 0..<numSequences {
        let sequence = readCharacters()
        let balanced = isBalanced(sequence)
        print(balanced ? "YES" : "NO")
    }
}

balancedBrackets()

This makes the code more modular, better readable, and allows you to add test cases easily. The isBalanced() function can "early return" if a non-match is found, making the labels and the special edgeCase variable obsolete:

func isBalanced(sequence: [Character]) -> Bool {
    var stack = [Character]()
    for bracket  in sequence {
        switch bracket {
        case "{", "[", "(":
            stack.append(bracket)
        case "}", "]", ")":
            if stack.isEmpty
                || (bracket == "}" && stack.last != "{")
                || (bracket == "]" && stack.last != "[")
                || (bracket == ")" && stack.last != "(")  {
                return false
            }
            stack.removeLast()
        default:
            fatalError("unknown bracket found")
        }
    }
    return stack.isEmpty
}

But the repeated usage of character literals is still error-prone. Better define an enumeration:

enum Bracket: Character {
    case Left = "("
    case Right = ")"
    case LeftCurly = "{"
    case RightCurly = "}"
    case LeftSquare = "["
    case RightSquare = "]"
}

Determining the matching open bracket for a given closing bracket can be made a computed property of this enumeration:

enum Bracket: Character {
    case Left = "("
    case Right = ")"
    case LeftCurly = "{"
    case RightCurly = "}"
    case LeftSquare = "["
    case RightSquare = "]"

    /// For a closing bracket, the corresponding opening bracket is returned.
    /// For an opening bracket, `nil` is returned.
    var matchingOpen: Bracket? {
        switch self {
        case .Right:        return .Left
        case .RightCurly:   return .LeftCurly
        case .RightSquare:  return .LeftSquare
        default:            return nil
        }
    }
}

Now the isBalanced() function does not use any explicit bracket values anymore:

func isBalanced(sequence: [Character]) -> Bool {
    var stack = [Bracket]()
    for char in sequence {
        if let bracket = Bracket(rawValue: char) {
            if let open = bracket.matchingOpen {
                // `bracket` is a closing bracket and `open` the corresponding opening bracket:
                guard let last = stack.last where last == open  else {
                    return false
                }
                stack.removeLast()
            } else {
                // `bracket` is an opening bracket:
                stack.append(bracket)
            }
        } else {
            fatalError("unknown bracket found")
        }
    }
    return stack.isEmpty
}

If you decide to add another type of brackets later (e.g. «») then only the enumeration needs to be extended, but not the isBalanced() function.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.