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

May 14, 2012 admin 2 Comments

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 )
			
				
					
				
					1
2
3
4
5
6
				
						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/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
				
						// 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/

======= 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[120];
    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/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
				
						// ============================================================================
//    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[120];
    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!!!

Was this article helpful?

👍 YesNo

Posted in: Advanced, C++ Tags: array, functions, if/else, Sentence, stack, While Loop

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

Krushkrush says:

April 8, 2014 at 12:19 pm

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

Reply
- admin says:
  
  April 8, 2014 at 4:15 pm
  
  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.
  
  Click here if you dont know how to work with files.
  
  Hope this helps
  
  Reply

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

Related

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

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories