5
\$\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\$
9
\$\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\$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .