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 Python square brackets, [ and ], are used for lists; curly brackets, { and }, are used for dictionaries; and parenthesis, ( and ), are used for tuples and arithmetic expressions. In 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 Task 3.7.1.a. The key C++ feature appears in line 38 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.

Exploration 3.7.1. Generalized Balance Symbol Checking.

(a) C++ Implementation.

//program that returns whether a string is balanced or not
#include <iostream>
#include <string>
#include <stack>

using namespace std;

//returns true of symbol is in symbols
bool inString(string symbol, string symbols){
    return symbols.find(symbol) != string::npos;
}

//returns true if the symbol in "open"
//matches the symbol in "close"
bool matches(string open, string close){
    string opens = "({[";
    string closers = ")]}";
    bool val = inString(open, opens) == inString(close, closers);
    return val;
}

// Go through the string pushing opening symbols
// and popping/matching when a closing symbol is
// encountered
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 = "([{";
        string closes = "}])";
        if (inString(symbol, opens)){
            s.push(symbol);
        } else if(inString(symbol, closes)){
            if (s.empty()){
                balanced = false;
            } else {
                string top = s.top();
                s.pop();
                if (!matches(top, symbol)){
                    balanced = false;
                    break;
                }
            }
        }
        index = index + 1;
    }
    if(balanced && s.empty()){
        return true;
    } else {
        return false;
    }
}

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

(b) Python Implementation.

#Program does the same as before, except with 2 extra symbols.

from pythonds.basic.stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{": #if the current symbol ==
                            #an open symbol.
            s.push(symbol)
        else:
            if s.isEmpty(): #if there is a closed symbol
                            #but no open symbol is pending.
                balanced = False
            else:
                top = s.pop()
                if not matches(top,symbol): #if the current closed symbol
                                            #is a different type than the
                                            #pending open one.
                       balanced = False
        index = index + 1
    if balanced and s.isEmpty(): #if the string is completely analyzed with
                                 #no remaining open symbols.
        return True
    else:
        return False

def matches(open,close):
    #Checks if the type of an open and closed symbol are the same.
    opens = "([{"
    closers = ")]}"
    return opens.index(open) == closers.index(close)

def main():
    print(parChecker('{[([][])]()}'))
    print(parChecker('[{()]'))
main()

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.

Reading Questions
Reading Question

1.

Using the program below, click on the line of code that adds an open parenthesis to the stack.

Remember that the function to do this would be the push function.

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;:
      }
}

You have attempted of activities on this page.

Prev Top Next

Section 3.7 Balanced Symbols - A General Case

Exploration 3.7.1. Generalized Balance Symbol Checking.

(a) C++ Implementation.

(b) Python Implementation.

Reading Questions Reading Question

1.

Reading Questions
Reading Question