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 Python square brackets, [ and ], are used for lists; curly braces, { and }, are used for dictionaries; and parentheses, ( and ), are used for tuples and arithmetic expressions. .. include:: file C++, square brackets, [ and ], are used for arrays and vectors, brackets { and } separate possibly nested blocks of code, and operations are given inside of possibly nested parentheses ( and ). 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 simple parentheses checker from the previous section can easily 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.

Implementations of this are shown in ActiveCode 1. The key C++ feature appears in line 16 where we call a helper function, matches, to assist with symbol-matching. Each symbol that is removed from the stack must be checked to see that it matches the current closing symbol. If a mismatch occurs, the Boolean variable balanced is set to false.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

bool inString(string symbol, string symbols){
    int n = symbols.length();
    int symb = symbols.find(symbol);
    if (symb < n){
        return true;
    }
    return false;
}

bool matches(string open, string close){
    string opens = "({[";
    string closers = ")]}";
    return inString(open, opens) == inString(close, closers);
}

bool parChecker(string symbolString){
    stack<string> s;
    bool balanced = true;
    int index = 0;
    int symbolLength = symbolString.length();

while(index < symbolLength && balanced){
        string symbol;
        symbol = symbolString[index];
        string opens = "({[";
        if (inString(symbol, opens)){
            s.push(symbol);
        } else {
            if (s.empty()){
                balanced = false;
            } else {
                string top = s.top();
                s.pop();
                if (!matches(top, symbol)){
                    balanced = false;
                }
            }
        }
        index = index + 1;
    }
    if(balanced && s.empty()){
        return true;
    } else {
        return false;
    }
}

int main() {
    cout << parChecker("{{([][])}()}") << endl;
    cout << parChecker("[{()]") << endl;
}

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 symbols that must be matched in a balanced order. A number of other important uses for stacks exist in computer science. We will continue to explore them in the next sections.

Next Section - 3.8. Converting Decimal Numbers to Binary Numbers