## C++ || Stack – Using A Stack, Determine If A Set Of Parentheses Is Well-Formed Here is another homework assignment which was presented in a C++ Data Structures course. This assignment was used to introduce the stack ADT, and helped prepare our class for two later assignments which required using a stack. Those assignments can be found here:

```(1) Stack Based Infix To Postfix Conversion (Single Digit) (2) Stack Based Postfix Evaluation (Single Digit)```

REQUIRED KNOWLEDGE FOR THIS PROGRAM

```Stack Data Structure Cin.getline #include "ClassStackListType.h" ```

A simple exercise for testing a stack is determining whether a set of parenthesis is “well formed” or not. What exactly is meant by that? In the case of a pair of parenthesis, for an expression to be well formed, consider the following table.

``` Well-Formed Expressions | Ill-Formed Expressions ------------------------------------|-------------------------------------- ( a b c [ ] ) | ( a b c [ ) ( ) [ ] { } | ( ( { ( a b c d e ) ( ) } | [ a b c d e ) ( ) } ( a + [ b - c ] / d ) | ( a + [ b - c } / d ) 123456 Well-Formed Expressions             |           Ill-Formed Expressions------------------------------------|--------------------------------------( a b c [ ] )                       |             ( a b c [ )( ) [ ] { }                         |             ( ({ ( a b c d e ) ( ) }               |             [ a b c d e ) ( ) }( a + [ b - c ] / d )               |             ( a + [ b - c } /  d ) ```

Given an expression with characters and parenthesis, ( ), [ ], and { }, our class was asked to determine if an expression was well formed or not by using the following algorithm:

``` // An algorithm for a Well Formed expression Set 'balanced' to true Set 'symbol' to the first character in the current expression while(there are more characters AND 'balanced' == true) { if('symbol' is an opening symbol) { Push 'symbol' onto the stack } else if('symbol' is a closing symbol) { if the stack is empty 'balanced' = false else Set the 'openSymbol' to the item at the top of the stack Pop the stack Check to see if 'symbol' matches 'openSymbol' (i.e - if openSymbol == '(' and symbol == ')' then 'balanced' = true) } Set 'symbol' to the next character in the current expression } if('balanced' == true AND stack is empty) { Expression is well formed } else { Expression is NOT well formed }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233 // An algorithm for a Well Formed expression Set 'balanced' to trueSet 'symbol' to the first character in the current expression while(there are more characters AND 'balanced' == true){    if('symbol' is an opening symbol)    {        Push 'symbol' onto the stack    }    else if('symbol' is a closing symbol)    {        if the stack is empty            'balanced' = false        else            Set the 'openSymbol' to the item at the top of the stack            Pop the stack            Check to see if 'symbol' matches 'openSymbol'            (i.e - if openSymbol == '(' and symbol == ')'            then 'balanced' = true)    }    Set 'symbol' to the next character in the current expression} if('balanced' == true AND stack is empty){    Expression is well formed}else{    Expression is NOT well formed}// http://programmingnotes.org/ ```

======= WELL-FORMED EXPRESSIONS =======

This program uses a custom template.h class. To obtain the code for that class, click here.

``` Is The Expression Well-Formed? C++ // ============================================================================ // Author: Kenneth Perkins // Date: May 14, 2012 // Taken From: http://programmingnotes.org/ // File: wellFormed.cpp // Description: Demonstrates how to check if an expression is well formed // ============================================================================ #include <iostream> #include "ClassStackListType.h" using namespace std; // function prototypes bool IsOpen(char symbol); bool IsClosed(char symbol); bool IsWellFormed(char openSymbol, char closeSymbol); int main() { // declare variables char expression; char openSymbol; int index=0; bool balanced = true; StackListType<char> stack; // this is the stack declaration // obtain data from the user using a char array cout <<"Enter an expression and press ENTER. "<<endl; cin.getline(expression,sizeof(expression)); cout << "\nThe expression: " << expression; // loop thru the char array until we reach the 'NULL' character // and while 'balanced' == true while (expression[index]!='\0' && balanced) { // if input is an "open bracket" push onto stack // else, process info if (IsOpen(expression[index])) { stack.Push(expression[index]); } else if (IsClosed(expression[index])) { if(stack.IsEmpty()) { balanced = false; } else { openSymbol = stack.Top(); stack.Pop(); balanced = IsWellFormed(openSymbol, expression[index]); } } ++index; } if (balanced && stack.IsEmpty()) { cout << " is well formed..." << endl; } else { cout << " is NOT well formed!!! " << endl; } }// End of Main bool IsOpen(char symbol) { if ((symbol == '(') || (symbol == '{') || (symbol == '[')) { return true; } else { return false; } }// End of IsOpen bool IsClosed(char symbol) { if ((symbol == ')') || (symbol == '}') || (symbol == ']')) { return true; } else { return false; } }// End of IsClosed bool IsWellFormed(char openSymbol, char closeSymbol) { return (((openSymbol == '(') && closeSymbol == ')') || ((openSymbol == '{') && closeSymbol == '}') || ((openSymbol == '[') && closeSymbol == ']')); }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 // ============================================================================//    Author: Kenneth Perkins//    Date:   May 14, 2012//    Taken From: http://programmingnotes.org///    File:  wellFormed.cpp//    Description: Demonstrates how to check if an expression is well formed// ============================================================================#include <iostream>#include "ClassStackListType.h"using namespace std; // function prototypesbool IsOpen(char symbol);bool IsClosed(char symbol);bool IsWellFormed(char openSymbol, char closeSymbol); int main(){    // declare variables    char expression;    char openSymbol;    int index=0;    bool balanced = true;    StackListType<char> stack; // this is the stack declaration     // obtain data from the user using a char array    cout <<"Enter an expression and press ENTER. "<<endl;    cin.getline(expression,sizeof(expression));     cout << "\nThe expression: " << expression;     // loop thru the char array until we reach the 'NULL' character    // and while 'balanced' == true    while (expression[index]!='\0' && balanced)    {        // if input is an "open bracket" push onto stack        // else, process info        if (IsOpen(expression[index]))        {            stack.Push(expression[index]);        }        else if (IsClosed(expression[index]))        {            if(stack.IsEmpty())            {                balanced = false;            }            else            {                openSymbol = stack.Top();                stack.Pop();                balanced = IsWellFormed(openSymbol, expression[index]);            }        }        ++index;    }     if (balanced && stack.IsEmpty())    {        cout << " is well formed..." << endl;    }    else    {        cout << " is NOT well formed!!! " << endl;    }}// End of Main bool IsOpen(char symbol){    if ((symbol == '(') || (symbol == '{') || (symbol == '['))    {        return true;    }    else    {        return false;    }}// End of IsOpen bool IsClosed(char symbol){    if ((symbol == ')') || (symbol == '}') || (symbol == ']'))    {        return true;    }    else    {        return false;    }}// End of IsClosed bool IsWellFormed(char openSymbol, char closeSymbol){    return (((openSymbol == '(') && closeSymbol == ')') || ((openSymbol == '{') && closeSymbol == '}')        || ((openSymbol == '[') && closeSymbol == ']'));}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output
(Note: the code was compile four separate times to display different output)

`====== RUN 1 ======`

``` Enter an expression and press ENTER. (( The expression: (( is NOT well formed!!! ====== RUN 2 ====== Enter an expression and press ENTER. (a{b[]}c) The expression: (a{b[]}c) is well formed... ====== RUN 3 ====== Enter an expression and press ENTER. [(7 * 28) - 1987] The expression: [(7 * 28) - 1987] is well formed... ====== RUN 4 ====== Enter an expression and press ENTER. {3 + [2 / 3] - (9 + 18) * 12) ```

```The expression: {3 + [2 / 3] - (9 + 18) * 12) is NOT well formed!!! ```

👍 YesNo

### 2 Responses to C++ || Stack – Using A Stack, Determine If A Set Of Parentheses Is Well-Formed

1. Krushkrush says:

how to read a file in text and make it check parenthesis using stacks?? any idea is appreciated

• admin says:

Hello, thanks for visiting

To read a text file to check parentheses, the program flow of control would be exactly the same as the example program demonstrated on this page.

The only thing differently you would do is, instead of using “cin” to read data into a string, you would use a file operator (such as ifstream) to read data into the program.