DS Balanced Symbols (A General Case)

Section 3.7 Balanced Symbols (A General Case)

The balanced parentheses problem shown above is a specific case of a more general situation that arises in many programming languages. The general problem of balancing and nesting different kinds of opening and closing symbols occurs frequently. For example, in Kotlin square brackets, [ and ], are used for indexing in lists; curly braces, { and }, are used for delimiting code blocks; and parentheses, ( and ), are used for arithmetic expressions. It is possible to mix symbols as long as each maintains its own open and close relationship. Strings of symbols such as:

🔗

{ { ( [ ] [ ] ) } ( ) }

[ [ { { ( ( ) ) } } ] ]

[ ] [ ] [ ] ( ) { }

are properly balanced in that not only does each opening symbol have a corresponding closing symbol, but the types of symbols match as well.

🔗

Compare those with the following strings that are not balanced:

🔗

( [ ) ]

( ( ( ) ] ) )

[ { ( ) ]

The basic parentheses checker from the previous section can, with a few changes, be extended to handle these new types of symbols. Recall that each opening symbol is simply pushed on the stack to wait for the matching closing symbol to appear later in the sequence. When a closing symbol does appear, the only difference is that we must check to be sure that it correctly matches the type of the opening symbol on top of the stack. If the two symbols do not match, the string is not balanced. Once again, if the entire string is processed and nothing is left on the stack, the string is correctly balanced.

🔗

The Kotlin program to implement this is shown in Listing 3.7.1. The main change is that we use a map to keep track of the closing symbol that matches each opening one, which we define in line 2. In line 15, we check that each symbol that is removed from the stack matches the current closing symbol. If a mismatch occurs, the balance checker returns false immediately.

🔗

Listing 3.7.1. Solving the General Balanced Symbol Problem

🔗

interface StackADT<T> {

// Returns true if there are no items on the stack;
    // false otherwise.
    fun isEmpty(): Boolean

// Pushes given item on the top of the stack
    fun push(item: T)

// Removes the item on top of the stack and returns it.
    // If the stack is empty, throws an exception.
    fun pop(): T

// Returns the item on top of the stack without removing it.
    // If the stack is empty, throws an exception.
    fun peek(): T

// Returns the number of items on the stack.
    fun size(): Int
}

class ListStack<T> : StackADT<T> {

/*
     * Create a new stack. The top of the stack is at the end
     * of the list.
     */
    private val items = mutableListOf<T>()

/*
     * Returns true if there are no items on the stack;
     * false otherwise.
     */
    override fun isEmpty(): Boolean {
        return items.isEmpty()
    }

/*
     * Pushes given item on the top of the stack
     */
    override fun push(item: T) {
        items.add(item)
    }

/*
     * Removes the item on top of the stack and returns it.
     * If the stack is empty, throws an exception.
     */
    override fun pop(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Stack is empty.")
        }
        return items.removeLast()
    }

/*
     * Returns the item on top of the stack without removing it.
     * If the stack is empty, throws an exception.
     */
    override fun peek(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Stack is empty.")
        }
        return items[items.count() - 1]
    }

/*
     * Returns the number of items on the stack.
     */
    override fun size(): Int {
        return items.count()
    }

/*
     * Convert to string as an array from bottom to top
     */
    override fun toString(): String {
        return items.toString()
    }
}

^^^^fun balanceCheck(symbolString: String): Boolean {
    val matchingMap = mapOf('(' to ')', '{' to '}', '[' to ']')
    val openers = matchingMap.keys
    val closers = matchingMap.values

val symStack = ListStack<Char>()

for (symbol in symbolString) {
        if (symbol in openers) {
            symStack.push(symbol)
        } else if (symbol in closers) {
            if (symStack.isEmpty()) {
                return false
            } else {
                if (matchingMap[symStack.pop()] != symbol) {
                    return false
                }
            }
        } else {
            // not a parenthesis; skip over it
        }
    }

return symStack.isEmpty()
}

fun main() {
    println(balanceCheck("{({([][])}())}")) // expect true
    println(balanceCheck("[{()]")) // expect false
    println(balanceCheck("[{()]]")) // expect false
}

These two examples show that stacks are very important data structures for the processing of language constructs in computer science. Almost any notation you can think of has some type of nested symbol that must be matched in a balanced order. There are a number of other important uses for stacks in computer science. We will continue to explore them in the next sections.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next